Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Чат
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 
[Положение] [Расписание] [Архив] [Содержание] [Задачи] [Рейтинг]

Задачи олимпиады "Полуфинал XIII Всероссийской командной олимпиады школьников по программированию (Восточно-Сибирский регион)"

Задача A. Бисер

(Время: 1 сек. Память: 16 Мб Баллы: 100)

В шкатулке хранится разноцветный бисер (или бусины). Все бусины имеют одинаковую форму, размер и вес. Бусины могут быть одного из N различных цветов. В шкатулке много бусин каждого цвета.

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

Входные данные

Входной файл INPUT.TXT содержит одно натуральное число N - количество цветов бусин (1 ≤ N ≤ 109).

Выходные данные

В выходной файл OUTPUT.TXT выведите ответ на поставленную задачу.

Пример

INPUT.TXTOUTPUT.TXT
134

Задача B. Веревочный мост

(Время: 1 сек. Память: 16 Мб Баллы: 100)

Однажды N путешественников решили ночью пересечь по веревочному мосту быструю горную речку. Без освещения перейти мост невозможно. К счастью, у одного из них оказался с собой фонарик. Известно, что мост выдерживает только двоих, а скорости людей могут различаться. Если мост пересекают два человека с разной скоростью, то они вынуждены двигаться со скоростью самого медленного из них. Скорость движения каждого из путников известна.

Помогите путешественникам как можно быстрее перебраться через мост. Требуется написать программу, определяющую минимальное время, которое потребуется для такого перехода. Например, если N=4, а время, требуемое для перехода по мосту для каждого, составляет 5, 10, 20 и 25 минут соответственно, то наименьшее время, требуемое для пересечения моста, составит ровно 60 минут.

Входные данные

В первой строке входного файла INPUT.TXT содержится натуральное число N – количество путешественников (N ≤ 105). Во второй строке располагаются N натуральных чисел – скорости всех путников, разделенные пробелом и не превосходящие 106. Здесь под скоростью человека понимается время в минутах, необходимое для перехода через мост.

Выходные данные

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

Примеры

INPUT.TXTOUTPUT.TXT
12
10 20
20
24
5 10 20 25
60

Задача C. Crimsonland

(Время: 8 сек. Память: 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.TXTOUTPUT.TXT
14 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» (без кавычек).

Примеры

INPUT.TXTOUTPUT.TXT
1 3
vtz ud xnm xugm itr pyy jttk gmv xt otgm xt xnm puk ti xnm fprxq
xnm ceuob lrtzv ita hegfd tsmr xnm ypwq ktj
frtjrpgguvj otvxmdxd prm iev prmvx xnmq
now is the time for all good men to come to the aid of the party
the quick brown fox jumps over the lazy dog
programming contests are fun arent they
2 3
vtz ud xnm xugm itr pyy jttk gmv xt otgm xt xnm puk ti xnm fprxq
xnm fffff lrtzv iia wwwfd tsmr xnm ypwq ktj
frtjrpgguvj otvxmdxd prm iev prmvx xnmq
No solution

Задача E. Функция - 2

(Время: 1 сек. Память: 16 Мб Баллы: 100)

Описана рекурсивная функции с тремя параметрами 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.TXTOUTPUT.TXT
11 1 12
22 2 24
310 4 6523
450 50 501048576

Задача F. Мышка

(Время: 1 сек. Память: 16 Мб Баллы: 100)

Однажды компьютерная мышка подумала, что стоит взять про запас еще один коврик. Чтобы никто не заметил запасного коврика, мышка решила его спрятать под свой прямоугольный коврик. Пробравшись ночью на склад, мышка обнаружила там только круглые коврики. Удастся ли мышке спрятать круглый коврик под прямоугольным ковриком?

Входные данные

Входной файл INPUT.TXT содержит три натуральных числа: W, H и R, где W и H - ширина и высота прямоугольного коврика, а R – радиус запасного коврика. Все числа не превосходят значения 109.

Выходные данные

В выходной файл OUTPUT.TXT выведите «YES», если новый коврик можно спрятать под старым, и слово «NO», если этого сделать нельзя.

Примеры

INPUT.TXTOUTPUT.TXT
14 7 2YES
24 7 3NO

Задача G. Число - 3

(Время: 1 сек. Память: 16 Мб Баллы: 100)

Дано натуральное число N. Над ним можно произвести следующий набор операций:

  • вычитать единицу;
  • делить на три, если число кратно трем;
  • делить на два, если число четное.

После выполнения одной из операций к полученному результату также можно применить указанные операции, и делается это до тех пор, пока результат не окажется равным 1.

Входные данные

Входной файл INPUT.TXT содержит натуральное число N (N ≤ 106).

Выходные данные

В выходной файл OUTPUT.TXT выведите наименьшее количество операций, в результате выполнения которых будет получена единица.

Примеры

INPUT.TXTOUTPUT.TXT
153
210
3103

Задача H. Морской бой - 3

(Время: 2 сек. Память: 32 Мб Баллы: 100)

Всем известна увлекательная игра «Морской бой». Сейчас играть в морской бой можно не только с соседом по парте, но и с компьютером. Игра c компьютером ведется на прямоугольном поле произвольных размеров N×M, где N - количество строк, M - количество столбцов. Приближается чемпионат Мира по морскому бою. Планируется вести его трансляцию в режиме реального времени: демонстрировать карту с кораблями и выводить статистику: количество целых, подбитых и уничтоженных кораблей, находящихся на поле. Требуется написать программу для подсчета статистики.

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

Входные данные

Первая строка входного файла INPUT.TXT содержит два целых числа N и M (1≤ N,M ≤ 103), разделённых пробелами - размеры игрового поля. Далее идут N строк по M символов - описание игрового поля.

Английская буква 'X' обозначает подбитую клетку корабля, 'S' - не подбитую клетка корабля, '-' – свободное водное пространство.

Выходные данные

В выходной файл OUTPUT.TXT выведите через пробел три числа:

  • количество целых кораблей
  • количество подбитых кораблей
  • количество уничтоженных кораблей

Пример

INPUT.TXTOUTPUT.TXT
1 3 8
---SSS--
XX--S-X-
X-S---S-
2 1 1

Задача I. Последовательность - 4

(Время: 1 сек. Память: 16 Мб Баллы: 100)

Бесконечная числовая последовательность задана с помощью формулы ее k-го члена:

        Ak = k!*2k, где k = 1, 2, 3,...

Найти сумму N первых членов этой последовательности. Так как найденная сумма может быть очень большой, выведите ее по модулю M.

Входные данные

Входной файл INPUT.TXT содержит два целых числа N - количество членов последовательности (1 ≤ N ≤ 104) и M - модуль (2 ≤ M ≤ 109).

Выходные данные

В выходной файл OUTPUT.TXT выведите сумму N первых членов последовательности по модулю M.

Примеры

INPUT.TXTOUTPUT.TXT
15 102
210000 20
3100 1000000000909349562


Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483