Задачи отборочных командных соревнований школьников 2009

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

Первая строка ввода содержит три целых числа – длина диагонали `D` (`1\ ≤\ D\ ≤\ 100`) требуемого монитора формата 4:3 и отношение сторон `W` и `H` (`1\ ≤\ H\ ≤\ W\ ≤\ 100`) у мониторов, производимых на Саракше.

Вывести одно вещественное число – диагональ монитора формата `W`:`H`, площадь которого совпадает с требуемой, с точностью `10^{-6}`.

17 16 9

18.017862

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

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

Первая строка ввода содержит одно целое число – количество шкатулок `N` (`1\ <\ N\ ≤\ 1000`). Далее следует `N` строк, каждая строка содержат по три целых числа в диапазоне от 1 до 1000 – длины ребер шкатулки в произвольном порядке.

В первой строке вывести одно целое число `K` – максимальное количество вложенных шкатулок. В следующей строке вывести `K` целых чисел – номера шкатулок, начиная с самой внутренней. Если возможно несколько вариантов, то можно вывести любой из них.

3
10 15 40
20 30 10
15 5 20

2
3 2

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

Напишите программу, которая поможет Максиму определить, какие сообщения можно отправить с помощью оставшихся на клавиатуре клавиш, а какие – нет.

Первая строка ввода содержит непустой набор из прописных латинских букв – неработающие клавиши. Вторая строка содержит одно целое число `N` (`1\ ≤\ N\ ≤\ 100`) – количество сообщений, которые хочет отправить Максим. Далее следует `N` непустых строк длиной не более 100 символов, содержащих только латинские буквы, пробелы и знаки препинания – отправляемые сообщения.

Вывести `N` строк. Если `i`-е сообщение можно отправить с помощью оставшихся клавиш, то вывести в `i`-й строке yes, иначе – no.

QYFJX
2
Oma, Ich habe nicht die Uhr geklaut.
Das Raumschiff ist kaputt. Hilfe ist notwendig.

yes
no

Изучая город, Максим посетил несколько раз казино. Первые два вечера Максим в основном наблюдал за действиями других игроков. На второй вечер Максим обратил внимание, что последовательность результатов ставок в одном из игровых автоматов совпадает с той, которую он увидел в первый вечер. Очевидно, что этот автомат из-за какой-то поломки каждый раз после включения генерировал одну и ту же последовательность выигрышей и проигрышей. Заметить эту особенность автомата мог только обладающий феноменальной памятью землянин. Чтобы не привлекать внимания охраны казино, Максим решил использовать этот автомат только один раз, сделав несколько ставок подряд.

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

Первая строка ввода содержит число `N` (`1\ ≤\ N\ ≤\ 10^5`) – количество результатов ставок, которые запомнил Максим. Во второй строке `N` целых чисел в диапазоне от `-100` до `100` – результаты ставок. Отрицательное число означает проигрыш, положительное – выигрыш.

Вывести три целых числа – максимальный выигрыш, который может получить Максим, номер начальной ставки и их количество. Если существует несколько вариантов с одинаковым максимальным выигрышем, то вывести вариант с меньшим количеством ставок, а если таких вариантов несколько, то с меньшим начальным номером ставки. Если Максим не может выиграть, то вывести 0 0 0.

6
1 5 -8 10 2 -10

12 4 2

Южным границам страны угрожают мутанты. Время от времени из подземелья на границе появляются мутанты и движутся цепочкой один за другим строго на север. Для защиты границы была создана система башен, на которые были установлены управляемые операторами генераторы излучения, воздействующего на мутантов. Воздействие одного генератора может уничтожить мутанта за время `T`, совместное воздействие `k` генераторов – за время `T/k`. Излучение генераторов является узконаправленным и поэтому сила воздействия не меняется с расстоянием, но большая рефракция атмосферы на Саракше делает невозможным точное прицеливание на расстояние более `R`. Оператор начинает стрелять, как только первый мутант в цепочке попадает в радиус поражения его башни. После гибели мутанта или выхода его за пределы радиуса поражения башни оператор переносит воздействие генератора на следующего мутанта в цепочке, если он уже в зоне действия башни, или ожидает, когда он приблизится на расстояние не более `R`, и тогда оператор снова начинает стрелять.

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

Первая строка ввода содержит шесть целых чисел - количество башен `K` (`1\ ≤\ K\ ≤\ 10`), радиус поражения башен `R` (`1\ ≤\ R\ ≤\ 1000`), время необходимого воздействия одного генератора для гибели мутанта `T` (`1\ ≤\ T\ ≤\ 100`), количество мутантов `M` (`1\ ≤\ M\ ≤\ 100`), расстояние между мутантами в цепочке `D` (`1\ ≤\ D\ ≤\ 100`) и интервал времени между появлениями мутантов из подземелья `F` (`1\ ≤\ F\ ≤\ 100`). Далее следует `K` строк, каждая строка содержит два целых числа `X_i` и `Y_i` (`0\ <\ X_i,\ Y_i\ <\ 10000`) – координаты башен.

В первой строке вывести сообщение yes, если мутантов удастся остановить, во второй строке вывести одно вещественное число с точностью `10^{-6}` – максимальное расстояние, на которое мутанты смогли пройти вглубь страны. Если мутанты смогут прорваться через защиту, то вывести в первой строке сообщение no, а во второй строке вывести одно целое число – количество прорвавшихся через защиту мутантов.

2 100 10 5 1 1
1 1
1 2

yes
21.000000

На северных границах страны тоже не всё благополучно. Хонтийцы планируют напасть на страну, и необходимо опередить их. Для рекогносцировки в каждый из `N` хонтийских городов был послан разведчик, и каждый из них сообщил о количестве дорог, ведущих из разведываемого города в другие города Хонти. Было известно, что 1) по системе дорог Хонти можно попасть из любого города в любой другой, при этом не меняя дорогу в местах их пересечений; 2) каждая дорога связывает ровно два города; 3) между двумя городами не более одной дороги; 4) нет дорог, ведущих из города в тот же самый город; 5) по всем дорогам можно ехать в обоих направлениях.

Напишите программу, которая определяет, можно ли построить по донесениям разведчиков карту дорог в Хонти, соответствующую вышеперечисленным условиям.

Первая строка ввода содержит одно целое число - количество городов `N` (`1\ ≤\ N\ ≤\ 1000`). Вторая строка ввода содержит `N` целых чисел в диапазоне от 0 до 1000 – `i`-е число в строке означает количество дорог из `i`-го города (`1\ ≤\ i\ ≤\ N`).

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

3
1 2 1

yes

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

Напишите программу, которая определяет количество номеров в диапазоне от `A` до `B` включительно, содержащих "счастливое" число `N`.

Первая строка ввода содержит три целых числа – границы диапазона выданных за год номеров `A` и `B` (`1\ ≤\ A\ ≤\ B\ ≤\ 10^18`) и "счастливое" число `N` (`0\ ≤\ N\ ≤\ 999`).

Вывести одно целое число – количество номеров в диапазоне от `A` до `B` включительно, содержащих "счастливое" число `N`.

1000 2000 33

19

Полицейские на Саракше проверяют состояние водителей, требуя их назвать числа по порядку от `A` до `B`. Если `A` меньше или равно `B`, числа нужно называть в возрастающем порядке, иначе – в убывающем. Чтобы убедиться, что водитель, называя числа, не ошибся, полицейским необходимо знать правильный порядок, в котором должны называться числа.

Напишите программу, которая выводит последовательность чисел от `A` до `B` по порядку.

Первая строка ввода содержит два целых числа - названные полицейским числа `A` и `B` (`1\ ≤\ A,\ B\ ≤\ 100`).

Вывести числа от `A` до `B` включительно, каждое число на отдельной строке.

5 8

5
6
7
8

10 7

10
9
8
7

Начинающий автомобилист Фанк боится делать левые повороты. Он хочет найти найти компромисс между временем поездки и её опасностью. Фанк разделил карту города на клетки, каждая из которых содержит небольшой прямой участок дороги, перекресток или бездорожье. В клетку с дорогой, ведущей с севера на юг, можно попасть только из клеток, расположенных выше или ниже, и выехать только вниз или вверх без смены направления движения. Аналогично для клетки с дорогой, ведущей с запада на восток, но допустимыми будут только клетки слева и справа. В клетку с перекрестком можно попасть из любой соседней клетки (сверху, снизу, слева и справа) и можно выехать также в любую соседнюю клетку, если такое перемещение является допустимым для соседней клетки. В клетку без дороги перемещаться нельзя. Перемещение из клетки с дорогой или перекрестком без поворота в соседнюю клетку Фанк оценил в `A` баллов, перемещение из клетки с перекрестком в соседнюю клетку справа по направлению движения с соответствующим изменением направления движения – в `B` баллов, слева – в `C` баллов, а противоположную направлению движения – в `D` баллов.

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

Первая строка ввода содержит шесть целых чисел - размеры города `N` и `M` (`2\ ≤\ N,\ M\ ≤\ 100`) и оценки сложности маневров для автомобилиста `A`, `B`, `C` и `D` (`1\ ≤\ A\ ≤\ B\ ≤\ C\ ≤\ D\ ≤\ 100`). Далее следует `N` строк, содержащих по `M` символов – карта города, разделенная на клетки. Символ '#' означает часть города без дорог, символ '+' – перекресток, символ '|' – дорогу с двухсторонним движением с севера на юг, '-' – дорогу с двухсторонним движением с запада на восток. Далее следует две строки, содержащих начальную и конечную позицию автомобиля и направление его движения в формате `r\ c\ d` (`1\ ≤\ r\ ≤\ N`, `1\ ≤\ c\ ≤\ M`, `d` – символ '<', '>', '^' или 'v', означающий направление движения влево, вправо, вверх или вниз соответственно). Начальная и конечная позиция автомобиля расположены на дороге или перекрестке. Верхний левый угол карты имеет координаты (1,1), правый нижний – координаты (`N,\ M`). Гарантируется, что существует по крайней мере один способ проезда из начального положения автомобиля в конечное.

Вывести одно целое число – минимальную сложность проезда.

3 3 1 2 3 3
+-+
|#|
+-+
2 1 v
1 2 <

11

Страннику необходимо определить, каким образом можно установить уличные фонари на проспекте Неизвестных Отцов, застроенного одинаковыми типовыми домиками. Дома стоят с одной стороны проспекта и имеют последовательные номера с `A` до `B`. Обитатели Саракша имеют особое "счастливое" число `N` для всех работ, связанных с электричеством. Поэтому на проспекте нужно установить ровно `N` фонарей, каждый фонарь нужно установить у одного из домов, на равном расстоянии друг от друга, сумма номеров домов, у которых стоят фонари, должна без остатка делиться на `N`. Пусть дома на проспекте имеют номера от 1 до 10, и "счастливым" является число 4. Можно поставить фонари у домов 1, 4, 7 и 10, но сумма номеров этих домов (равная 22) не будет делиться на 4. Условиям соответствуют только следующие 4 способа: 1-3-5-7, 2-4-6-8, 3-5-7-9 и 4-6-8-10.

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

Первая строка ввода содержит три целых числа - номера первого и последнего дома на проспекте `A` и `B` (`1 ≤\ A\ ≤\ B\ ≤\ 10^9`) и "счастливое" число `N` (`1\ ≤\ N\ ≤\ 10^9`).

Вывести одно целое число – количество способов провести освещение на проспекте.

1 10 4

4