Задача A. Счастливые цифры ≡

Условие

Школьнику Васе нравятся числа, которые заканчиваются счастливыми для него цифрами k. Поэтому каждый раз, когда он видит какое-нибудь натуральное число n, он сразу пытается подобрать такое d (d ≤ 2), что число n в системе счисления с основанием d заканчивается как можно большим количеством цифр k.

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

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

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

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

В выходной файл выведите два числа: d - искомое основание системы счисления и l — количество цифр k, которым заканчивается запись числа n в этой системе счисления. Если искомых d несколько, выведите любое из них, не превосходящее 10¹² (такое всегда существует).

Комментарии к примерам:

1. 49₁₀ = 1211₃.
2. Ни в одной системе счисления 7 не заканчивается на цифру 5.

Ограничения

1 ≤ n ≤ 10¹¹

0 ≤ k ≤ 9

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

49 1

3 2

7 5

3 0

Задача B. Сочи-2014 ≡

Условие

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

В строительстве объектов готовы участвовать K фирм. Фирмы имеют разные строительные мощности, выраженные в количестве денежных средств, которые фирма может осваивать в единицу времени.

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

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

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

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

Первая строка входного файла содержит целое число N - количество объектов. Во второй строке содержатся разделенные пробелами целочисленные значения S₁, S₂, S₃, …, S_N объемов денежных средств, выделяемых для строительства каждого из объектов.

В третьей строке находится целое число K — количество строительных фирм. Четвертая строка содержит разделенные пробелами целочисленные значения мощностей каждой из фирм V₁, V₂, V₃, …, V_K в тыс.руб/час.

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

Первая строка выходного файла содержит действительное число T — время в часах окончания всех работ, считая с начала строительства, выведенное не менее чем с тремя точными знаками после запятой. Далее в каждой строке выходного файла содержатся разделенные пробелами три числа: t, i, j, где действительное число t - время от начала строительства в часах, в которое j-я фирма приступает к строительным работам на i-м объекте.

Значения времен необходимо выводить с максимально возможной точностью.

Строки должны быть отсортированы по неубыванию t.

Ограничения

1 ≤ N ≤ 50

1 ≤ K ≤ 50

Числа S_i выражены в тысячах рублей, положительные и не превышают 1000.

Числа V_j положительные и не превышают 1000.

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

2
24 20
2
3 2

8.800
0 1 1
0 2 2
6.4000000 1 2
6.4000000 2 1

3
100 100 100
4
5 5 10 10

12.00000
0 1 3
0 2 4
0 3 1
4 2 2
4 3 4
8 1 1
8 3 4
8 2 3

Задача C. Тапкодер ≡

Условие

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

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

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

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

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

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

В первой строке входного файла заданы три целых числа k, n и m. В следующих n строках описаны n пар участников, которые договорились между собой о том, что первый из двух участников пары выиграет встречу, если она состоится. Гарантируется, что каждая пара участников присутствует во входных данных не более одного раза, при этом, если задана пара x y, то пары y x быть не может, кроме того, x ≠ y. В последней строке файла перечислены номера участников, желающих работать в Тапкодере, в порядке возрастания их номеров. Все номера претендентов на работу различны.

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

Выходной файл должен содержать m целых чисел - максимальные номера туров, до которых могут дойти соответствующие претенденты на работу. Туры нумеруются от 1 до k.

Комментарии к примерам:

1. У каждого из участников есть возможность выйти в финал, так как договорных матчей нет.
2. Если четвертый участник выиграет у третьего, то договорная встреча первого и третьего не состоится, что благоприятно для первого.
3. Первому участнику благоприятно во втором туре играть с третьим, а не с четвертым, в свою очередь, четвертый может выиграть у третьего и также выйти в финал.

Ограничения

1 ≤ k ≤ 60

0 ≤ n ≤ 10⁵

1 ≤ m ≤ 10⁵

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

2 0 3
1 3 4

2 2 2

3 1 1
3 1
1

3

3 3 4
1 2
1 3
4 1
1 2 3 4

3 1 2 3