ВолБИТ-2018, основной тур, 02 марта 2018 г.


01. Степень 6
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
4 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Ваша первая задача: найти последнюю цифру числа 6n, где n – целое число

Входные данные

Одно целое число n (0 ≤ n ≤ 109)

Выходные данные

Выведите одну цифру – ответ

Пример

Входные данные
2
Выходные данные
6

02. Итоговая оценка
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
4 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

На соревнованиях выступления спортсменов оценивает судейская бригада, которая может состоять из 3-х, 4-х или 5-ти человек. Каждый из судей показывает поставленную им оценку (вещественное число от 0 до 10). Если судей трое, то сначала считается средний балл из всех их оценок, потом отбрасывается оценка, наиболее отклоняющаяся от среднего, и итог получается как среднее из оставшихся (если максимальная и минимальная оценки одинаково отклоняются, то ответ - среднее всех трёх чисел). Если судей четверо или пятеро, то отбрасываются минимальная и максимальная оценки, а итог получается как среднее из оставшихся. По данному количеству судей и их оценкам найдите итоговый балл выступления, выведите его с точностью не менее 4 знаков после десятичной точки.

Входные данные

В первой строке дано количество судей 3 ≤ N ≤ 5. Далее идут N вещественных чисел, содержащие не более чем 3 цифры после десятичной точки

Выходные данные

По данному количеству судей и их оценкам найдите итоговый балл выступления и выведите его с точностью не менее 4 знаков после десятичной точки.

Примеры

Входные данные
3
4
6
10
Выходные данные
5.0000
Входные данные
4
6.2
4.7
6.3
6.3
Выходные данные
6.2500

03. Максимальная сумма
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
4 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

На вход программы поступает последовательность из N натуральных чисел. Нужно выбрать из них произвольное количество чисел так, чтобы их сумма была максимальной и не делилась на 4. В результате программа должна вывести количество выбранных чисел и их сумму. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0.

Входные данные

На вход программе подаётся натуральное число N (N ≤ 106), а затем N натуральных чисел, каждое из которых не превышает 109.

Выходные данные

Программа должна вывести два числа: сначала количество выбранных чисел, а затем их сумму.

Примеры

Входные данные
3
1 2 1
Выходные данные
2 3
Входные данные
2
4 8
Выходные данные
0

04. Количество делителей
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
4 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Дано натуральное число 1 ≤ N ≤ 1018. Известно, что все его простые делители не превышают 10. Найдите количество всех делителей данного числа.

Пример

Входные данные
24
Выходные данные
8

05. Количество чисел
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
4 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Определите сколько существует натуральных чисел, таких, что выполняются следующие условия:

1. Искомые числа не должны превосходить данного N.

2. Искомые числа должны делиться на данные числа a и b и не должны делиться на данное c (числа a, b и c - попарно взаимно простые).

Решения для чисел, не превосходящих 100, будут оцениваться из 35 баллов

Входные данные

В строке ввода даны 4 числа: 1 ≤ N ≤ 1018, 2 ≤ a, b, c ≤ 109

Выходные данные

Напечатайте количество чисел, удовлетворяющих всем данным условиям

Пример

Входные данные
100 2 5 3
Выходные данные
7

06. Радиотелескоп
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
4 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Радиотелескоп пытается получать и анализировать сигналы из космоса. Различные шумы переводятся в последовательность вещественных неотрицательных чисел, заданных с точностью до 1 знака после десятичной точки.

При анализе этих данных потребовалось выбрать такое непустое подмножество сигналов (в него может войти как один сигнал, так и все), произведение значений которого будет максимальным. Определите, какие сигналы войдут в это подмножество.

Входные данные

Дано количество сигналов 1 ≤ N ≤ 106, далее идут N вещественных чисел 0.0 ≤ ai ≤ 10000.0

Выходные данные

Выведите номера сигналов (нумерация идёт с единицы), которые войдут в результирующее множество. Номера следует выводить в порядке возрастания. В случае нескольких правильных ответов выведите любой.

Пример

Входные данные
5
12.3
0.1
100.2
0.3
1.4
Выходные данные
1 3 5 

07. Дата контеста
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
4 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Известна дата начала некоторого образовательного проекта (3 натуральных числа: день 1 ≤ d ≤ 31, месяц 1 ≤ m ≤ 12 и год 1000 ≤ y ≤ 9999). Конкурс будет проводиться спустя 1 ≤ k ≤ 1000 дней после начала проекта. Определите дату конкурса.

Пример

Входные данные
29 1 2018
32
Выходные данные
2 3 2018

08. Радиус окружности
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
4 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

У правильного треугольника ABC и квадрата ACDE есть общая сторона AC, ее длина равна a (вещественное число от 0 до 100). Через точки E, D, B провели окружность. Напечатайте радиус окружности, округлив его до ближайшего целого числа.

Пример

Входные данные
3.7
Выходные данные
4

09. Треугольник наибольшей площади
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
4 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

На плоскости дан набор точек с целочисленными координатами. Необходимо найти треугольник наибольшей площади с вершинами в этих точках, одна из сторон которого лежит на оси OX.

Входные данные

В первой строке вводится одно целое положительное число – количество точек 1 ≤ N ≤ 106. Каждая из следующих N строк содержит два целых числа – сначала координата  - 109 ≤ x ≤ 109, затем координата  - 109 ≤ y ≤ 109 очередной точки.

Выходные данные

Программа должна вывести одно число – максимальную площадь треугольника, удовлетворяющего условиям задачи, с точностью не менее 4 цифр после точки. Если такого треугольника не существует, программа должна вывести ноль.

Пример

Входные данные
6
0 0
2 0
0 4
3 3
5 5
-6 -6
Выходные данные
6.0

10. Автогонки
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
4 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Гоночная трасса состоит из двух основных дорог и нескольких переездов, позволяющих перейти с одной дороги на другую. На всех участках, включая переезды, движение разрешено только в одну сторону, поэтому переезд возможен только с дороги A на дорогу B. Гонщик стартует в точке A0 и должен финишировать в точке BN. Он знает, за какое время сможет пройти каждый участок пути по каждой дороге, то есть время прохождения участков A0A1, A1A2, ..., AN - 1AN, B0B1, B1B2, ..., BN - 1BN. Время прохождения всех переездов A0B0, A1B1, ..., ANBN одинаково и известно гонщику. Необходимо определить, за какое минимальное время гонщик сможет пройти трассу. Решения, верно работающие при количестве участков не более 10, будут оцениваться из 20 баллов.

Входные данные

В первой строке задаётся количество участков трассы 1 ≤ N ≤ 106. Во второй строке задаётся целое число 1 ≤ t ≤ 10000 – время (в секундах) прохождения каждого из переездов A0B0, A1B1, …, ANBN. В каждой из последующих N строк записано два целых числа 1 ≤ ai, bi ≤ 10000, задающих время (в секундах) прохождения очередного участка на каждой из дорог. В первой из этих строк указывается время прохождения участков A0A1 и B0B1, во второй – A1A2 и B1B2 и т. д.

Выходные данные

Программа должна напечатать одно целое число: минимально возможное время прохождения трассы (в секундах).

Пример

Входные данные
3
20
320 150
200 440
300 210
Выходные данные
750