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

Условие

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

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

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

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

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

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

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

Первая строка входного файла содержит целые числа 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

Задача B. Горячий кофе ≡

Условие

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

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

В первой строке входного файла содержится два целых числа — n и p. Во второй строке записаны n целых чисел a₁, a₂, …, a_n, задающих время прихода каждого программиста на работу (время считается от начала рабочего дня в тех же единицах, в которых необходимо выдать ответ).

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

В выходной файл выведите единственное число — ответ к задаче.

Ограничения

2 ≤ n ≤ 10⁶;

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

3 2
0 30 10 

30

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

Условие

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

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

Здесь , где 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

Задача D. Восстановление сетки ≡

Условие

Турнир по олимпийской системе, состоящий из N раундов, проводятся между 2^N участниками по следующей схеме: сначала составляется последовательность из расставленных в произвольном порядке игроков. В первом раунде первый в последовательности участник соревнуется со вторым, третий с четвёртым, и т.д. Проигравшие выбывают из турнира, и на втором раунде победитель первой пары играет с победителем второй, победитель третьей с победителем четвёртой, и т.д. Наконец, после N-го раунда остаётся ровно один участник, который становится победителем турнира.

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

Назовём упорядоченной такую первоначальную последовательность участников, что в каждом матче сетки победителем оказывается первый участник. Например, первоначальная последовательность в приведённой справа сетке не соответствует этому условию — чтобы это исправить, нужно расположить участников в порядке: Life, MarineKing, TaeJa, Leenock, Mvp, Symbol, Rain, Hero.

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

Рекомендуется рассмотреть частичные решения

N ≤ 10;

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

Входной файла содержит целое число N, за которым следуют 2^N − 1 пар чисел W_i L_i, означающих, что участник с номером W_i победил участника с номером L_i. Участники пронумерованы от 1 до 2^N.

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

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

Ограничения

1 ≤ N ≤ 20

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

3
1 2  3 1  7 3
7 6  6 5  7 8  3 4

7 8 6 5 3 4 1 2 

Problem E. Ganking ≡

Statement

Popular on-line game "Attack Of The Moderns 3" is played by two teams of 5 players each. During the match, players run around the map and try to kill members of opposing team by attacking them with various weapons and magic spells. Killed players respawn after a certain period of time.

Players of the first team are numbered from 1 to 5, players of the second team are numbered from 6 to 10. All attacks are recorded by the game for statistics gathering. Each attack is described by values t, a, v, k, where t is a time in seconds since the game start, a — the number of the attacking player, v — the number of the player being attacked, k = 1 if this attack killed the victim and 0 otherwise.

Gank is an event when one or more players attack and kill a single opponent while his teammates are elsewhere and unable to help. Specifically: let G be a set of players who attacked the victim during the last T seconds of the game before the kill. A kill is counted as a gank, if in that period of time:

• the victim only attacked players from set G, and
• players from set G attacked and were attacked only by the victim.

Your program must, given the value of T and a sequence of N attack descriptions, count the number of ganks each player has participated in.

Input file format

Input file contains integers N T followed by N quartets of integers t_i a_i v_i k.

Output file format

Output file must contain 10 integers — the numbers of ganks for each player.

Constraints

1 ≤ N ≤ 10000, 1 ≤ t_i ≤ t_i+1 ≤ 10⁵, 1 ≤ T ≤ 10⁵. Either 1 ≤ a_i ≤ 5 < v_i ≤ 10 or 1 ≤ v_i ≤ 5 < a_i ≤ 10. Time between sequential kills of the same victim is greater than T.

Sample tests

7 4
1 1 6 0
2 2 6 0
5 3 6 1
10 7 1 1
10 7 2 1
20 8 1 1
20 3 7 1

0 1 2 0 0 0 0 1 0 0