Задача A. Улучшение успеваемости ≡

Условие

В лицее на уроках информатики ответы учеников оцениваются целым числом баллов от 2 до 5. Итоговая оценка по информатике выставляется как среднее арифметическое оценок на всех уроках, округленное до ближайшего целого числа. Если среднее значение находится ровно посередине между двумя целыми числами, то оценка округляется вверх.

Примеры округления оценок приведены в таблице.

Все ученики лицея стремятся получить итоговую оценку по информатике не ниже 4 баллов. К сожалению, один из учеников получил на уроках a двоек, b троек и c четверок. Теперь он планирует получить несколько пятерок, причем хочет, чтобы итоговая оценка была не меньше 4 баллов. Ему надо понять, какое минимальное количество пятерок ему необходимо получить, чтобы добиться своей цели.

Требуется написать программу, которая по заданным целым неотрицательные числам a, b и c определяет минимальное количество пятерок, которое необходимо получить ученику, чтобы его итоговая оценка по информатике была не меньше 4 баллов.

Формат входных данных

Входные данные содержат три строки. Первая строка содержит целое неотрицательное число a, вторая строка содержит целое неотрицательное число b, третья строка содержит целое неотрицательное число c.

Примечание

Следует обратить внимание, что входные данные в этой и других задачах не помещаются в стандартный 32-битный тип данных. Необходимо использовать 64-битный тип данных (long long в С++, int64 в Паскале, long в Java).

Формат выходных данных

Выходные данные должны содержать одно число: минимальное число пятерок, которое необходимо получить ученику, чтобы итоговая оценка была не меньше 4 баллов.

Ограничения

0 ≤ a, b, c ≤ 10¹⁵

a + b + c ≥ 1

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.

Примеры тестов

2
0
0

2

Задача B. Призы ≡

Условие

Петр участвует в конкурсе, в котором разыгрывается N призов. Призы пронумерованы от 1 до N.

По итогам конкурса участник может набрать от 2 до N баллов. Если участник наберет K баллов, то он получит один из призов с номером от 1 до K.

Перед тем, как участник выберет свой приз, ведущий конкурса удаляет один из призов с номером от 1 до K. Затем участник может выбрать любой приз из оставшихся K − 1.

Список призов стал известен Петру. Он определил для каждого приза его ценность, для i-го приза она задается целым числом a_i.

Требуется написать программу, которая по заданным ценностям призов определяет для каждого K от 2 до N, приз с какой максимальной ценностью гарантированно достанется Петру, если он наберет в конкурсе K баллов.

Формат входного файла

Первая строка входного файла содержит число N. Вторая строка этого файла содержит N целых чисел: a₁, a₂, …, a_N.

Формат выходного файла

Выходной файл должен содержать одну строку, содержащую N − 1 целых чисел: для каждого K от 2 до N должна быть выведена ценность приза, который достанется Петру, если он наберет K баллов.

Ограничения

2 ≤ N ≤ 100000; 1 ≤ a_i ≤ 10⁹

Система оценки и описание подзадач

Баллы за каждую подзадачу начисляются только в случае, если все тесты успешно пройдены.

Подзадача 1 (24 балла)

N ≤ 100

Подзадача 2 (24 балла)

N ≤ 5000

Подзадача 3 (52 балла)

N ≤ 100 000

Получение информации о результатах окончательной проверки

По запросу сообщается результат окончательной проверки на каждом тесте.

Примеры тестов

5
1 3 4 2 5

1 3 3 4 

Задача C. Удаление чисел ≡

Условие

В ряд выписаны натуральные числа от 1 до n и задано натуральное число k.

Выполняется один или несколько шагов по удалению чисел в этом ряду. На очередном шаге оставшиеся числа просматриваются в возрастающем порядке, и каждое k-е число удаляется. Если после очередного шага осталось меньше k чисел, то процесс удаления чисел завершается.

Необходимо определить, на каком шаге будет удалено число n, или выяснить, что оно не будет удалено до завершения процесса.

Например, пусть n = 13, k = 2.

• На первом шаге будут удалены числа 2, 4, 6, 8, 10 и 12, останутся числа 1, 3, 5, 7, 9, 11 и 13.
• На втором шаге будут удалены числа 3, 7 и 11, останутся числа 1, 5, 9 и 13.
• На третьем шаге будут удалены числа 5 и 13, останутся числа 1 и 9.
• На четвертом шаге будет удалено число 9, останется число 1. Поскольку осталось одно число, процесс завершается.

Таким образом, число 13 будет удалено на третьем шаге.

Требуется написать программу, которая по заданным числам n и k определяет, на каком шаге будет удалено число n.

Формат входных данных

Первая строка входных данных содержит целое число n.

Вторая строка входных данных содержит целое число k.

Формат выходных данных

Требуется вывести одно целое число — номер шага, на котором будет удалено число n, или число 0, если число n не будет удалено.

Ограничения

3 ≤ n ≤ 10¹⁸

2 ≤ k ≤ 100, k < n

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.

Примеры тестов

13
2

3

Задача D. Города ≡

Условие

Юный программист решил придумать собственную игру. Игра происходит на поле размером N×N клеток, в некоторых клетках которого расположены города (каждый город занимает одну клетку; в каждой клетке может располагаться не более одного города). Всего должно быть чётное количество городов.

Изначально про каждую клетку игрового поля известно, расположен ли в ней город или нет. Чтобы начать игру, необходимо разделить игровое поле на два государства так, чтобы в каждом государстве было поровну клеток-городов.

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

Требуется написать программу, которая с учетом сказанного разделит клетки заданного игрового поля между двумя государствами.

Система оценивания

Правильные решения для тестов, в которых всего два города, будут оцениваться из 40 баллов.

Формат входного файла

Формат выходного файла

Ограничения

1 ≤ N ≤ 50

Примеры тестов

3
DDD
DDC
DDC

111
111
112

5
DDDDD
CDCDC
DCCDC
DDDDD
DDDDD

11111
11111
12222
22222
22222

Задача E. Автоматизированное управление доставкой ≡

Условие

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

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

Если после приема очередной посылки суммарный вес посылок в пакете больше или равен x кг, то пакет доставляется в муниципальный почтовый центр, где пакет с посылками перемещается в специальный контейнер.

Если после доставки очередного пакета суммарный вес посылок в контейнере больше или равен y кг, то контейнер перевозится в региональный сортировочный центр, откуда посылки уже доставляются получателям.

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

Требуется написать программу, которая по заданным значениям k — максимального веса посылки, x — необходимого веса пакета для его отправки в муниципальный почтовый центр, и y — необходимого веса контейнера для его отправки в региональный сортировочный центр, определяет минимальный вес контейнера при его перевозке.

Формат входного файла

Входной файл содержит три целых положительных числа, по одному на строке. Первая строка содержит число k. Вторая строка содержит число x. Третья строка содержит число y.

Формат выходного файла

Требуется вывести одно целое число — минимальный возможный вес контейнера при перевозке.

Ограничения

1 ≤ k, x, y ≤ 10⁹

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.

Получение информации о результатах окончательной проверки

По запросу сообщается результат окончательной проверки на каждом тесте.

Пояснение к примеру

В приведенном примере принимаются посылки весом 1 и 2 кг. При накоплении посылок с суммарным весом хотя бы в 7 кг пакет доставляется из клиентского почтового пункта в муниципальный почтовый центр. При накоплении посылок с суммарным весом хотя бы в 20 кг контейнер перевозится из муниципального почтового центра в региональный сортировочный центр.

Минимальный возможный вес контейнера в данном примере составляет 21 кг и достигается, например, следующим образом: в муниципальный почтовый центр последовательно доставляется 3 пакета по 7 кг каждый. Пакет весом 7 кг может получиться, например, после приема семи посылок по 1 кг.

Примеры тестов

2
7
20

21

Задача F. Кольцевая линия ≡

Условие

В городе, в котором живут друзья Андрей и Борис, метро состоит из единственной кольцевой линии, вдоль которой на равном расстоянии друг от друга расположены n станций, пронумерованных от 1 до n. Участок линии метро между двумя соседними станциями называется перегоном.

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

Друзья заметили, что выполняется следующее условие: если загадать некоторую станцию X и выписать для нее два числа: D_a — расстояние от станции, на которой живет Андрей, до станции X и D_b — расстояние от станции, на которой живет Борис, до станции X, то полученная пара чисел [D_a, D_b] будет однозначно задавать станцию X.

Например, если n = 4, Андрей живет на станции 1, а Борис живет на станции 2, то станция 1 задается парой [0, 1], станция 2 — парой [1, 0], станция 3 — парой [2, 1] и станция 4 — парой [1, 2].

Их одноклассник Сергей живет в соседнем городе и не знает, на каких станциях живут Андрей и Борис. Чтобы найти друзей, он заинтересовался, сколько существует вариантов пар станций A, B, таких что если Андрей живет на станции A, а Борис — на станции B, то выполняется описанное выше условие.

Требуется написать программу, которая по числу станций n на кольцевой линии определяет искомое количество вариантов.

Пояснения к примерам

В первом примере подходят следующие варианты:

• Андрей живет на станции 1, а Борис на станции 2;
• Андрей живет на станции 1, а Борис на станции 4;
• Андрей живет на станции 2, а Борис на станции 1;
• Андрей живет на станции 2, а Борис на станции 3;
• Андрей живет на станции 3, а Борис на станции 2;
• Андрей живет на станции 3, а Борис на станции 4;
• Андрей живет на станции 4, а Борис на станции 1;
• Андрей живет на станции 4, а Борис на станции 3.

Система оценки и описание подзадач

В этой задаче три подзадачи. Баллы за подзадачу начисляются только в случае, если все тесты для данной подзадачи успешно пройдены.

Подзадача 1 (25 баллов)

Подзадача 2 (25 баллов)

Подзадача 3 (50 баллов)

Получение информации о результатах окончательной проверки

По запросу сообщается результат окончательной проверки на каждом тесте.

Формат входного файла

Первая строка входного файла содержит одно целое число n.

Формат выходного файла

Выходной файл должен содержать одно число — искомое количество вариантов.

Ограничения

3 ≤ n ≤ 40 000;

Примеры тестов

4

8

5

20

Задача G. Крестьянин и чёрт ≡

Условие

Встретил крестьянин чёрта, и тот говорит ему: «Видишь мост через эту реку? Стоит тебе только перейти через этот мост — у тебя будет втрое больше денег, чем есть. Перейдёшь назад, опять станет втрое больше, чем было. И так каждый раз, как ты будешь переходить через мост».

 — Ой ли? — говорит крестьянин.

 — Верное слово! — уверяет чёрт. — Только чур, уговор! За то, что я тебе утраиваю деньги, ты, каждый раз перейдя через мост, будешь отдавать мне по X копеек. Иначе не согласен.

 — Ну, что же, это не беда! — говорит крестьянин. — Раз деньги будут утраиваться, так отчего же тебе X копеек каждый раз не дать?

Перешёл крестьянин через мост, посчитал деньги — и вправду, стало втрое больше, чем было. Отсчитал X копеек, бросил чёрту, перешёл снова.. После N-го перехода по мосту отсчитал крестьянин в N-й раз X копеек, бросил чёрту и понял, что не осталось у него ни копейки.

Сколько копеек было у крестьянина изначально?

Требуется написать программу, которая по количеству копеек, взятых чёртом за один переход по мосту, и количеству переходов определит изначальное количество копеек у крестьянина.

Формат входных данных

В первой строке ввода содержится целое число X — количество копеек, которые крестьянин будет отдавать чёрту.

Во второй строке содержится целое число N — сколько раз крестьянин смог пройти по мосту, прежде чем у него закончились копейки.

Формат выходных данных

Выведите единственное целое число K — изначальное количество копеек у крестьянина.

Ограничения

1 ≤ X ≤ 10⁹

1 ≤ N ≤ 18

Описание системы оценивания

Баллы начисляются пропорционально количеству пройденных тестов.

По запросу сообщается количество набранных баллов.

Пояснения к примерам

В первом примере у крестьянина изначально было 5 копеек. После перехода по мосту копеек стало 15 и крестьянину пришлось их все отдать чёрту.

Примеры тестов

15
1

5

81
4

40

Задача H. Кондиционеры ≡

Условие

При реализации проекта «Умная школа» было решено в каждый учебный класс выбранной для этого школы установить по кондиционеру нового поколения для автоматического охлаждения и вентиляции воздуха. По проекту в каждом классе должен быть установлен только один кондиционер и мощность кондиционера должна быть достаточной для размеров класса. Чем больше класс, тем мощнее должен быть кондиционер.

Все классы школы пронумерованы последовательно от 1 до n. Известно, что для каждого класса с номером i, требуется ровно один кондиционер, мощность которого больше или равна a_i ватт.

Администрации школы предоставили список из m различных моделей кондиционеров, которые можно закупить. Для каждой модели кондиционера известна его мощность и стоимость. Требуется написать программу, которая определит, за какую минимальную суммарную стоимость кондиционеров можно оснастить все классы школы.

Пояснения к примерам

В первом примере нужно купить один единственно возможный кондиционер за 1000 рублей.

Во втором примере оптимально будет установить в первом и втором классах кондиционеры четвертого типа, а в третьем классе — кондиционер третьего типа. Суммарная стоимость этих кондиционеров будет составлять 13 рублей (3 + 3 + 7).

Система оценивания

Частичные решения для n, m ≤ 1000 будут оцениваться из 50 баллов.

Формат входного файла

Первая строка входного файла содержит одно целое число n — количество классов в школе.

Вторая строка содержит n целых чисел a_i — минимальная мощность кондиционера в ваттах, который можно установить в классе с номером i.

Третья строка содержит одно целое число m — количество предложенных моделей кондиционеров.

Далее, в каждой из m строк содержится пара целых чисел b_j и c_j — мощность в ваттах j-й модели кондиционера и его цена в рублях соответственно.

Формат выходного файла

Выходной файл должен содержать одно число — минимальную суммарную стоимость кондиционеров в рублях. Гарантируется, что хотя бы один корректный выбор кондиционеров существует, и во всех классах можно установить подходящий кондиционер.

Ограничения

1 ≤ n ≤ 50 000;

1 ≤ a_i ≤ 1000;

1 ≤ m ≤ 50 000

1 ≤ b_j ≤ 1000, 1 ≤ c_j ≤ 1000;

Примеры тестов

1
800
1
800 1000

1000

3
1 2 3
4
1 10
1 5
10 7
2 3

13

Задача I. Трёхцветник ≡

Условие

Куст трёхцветника в начале своего роста выглядит, как три ветки, направленные в разные стороны:

В начале очередного цикла цветения каждая ветка пускает два отростка в разные стороны. При этом, ветка продолжает свой рост. Отростки являются ветками, из которых в начале следующего цикла также начнут появляться новые отростки. Каждая ветка даёт отростки ровно один раз.

После первого и второго циклов цветения трёхцветник примет следующий вид:

Юному садоводу стало интересно узнать количество веток у куста трёхцветника после N циклов цветения.

Требуется написать программу, которая считывает количество циклов цветения, и вычисляет количество веток.

Формат входных данных

Первая строка содержит одно целое число N — количество циклов цветения.

Формат выходных данных

В единственной строке выведите ответ на задачу.

Ограничения

1 ≤ N ≤ 40

Описание системы оценивания

Баллы начисляются пропорционально количеству пройденных тестов.

По запросу сообщается количество набранных баллов.

Примеры тестов

1

9

2

21

Задача Z. Сумма с перестановкой ≡

Условие

Заданы три числа: a, b, c. Необходимо выяснить, существуют ли такие числа x и y, что:

1. x получается перестановкой цифр числа a;
2. y получается перестановкой цифр числа b;
3. x и y не содержат лидирующих нулей;
4. x + y = c.

Формат входного файла

Входной файл содержит целые числа a b c.

Формат выходного файла

Если искомые числа существуют, вывести в первую строку выходного файла слово YES, а во вторую — числа x y, разделённые пробелом. В противном случае вывести слово NO.

Ограничения

1 < a, b, c < 10⁹

Примеры тестов

12 31 25

YES
12 13

12 31 26

NO