Задача A. Самый сложный вопрос ≡

Условие

Один вопрос в части A на ЕГЭ был очень сложным, и никто из школьников не знал точного ответа на него. Однако некоторые школьники знали, какой ответ точно неправильный. После экзамена они собрались, чтобы выяснить, какой же правильный ответ на этот вопрос.

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

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

Входной файл содержит целое число N, за которым следуют N целых чисел от 1 до 4 — догадки школьников.

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

Требуется вывести в выходной файл список возможных вариантов ответа в порядке возрастания.

Ограничения

1 ≤ N ≤ 100.

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

5
1 2 3 1 2

4

4
1 4 1 1

2 3

Задача B. Деревья ≡

Условие

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

Даны значения высот N деревьев аллеи. Требуется найти два дерева, сумма высот которых максимальна и при этом расстояние между ними не меньше d. Расстояние — это разница порядковых номеров деревьев.

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

Входной файл содержит целые числа N d, за которым следуют N целых чисел a_i — высоты деревьев.

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

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

Ограничения

2 ≤ N ≤ 100000.

1 ≤ d ≤ N−1.

1 ≤ a_i ≤ 10⁹.

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

7 4
3 4 5 6 7 1 2

10

5 3
1 2 3 4 1

5

Задача C. Косточки для собак ≡

Условие

Однажды стая из N собак нашла M косточек. Теперь собаки хотят поделить косточки между собой. В стае действует безоговорочное правило: если одна собака старше другой, то она должна получить не меньше косточек, чем младшая.

Сколько существует способов распределить косточки между собаками, чтобы каждая собака получила хотя бы одну кость?

Например, если собак 2, а косточек 4, то существует 2 способа: либо младшей 1 кость, а старшей 3, либо младшей и старшей по 2 кости.

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

Входной файл содержит целые числа N M.

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

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

Ограничения

1 ≤ N ≤ M ≤ 50.

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

2 4

2

3 6

3

Задача D. Годы летят ≡

Условие

В пожилом возрасте Марфа Геннадьевна совершила прыжок с парашютом. Как говорится, годы летят...

Когда Марфа Геннадьевна уже приземлилась, она как опытный физик и математик решила вычислить, сколько времени она летела до раскрытия парашюта. Для простоты Марфа Геннадьевна приняла силу сопротивления воздуха пропорциональной скорости: . После несложных вычислений Марфа Геннадьевна получила формулу, выражающую зависимость высоты от времени:

Здесь , где e = 2.71828... — постоянная Эйлера, H — начальная высота, g = 9.8 м/с² — ускорение свободного падения, m — масса Марфы Геннадьевны. Марфа Геннадьевна пренебрегла начальной горизонтальной скоростью за счет движения самолета и приняла начальную вертикальную скорость равной 0.

Требуется определить, через какое время Марфа Геннадьевна достигла высоты h_*, на которой она раскрыла парашют.

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

Входной файл содержит вещественные числа H h_*  m k.

H и h_* заданы в км, m в кг, k в кг/с.

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

Требуется вывести в выходной файл единственное вещественное число — время до раскрытия парашюта в секундах по меньшей мере с 3-мя точными знаками после запятой.

Ограничения

2 ≤ H ≤ 100, 1 ≤ h_* ≤ H.

50 ≤ m ≤ 150.

0.1 ≤ k ≤ 10.

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

3 1.5 85 1

18.1178

20 12 92 0.5

41.9407

Задача E. Набор сотрудников ≡

Условие

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

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

Вася дал объявление о наборе сотрудников в каждый отдел и сейчас он имеет на руках список желающих. Каждый желающий указал, в какой отдел он хочет идти работать, либо указал, что готов работать в любом отделе. Тем не менее, Вася может нанять любого желающего только в один из отделов.

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

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

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

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

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

Вторая строка содержит N целых чисел a_i  — полезность желающего с номером i.

Третья строка содержит N целых чисел d_i, имеющих значения 1,2 либо 0  — 1, если i-й желающий хочет работать в первом отделе, 2  — во втором, либо 0  — в обоих.

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

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

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

Если существует несколько решений, выведите любое из них.

Ограничения

1 ≤ N, M, K ≤ 100000.

1 ≤ a_i ≤ 10⁴.

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

1 1 1
123
1

1 1
0

2 1 1
123 145
1 1

1 2
0