Литература Русский язык Английский язык Математика Информатика Физика Химия Биология География История

Олимпиады по информатике: «Счастливые цифры», «Тапкодер», «Сочи-2014»

Задача 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 (такое всегда существует).

Примеры

lucky.in

lucky.out

комментарий

49 1

3 2

4910 = 12113

7 5

3 0

Ни в одной системе счисления 7 не заканчивается на цифру 5

 

Задача 2. Тапкодер

Имя входного файла:

topcoder.in

Имя выходного файла:

topcoder.out

Ограничение по времени:

2 секунды

Ограничение по памяти:

64 мегабайта

Максимальная оценка

100 баллов

Ассоциация Тапкодер организует Всемирное парное соревнование сильнейших программистов. К участию в соревновании допущены первые 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.

Примеры

topcoder.in

topcoder.out

комментарий

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

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

 

Задача 3. Сочи-2014

Имя входного файла:

olymp.in

Имя выходного файла:

olymp.out

Ограничение по времени:

2 секунды

Ограничение по памяти:

64 мегабайта

Максимальная оценка

100 баллов

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

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

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

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

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

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

Первая строка входного файла содержит целое число N — количество объектов (1 ? N ? 50). Во второй строке содержатся разделенные пробелами целочисленные значения S1S2, S3, …, SN объемов денежных средств, выделяемых для строительства каждого из объектов. Числа Si выражены в тысячах рублей, положительные и не превышают 1000.

В третьей строке находится целое число K — количество строительных фирм (1 ? K ? 50). Четвертая строка содержит разделенные пробелами целочисленные значения мощностей каждой из фирм V1, V2, V3, …, VK в тыс.руб/час. Числа Vj положительные и не превышают 1000.

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

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

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

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

Примеры

olymp.in

olymp.out

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

4807

Комментарии  

 
+2 Человечина 17 сентября 2014, 19:01
бля если такие вопросы будут по олимпиаде в моей школе я ж сдохну я ж не фига не понял что там написано тем более эта училка по информатике меня уже записала на олимпиаду хотя я тока в игры умею игратb XD лан прорвусь как нить
Ответить Ссылка
 
 
+1 iAlex 17 сентября 2014, 19:17
Красава :D
Ответить Ссылка
 
 
+1 Тема 3 апреля 2013, 11:09
Олимпиадные задания довольно сложные. Думаю, что это только на первый взгляд эти задания кажутся такими простыми. А на самом то деле что бы их решить нужно хорошо помучиться.
Ответить Ссылка
 
 
0 Skyfire 27 марта 2013, 8:55
В принципе задания не такие уж и сложные. Хотя думаю, что в такой олимпиаде участвует очень много умных детей и место какое то занять было бы очень сложно.
Ответить Ссылка
 
 
0 Rogue 22 марта 2013, 20:48
Вообще задания не сложные, главное подобрать подходящий алгоритм и оптимизировать его правильно, а кодинг проблем не составить, потому что программы небольшие
Ответить Ссылка
 
 
0 Portos 7 марта 2013, 0:43
Вот это интересная олимпиада, интересно сколько времени давали студентам для выполнения этих заданий, мне бы в 10 классе хватило бы где-то 3-4 часа на решение задач и их отладку
Ответить Ссылка
 
 
0 Pheonix 11 марта 2013, 19:10
Вообще стандартное время на любую олимпиаду 4 часа. Думаю, что и эта олимпиада исключением не стала. Задания действительно очень интересные, думаю, что я бы их и за 4 часа не решил бы.
Ответить Ссылка