Задачи олимпиады "Полуфинал XIII Всероссийской командной олимпиады школьников по программированию (Восточно-Сибирский регион)"
Задача A. Бисер
(Время: 1 сек. Память: 16 Мб Баллы: 100)
В шкатулке хранится разноцветный бисер (или бусины). Все бусины имеют одинаковую форму, размер и вес. Бусины могут быть одного из N различных цветов. В шкатулке много бусин каждого цвета.
Требуется определить минимальное число бусин, которые можно не глядя вытащить из шкатулки так, чтобы среди них гарантированно были две бусины одного цвета.
Входные данные
Входной файл INPUT.TXT содержит одно натуральное число N - количество цветов бусин (1 ≤ N ≤ 109).
Выходные данные
В выходной файл OUTPUT.TXT выведите ответ на поставленную задачу.
Пример
№
INPUT.TXT
OUTPUT.TXT
1
3
4
Задача B. Веревочный мост
(Время: 1 сек. Память: 16 Мб Баллы: 100)
Однажды N путешественников решили ночью пересечь по веревочному мосту быструю горную речку. Без освещения перейти мост невозможно. К счастью, у одного из них оказался с собой фонарик. Известно, что мост выдерживает только двоих, а скорости людей могут различаться. Если мост пересекают два человека с разной скоростью, то они вынуждены двигаться со скоростью самого медленного из них. Скорость движения каждого из путников известна.
Помогите путешественникам как можно быстрее перебраться через мост. Требуется написать программу, определяющую минимальное время, которое потребуется для такого перехода. Например, если N=4, а время, требуемое для перехода по мосту для каждого, составляет 5, 10, 20 и 25 минут соответственно, то наименьшее время, требуемое для пересечения моста, составит ровно 60 минут.
Входные данные
В первой строке входного файла INPUT.TXT содержится натуральное число N – количество путешественников (N ≤ 105). Во второй строке располагаются N натуральных чисел – скорости всех путников, разделенные пробелом и не превосходящие 106. Здесь под скоростью человека понимается время в минутах, необходимое для перехода через мост.
Выходные данные
В выходной файл OUTPUT.TXT выведите одно целое число – минимально возможное время, необходимое путникам для пересечения моста.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
2 10 20
20
2
4 5 10 20 25
60
Задача C. Crimsonland
(Время: 1 сек. Память: 16 Мб Баллы: 100)
Гриша третий день играет в Crimsonland, он «застрял» на самом сложном уровне: Panic Rush, так как ему постоянно не хватает боеприпасов.
На уровне Panic Rush есть несколько особенностей. Персонаж Гриши вооружён плазменным дробовиком с углом атаки α и неограниченной дальностью. Все монстры, попадающие в угол атаки, при выстреле тут же погибают. Дробовик достаточно тяжёлый, переносить его нельзя, но можно быстро поворачивать вокруг своей оси на любой угол. Монстры появляются все одновременно в произвольных точках карты, при этом их местоположение не совпадает с местоположением персонажа.
Гриша нашел в интернете чит-код, и теперь он знает, где появятся монстры и какой будет угол атаки дробовика. Помогите Грише подсчитать минимальное количество выстрелов, необходимых для отражения атаки.
Входные данные
Первая строка входного файла INPUT.TXT содержит два целых числа N и α, где N (1 ≤ N ≤ 104) — количество монстров, а α (1 ≤ α ≤ 180) — угол атаки дробовика в градусах. В следующей строке указано местоположение персонажа X0 и Y0, затем в N строках описаны координаты появления монстров Xi и Yi (все координаты — целые числа, не превосходящие по модулю 104).
Выходные данные
В выходной файл OUTPUT.TXT выведите наименьшее количество выстрелов, необходимых для отражения атаки.
Пример
№
INPUT.TXT
OUTPUT.TXT
1
4 90
1 1
2 2
0 2
0 0
2 0
2
Задача D. Криптограмма
(Время: 1 сек. Память: 16 Мб Баллы: 100)
На одной из лекций по информатике студент Петя узнал про новый шифр - простой замены. Он и на самом деле прост: в тексте каждая буква алфавита заменяется некоторой другой буквой того же алфавита (может быть, той же самой).
Петя написал письмо своему другу Васе. Письмо - это текст из нескольких строк, написанный на английском языке, с использованием только строчных английских букв и пробелов. В произвольное место, отдельной строкой Петя вставил ключевую фразу: "the quick brown fox jumps over the lazy dog", о которой они с Васей договорились заранее. После чего зашифровал письмо. Известно, что пробелы в письме не шифруются. Получив такое письмо, Вася сумеет его расшифровать и прочесть. Иногда Петя ошибается, и забывает вставить ключевую фразу. Увы, в этом случае прочесть письмо невозможно.
Так как процесс расшифровки трудоемок, Вася просит написать программу, с помощью которой он сможет быстро расшифровывать письмо от Пети.
Входные данные
Первая строка входного файла INPUT.TXT содержит целое число N – количество строк в письме (1 ≤ N ≤ 200). Далее идет N строк письма (пустые строки отсутствуют, в каждой строке не более 80 символов).
Выходные данные
В выходной файл OUTPUT.TXT в случае присутствия в тексте ключевой фразы выведите N строк расшифрованного сообщения. Если ключевой фразы нет, следует вывести «No solution» (без кавычек). Гарантируется, что есть не более одного способа расшифровки текста из входных данных.
Описана рекурсивная функция с тремя параметрами F(a, b, c):
если a ≤ 0 или b ≤ 0 или c ≤ 0, то F(a, b, c) = 1
если a > 20 или b > 20 или c > 20, то F(a, b, c) = F(20, 20, 20)
если a < b и b < c, то F(a, b, c) = F(a, b, c-1) + F(a, b-1, c-1) - F(a, b-1, c)
иначе F(a, b, c) = F(a-1, b, c) + F(a-1, b-1, c) + F(a-1, b, c-1) - F(a-1, b-1, c-1)
Однако, если указанную функцию реализовать напрямую, то даже для небольших значений a, b и c (например, a = 15, b = 15, c = 15), программа будет работать несколько часов!
Необходимо реализовать эффективный алгоритм вычисления функции F, который успеет найти любое ее значение менее чем за одну секунду!
Входные данные
Входной файл INPUT.TXT содержит три целых числа a, b, c - параметры функции F (-104 ≤ a,b,c ≤ 104).
Выходные данные
В выходной файл OUTPUT.TXT выведите значение функции F(a, b, c).
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
1 1 1
2
2
2 2 2
4
3
10 4 6
523
4
50 50 50
1048576
Задача F. Мышка
(Время: 1 сек. Память: 16 Мб Баллы: 100)
Однажды компьютерная мышка подумала, что стоит взять про запас еще один коврик. Чтобы никто не заметил запасного коврика, мышка решила его спрятать под свой прямоугольный коврик. Пробравшись ночью на склад, мышка обнаружила там только круглые коврики. Удастся ли мышке спрятать круглый коврик под прямоугольным ковриком?
Входные данные
Первая строка входного файла INPUT.TXT содержит три натуральных числа через пробел: W, H и R, где W и H - ширина и высота прямоугольного коврика, а R – радиус запасного коврика. Все числа не превосходят значения 109.
Выходные данные
В выходной файл OUTPUT.TXT выведите «YES», если новый коврик можно спрятать под старым, и слово «NO», если этого сделать нельзя.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
4 7 2
YES
2
4 7 3
NO
Задача G. Число - 3
(Время: 2 сек. Память: 64 Мб Баллы: 100)
Дано натуральное число N. Над ним можно произвести следующий набор операций:
вычитать единицу;
делить на три, если число кратно трем;
делить на два, если число четное.
После выполнения одной из операций к полученному результату также можно применить указанные операции, и делается это до тех пор, пока результат не окажется равным 1.
Входные данные
Входной файл INPUT.TXT содержит натуральное число N (N ≤ 106).
Выходные данные
В выходной файл OUTPUT.TXT выведите наименьшее количество операций, в результате выполнения которых будет получена единица.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
5
3
2
1
0
3
10
3
Задача H. Морской бой - 3
(Время: 2 сек. Память: 32 Мб Баллы: 100)
Всем известна увлекательная игра «Морской бой». Сейчас играть в морской бой можно не только с соседом по парте, но и с компьютером. Игра c компьютером ведется на прямоугольном поле произвольных размеров N×M, где N - количество строк, M - количество столбцов. Приближается чемпионат Мира по морскому бою. Планируется вести его трансляцию в режиме реального времени: демонстрировать карту с кораблями и выводить статистику: количество целых, подбитых и уничтоженных кораблей, находящихся на поле. Требуется написать программу для подсчета статистики.
Корабль на поле — это связанная фигура, стоящая из одной или нескольких рядом лежащих клеток, имеющих общую сторону. Корабли могут быть абсолютно любых форм и размеров!
Входные данные
Первая строка входного файла INPUT.TXT содержит два целых числа N и M (1≤ N,M ≤ 103), разделённых пробелами - размеры игрового поля. Далее идут N строк по M символов - описание игрового поля.
