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

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

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

Первая строка ввода содержит одно целое число — количество страниц в докладе `N` (`1\ ≤\ N\ ≤\ 30000`). Далее следует `N-1` строка, каждая из которых содержит одно целое число от 1 до `N` – номера собранных страниц. Все номера страниц различны.

Вывести одно целое число – номер потерянной страницы.

5
4
5
2
1

3

Ральф не очень хорошо читает и пишет, но зато он очень хорошо считает, он выполняет сложение, вычитание, умножение, возведение в степень мгновенно, хотя все вычисления при этом делает по модулю 32, то есть вместо правильного ответа у него получается остаток от деления результата на 32. Например, при умножении 7 на 7 он получает ответ 17. Поэтому у Ральфа очень плохие оценки даже по математике, несмотря на его способности к счету. Однажды миссис Гувер, чтобы Ральф спокойно сидел и не бегал по классу, заставила его посчитать значение `A_N`, где `A_i\ =\ A_{i-1}^P\ +\ B` для `i` от 1 до `N`.

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

Первая строка ввода содержит пять целых чисел – `A_0`, `B`, `P`, `N` и `M` (`1\ ≤\ A_0,\ B,\ P,\ N\ ≤\ 10^9`, `2\ ≤\ M\ ≤\ 10^5`).

Вывести одно целое число — значение `A_N\ mod\ M`.

15 5 2 6 10

5

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

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

Первая строка ввода содержит одно целое число `N` (`1\ ≤\ N\ ≤\ 100`) – количество платформ. Вторая строка содержит `N` различных целых чисел от 1 до `N` – номера платформ в порядке прибытия.

Вывести сообщение "YES", если можно обеспечить правильный порядок платформ, или сообщение "NO", если нельзя.

4
1 3 4 2

YES

4
4 3 2 1

NO

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

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

Первая строка ввода содержит число `N` (`1\ ≤\ N\ ≤\ 20`) – размеры реактора. Далее следует `3*N` строк по `N` символов – три снимка реактора размером `N\ times\ N` спереди, справа и сверху. Символ '.' означает отсутствие блоков в данном ряду, а символ '#' – наличие хотя бы одного блока.

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

2
#.
##
.#
##
##
#.

4

1
#
.
.

-1

3
...
.#.
...
...
.#.
...
...
.#.
...

1

Барт и Милхаус решили создать сигнальную систему для общения друг с другом. Для генерации сигнала они решили использовать китайскую лазерную указку и расставить на улице зеркала так, чтобы луч прошел от домика на дереве до комнаты Милхауса в обход препятствий: домов, деревьев, почтовых ящиков и т.п. Они выбрали несколько подходящих точек для установки зеркал и хотят использовать расстановку с минимальным количеством зеркал, так как каждое отражение приводит к потере мощности сигнала, а если таких расстановок несколько, то из них выбрать расстановку с минимальной длиной пути луча. Луч лазера не должен проходить через препятствия или касаться их. Луч не должен проходить дважды через одно зеркало и не может проходить через зеркало без отражения. Угол между падающим на зеркало лучом и отраженным должен быть строго меньше 180 градусов.

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

Первая строка ввода содержит шесть целых чисел - количество препятствий `K` (`1 ≤\ K\ ≤\ 100`) и количество точек для установки зеркал `N` (`1\ ≤\ N\ ≤\ 100`), координаты источника лазерного луча `X_S`, `Y_S` и координаты приемника `X_D`, `Y_D` . Далее следует `K` строк, каждая строка содержит четыре целых числа – координаты противоположных углов препятствия (препятствия являются невырожденными прямоугольниками со сторонами параллельными осям координат). Далее следует `N` строк, каждая строка содержит два целых числа – координаты возможной точки для установки зеркала. Все координаты – целые числа в диапазоне от 0 до 1000. Точки для установки зеркал различны, находятся вне препятствий и не соприкасаются с ними. Препятствия не пересекаются, но могут касаться друг друга.

В первой строке вывести одно целое число `M` (`0\ ≤\ M\ ≤\ N`) – количество установленных зеркал. Во второй строке вывести `M` целых чисел – номера точек в порядке прохождения их лучом лазера. Если существует несколько оптимальных расстановок зеркал, то можно вывести любую из них. Если решения не существует, то в первой строке вывести сообщение "No solution" (без кавычек).

1 3 100 200 700 600
200 300 600 500
0 400
400 200
300 600

2
1 3

Профессор Фринк хочет скопировать информацию о своих изобретениях из своего компьютера на CD. Для уменьшения количества дисков он придумал следующий алгоритм. На первом этапе файлы упорядочиваются в порядке уменьшения их размера (при совпадении размеров первым должен быть файл, указанный в списке копируемых файлов раньше). На втором этапе файлы записываются на диски. Для записи очередного файла выбирается диск с наименьшим номером среди тех используемых для копирования дисков, на который данный файл может поместиться. Если ни одного такого диска нет, к набору дисков добавляется новый диск, на который записывается файл.

Напишите программу, определяющую какие файлы на какой диск будут записаны при использовании этого алгоритма. При записи нужно учитывать, что файл должен занимать целое число кластеров и, если размер кластера равен `C`, файл размером от 1 до `C` байт занимает `C` байт на диске, файл размером от `C+1` до `2*C` занимает `2*C` байт на диске и так далее.

Первая строка ввода содержит три целых числа - количество файлов `N` (`1\ ≤\ N\ ≤\ 1000`), размер одного диска `S` (`10^3\ ≤\ S\ ≤\ 10^9`) и размер кластера `C` (`1\ ≤\ C\ ≤\ S`, `S` кратно `C`). Вторая строка ввода содержит `N` целых чисел в диапазоне от 1 до `S` – размеры файлов.

В первой строке выведите одно целое число `M` – количество дисков, использованных для записи. Далее выведите `M` строк, в `(i+1)`-й строке выведите номера файлов, которые нужно записать на `i`-й диск, в порядке их записи.

3 675840000 4096
15 675839000 100000

2
2
3 1

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

Первая строка ввода содержит два целых числа - количество сортов `N` и количество одинаковых конфет `K` (`1\ ≤\ N,\ K\ ≤\ 10`).

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

3 2

4

2 3

5

"Я знаю больше двухсот способов сдать сдачу в один доллар и один пенни" – сказал Апу, отсчитывая сдачу Гомеру с пятерки за конфеты.

"Думаю, даже если использовать монеты всех шести номиналов, количество способов не может быть больше ста" – ответил Гомер.

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

Первая строка ввода содержит два целых числа – сумма сдачи `S` (`1\ ≤\ S\ ≤\ 10000`) и количество различных номиналов монет `N` (`1\ ≤\ N\ ≤\ 10`). В следующей строке `N` различных целых чисел в диапазоне от 1 до 1000 в порядке возрастания – номиналы монет.

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

101 6
1 5 10 25 50 100

293

Мэгги разломала ксилофон, и у нее получился набор из разноцветных палочек. Палочки в ксилофоне идут по возрастанию длины, каждая палочка длиннее предыдущей на 1 сантиметр, самая маленькая палочка имеет длину `N` сантиметров, а самая большая – `M` сантиметров. Мэгги складывает из палочек треугольник и показывает его Мардж. Если треугольник отличается от уже виденных ранее, Мардж хвалит Мэгги, иначе просит не отвлекать ее и возвращается к домашним делам.

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

Первая строка ввода содержит два целых числа `N` и `M` (`1\ ≤\ N\ <\ M\ ≤\ 10^6`) - диапазон длин палочек.

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

3 7

9

У Диско Стю есть большая коллекция виниловых пластинок, но они не лежат на полках, а разбросаны по полу. Однажды Стю решил подсчитать, сколько у него пластинок. Он не стал их собирать с пола, а просто встал повыше и стал считать только те пластинки, которые были видны.

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

Первая строка ввода содержит два целых числа - количество пластинок `N` (`1\ ≤\ N\ ≤\ 100`) и радиус пластинок `R` (`1\ ≤\ R\ ≤\ 100`). Далее следует `N` строк, каждая из которых содержит два целых числа `X_i`, `Y_i` (`0\ ≤\ X_i,\ Y_i\ ≤\ 1000`) – координаты центра `i`-й пластинки. Пластинки перечисляются в том порядке, в котором их бросали на пол.

Вывести одно целое число – количество видимых пластинок.

3 1
1 2
1 1
1 2

2

Для очистки загрязненного озера было решено использовать подводного робота. С помощью подводной съемки было выяснено местонахождение всех препятствий и загрязнений в озере и составлена карта. Озеро было разбито на квадратные участки-клетки, в каждой клетке было обнаружено от 0 до 9 единиц мусора. Робот может передвигаться по дну озера, обходя препятствия вокруг, но не может их "перелететь" сверху. За одну единицу времени робот может переместиться в соседнюю клетку по вертикали или горизонтали. Робот может мгновенно поднять манипуляторами любой предмет, находящийся в той же клетке, где находится робот. Также мгновенно он может бросить предмет в манипуляторах на грунт в этой клетке. При перемещении робот может нести не более одного предмета. Робот должен собрать весь мусор в определенной клетке озера, с которой мусор будет поднят на поверхность и вывезен на свалку. После выполнения работы роботу не обязательно находиться в клетке с подъемником. Робот может быть как в этой клетке, так и в любой другой.

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

Первая строка ввода содержит шесть целых чисел - размеры озера в клетках `N` и `M` (`2\ ≤\ N,\ M\ ≤\ 100`), начальное расположение робота `R` и `C` (`1\ ≤\ R\ ≤\ N`, `1\ ≤\ C\ ≤\ M`) и расположение подъемника `D` и `E` (`1\ ≤\ D\ ≤\ N`, `1\ ≤\ E\ ≤\ M`). Далее следует `N` строк по `M` символов – карта озера. Символ '#' означает клетку с препятствием (например, скалы или водоросли), а цифры от 0 до 9 означают количество единиц мусора в свободной от препятствий клетке. Клетки с роботом и подъемником не содержат препятствий.

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

2 3 2 3 1 3
1#3
#12

6 7