Задача 1. Счастливые цифры
Имя входного файла:
lucky.in
Имя выходного файла:
lucky.out
Ограничение по времени:
2 секунды
Ограничение по памяти:
64 мегабайта
Максимальная оценка
100 баллов
Школьнику Васе нравятся числа, которые заканчиваются счастливыми для него цифрами k. Поэтому каждый раз, когда он видит какое-нибудь натуральное число n, он сразу пытается подобрать такое d (d ? 2), что число n в системе счисления с основанием d заканчивается как можно большим количеством цифр k.
Требуется написать программу, которая по заданным числам n и k найдет такое d, чтобы число n в системе счисления с основанием d заканчивалось как можно большим количеством цифр k.
Формат входных данных
Входной файл содержит два целых десятичных числа n и k (1 ? n ? 1011; 0 ? k ? 9).
Формат выходных данных
В выходной файл выведите два числа: d — искомое основание системы счисления и l —количество цифр k, которым заканчивается запись числа n в этой системе счисления. Если искомых d несколько, выведите любое из них, не превосходящее 1012 (такое всегда существует).
Примеры
комментарий
49 1
3 2
4910 = 12113
7 5
3 0
Ни в одной системе счисления 7 не заканчивается на цифру 5
Задача 2. Тапкодер
topcoder.in
topcoder.out
Ассоциация Тапкодер организует Всемирное парное соревнование сильнейших программистов. К участию в соревновании допущены первые 2k зарегистрировавшихся участников, которым присвоены номера от 1 до 2k.
Соревнование будет проходить по олимпийской системе. В первом туре первый участник встречается со вторым, третий с четвертым и так далее. В каждой паре победителем становится участник, первым решивший предложенную задачу, при этом ничьих не бывает. Все победители очередного тура и только они являются участниками следующего тура. В каждом туре пары составляются из участников в порядке возрастания присвоенных им номеров. Соревнование продолжается до тех пор, пока не останется один победитель.
Организаторам стало известно, что некоторые пары участников заранее договорились о результате встречи между собой, если такая встреча состоится. Для всех остальных встреч, кроме n договорных, возможен любой исход.
Некоторые m участников соревнования представили свои резюме в ассоциацию Тапкодер с целью поступления на работу. Организаторов интересует, до какого тура может дойти каждый из претендентов при наиболее благоприятном для него стечении обстоятельств. При этом для каждого участника в отдельности считается, что все недоговорные встречи, в том числе те, в которых он не участвует, закончатся так, как ему выгодно, а все состоявшиеся договорные встречи закончатся в соответствии с имеющимися договоренностями.
Требуется написать программу, которая для каждого из претендентов определяет максимальный номер тура, в котором он может участвовать.
В первой строке входного файла заданы три целых числа k (1 ? k ? 60), n (0 ? n ? 100 000) и m (1 ? m ? 100 000). В следующих n строках описаны n пар участников, которые договорились между собой о том, что первый из двух участников пары выиграет встречу, если она состоится. Гарантируется, что каждая пара участников присутствует во входных данных не более одного раза, при этом, если задана пара x y, то пары y x быть не может, кроме того, x ? y. В последней строке файла перечислены номера участников, желающих работать в Тапкодере, в порядке возрастания их номеров. Все номера претендентов на работу различны.
Выходной файл должен содержать m целых чисел — максимальные номера туров, до которых могут дойти соответствующие претенденты на работу. Туры нумеруются от 1 до k.
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
Первому участнику благоприятно во втором туре играть с третьим, а не с четвертым, в свою очередь, четвертый может выиграть у третьего и также выйти в финал
Задача 2. Сочи-2014
olymp.in
olymp.out
К предстоящей олимпиаде в Сочи требуется возвести N олимпийских объектов. Процесс строительства каждого объекта определяется освоением выделяемых на него денежных средств.
В строительстве объектов готовы участвовать K фирм. Фирмы имеют разные строительные мощности, выраженные в количестве денежных средств, которые фирма может осваивать в единицу времени.
В каждый момент времени фирма может осуществлять работы только на одном объекте. В строительстве одного объекта не могут одновременно участвовать несколько фирм. В любой момент времени любой объект может быть передан для продолжения строительства любой фирме.
Администрация строительства олимпийских объектов заинтересована в скорейшем освоении денежных средств, поэтому хочет составить такой график работ, при следовании которому строительство будет завершено в кратчайшие сроки. В графике будет указано время, в течение которого тот или иной объект будет строиться какой-то фирмой.
Напишите программу, результаты работы которой позволят администрации построить требуемый график.
Первая строка входного файла содержит целое число N — количество объектов (1 ? N ? 50). Во второй строке содержатся разделенные пробелами целочисленные значения S1, S2, S3, …, SN объемов денежных средств, выделяемых для строительства каждого из объектов. Числа Si выражены в тысячах рублей, положительные и не превышают 1000.
В третьей строке находится целое число K — количество строительных фирм (1 ? K ? 50). Четвертая строка содержит разделенные пробелами целочисленные значения мощностей каждой из фирм V1, V2, V3, …, VK в тыс.руб/час. Числа Vj положительные и не превышают 1000.
Первая строка выходного файла содержит действительное число T — время в часах окончания всех работ, считая с начала строительства, выведенное не менее чем с тремя точными знаками после запятой. Далее в каждой строке выходного файла содержатся разделенные пробелами три числа: t, i, j, где действительное число t — время от начала строительства в часах, в которое j-я фирма приступает к строительным работам на i-м объекте.
Значения времен необходимо выводить с максимально возможной точностью.
Строки должны быть отсортированы по неубыванию t.
2
24 20
8.800
0 1 1
0 2 2
6.4000000 1 2
6.4000000 2 1
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
Представьтесь*
Ваш комментарий*
