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

В парке развлечений "Страна чудес Гудвина" много замечательных аттракционов. Учительница, которая возила детей в парк, решила выяснить насколько их много, и опросила детей, в каких аттракционах они были. Результаты опроса она записала, обозначая каждый названный аттракцион одной из букв латинского алфавита. Некоторые аттракционы дети назвали несколько раз, а про какие-то они, возможно, забыли, но учительнице достаточно определить, сколько различных аттракционов среди названных.

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

В первой строке ввода содержится одна строка длиной от 1 до 250 символов, состоящая из прописных латинских букв.

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

ABRACADABRA

5

В одной из палаток "Страны чудес Гудвина" артист, выдающий себя за экстрасенса, показывает следующее представление. "Экстрасенс" просит одного из зрителей задумать два целых числа `A` и `B` в диапазоне от 1 до 100. Затем зритель должен взять несколько чистых карточек и записать на первой карточке число `A`, на второй – число `A+B`, на третьей – число `A+2*B`, на `i`-ой – число `A+(i-1)*B` и т.д. После этого карточки перемешиваются, одна из карточек прячется, а остальные показываются "экстрасенсу". Увидев числа на карточках, артист, имеющий хорошую память, легко угадывает число на спрятанной карточке. В редких случаях для угадывания "экстрасенсу" требуется более одной попытки.

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

В первой строке ввода содержится одно целое число `N` (`3\ ≤\ N\ ≤\ 50`) – количество заполненных карточек. Во второй строке ввода содержится `(N-1)` целых положительных чисел, разделенных пробелами – числа на показанных карточках.

В первой строке вывести одно или более чисел в порядке возрастания, разделяя их пробелами – все варианты для числа на спрятанной карточке.

5
9 5 11 7

3 13

Для выступления гимнастов необходимо застелить площадку размером `N\ times\ M` метров циновками двух цветов. Циновки имеют размер `1\ times\ 1` метр. Циновками белого цвета выстилается внутренняя часть площадки, а по краю площадки полосой в 1 метр должны постелены циновки красного цвета.

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

В первой строке ввода содержатся два целых числа `N` (`2\ ≤\ N\ ≤\ 100`) и `M` (`2\ ≤\ M\ ≤\ 100`) – размеры площадки.

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

3 5

12 3

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

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

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

Вывести одно вещественное число – минимальное расстояние от края арены до клетки с точностью `10^{-4}`.

21 4
0 10
10 0
0 -10
-10 0

11.0000

В разных частях парка "Страна чудес Гудвина" стоят клоуны и раздают детям воздушные шары. У каждого клона шары своего цвета. Клоун дает ребенку только один шар и только один раз, но можно взять несколько шариков разного цвета у нескольких клоунов. Собирание шариков является своеобразным аттракционом, так как парк настолько большой, что не каждый ребенок может найти всех клоунов, чтобы получить воздушные шары всех возможных цветов.

Известно, сколько пришло в парк детей и сколько шариков раздал каждый клоун. Нужно определить количество детей, собравших шарики всех цветов.

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

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

10 2
9 9

8 9

Для шахматистов в "Стране чудес Гудвина" есть следующее развлечение. На доске `N\ times\ M` расставляется несколько шахматных фигур одного цвета (пешки не используются). Игроку для получения приза необходимо убрать минимальное число фигур с доски так, чтобы оставшиеся фигуры не били друг друга.

Первая строка ввода содержит два числа `N` и `M` (`1\ ≤\ N,\ M\ ≤\ 10`) – размеры доски. Далее следует `N` строк, содержащих по `M` символов – расположение фигур на доске. Символ '.' означает пустое поле, символ 'K' – поле, на котором находится король, 'Q' – королева, 'R' – ладья, 'N' – конь, 'B' – слон. Суммарное количество фигур на доске не превышает 20.

Вывести одно целое число – минимальное число фигур, убираемых с доски.

3 3
K.B
.Q.
R.N

2

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

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

В первой строке ввода содержится одно целое число `N` (`3\ ≤\ N\ ≤\ 50`) – размер лабиринта. Далее следует `N` строк, содержащих по `N` символов – карта лабиринта. Символ '.' означает пустую клетку, символ '#' – клетку с ящиком, символ 'M' (прописная латинская буква M) – клетку с Минотавром. Клетка с Минотавром на карте может появиться ровно один раз, и до неё есть путь от входа в лабиринт. Также все клетки по краю лабиринта, кроме одной, заставлены ящиками.

Вывести номер строки и номер столбца клетки на карте лабиринта, в которой находится сдвигаемый ящик, и направление сдвига ящика ('D' – вниз, 'U' – вверх, 'R' – вправо, 'L' – влево). Если не существует ящика, который можно сдвинуть, чтобы запереть Минотавра, то вывести одно число `-1`.

5
##.##
#...#
###.#
#M..#
#####

3 3 D

Родители отправили детей в "Страну чудес Гудвина", а сами отправились в кафе у входа пить кофе. Дети посмотрели на указатели у входа в парк, выбрали один из аттракционов и отправились в него. Выйдя из аттракциона, они посмотрели на указатели рядом с выходом и снова выбрали один из аттракционов. И так далее. Дети делают выбор совершенно случайно и могут снова посещать те аттракционы, где уже бывали. На каждый аттракцион дети тратят 10 минут. Временем на перемещение между аттракционами можно пренебречь.

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

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

В первой строке вывести в порядке возрастания номера аттракционов, где могут находиться дети.

5 2
4 1 2 3 4
1 2
1 3
1 4
1 5
1 1

1 3 4 5

Парк аттракционов "Страна чудес Гудвина" отправляется из столицы на гастроли по провинциальным городам. Все аттракционы погрузили в вагоны, каждый аттракцион в отдельный вагон. Поезд должен проехать по некоторому заданному маршруту, отцепляя в каждом городе некоторое количество вагонов от хвоста поезда. Среди этих вагонов обязательно должны быть вагоны с аттракционами, которые требуются жителям данного города. Кроме заказанных аттракционов можно отцепить другие вагоны с целью увеличения скорости движения поезда на оставшейся части маршрута. При отсутствии пожеланий по видам аттракционов в некотором городе можно оставить в нем любые аттракционы, а можно не оставлять ни одного. Паровоз без вагонов проезжает перегон между городами за 1000 минут. Если к паровозу прицепить `K` вагонов, то время движения на перегоне возрастет до `(1000+K)` минут.

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

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

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

smalltrain
2
all
iran

2014