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

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

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

Первая строка ввода содержит одно целое число `N` (`3\ ≤\ N\ ≤\ 15`) — количество проволок. Во второй строке содержатся `N` целых чисел от 0 до 2 — количество косточек, выставленных на `i`-й проволоке в "небесном" отделении, а в третьей строке содержатся `N` целых чисел от 0 до 5 — количество косточек, выставленных на `i`-й проволоке в "земном" отделении.

В первой строке вывести одно целое число — число, выставленное на суаньпане.

10
1 0 0 0 1 0 1 0 0 1
1 3 0 2 2 1 0 4 0 3

6302715408

3
0 0 2
0 5 0

60

Французский математик Блез Паскаль известен в истории вычислительной техники не только по названному в честь него языку программирования, но и тем, что он изобрел первое механическое вычислительное устройство, позволяющее находить сумму нескольких чисел.

Одним из своих устройств, позволяющим складывать 8-разрядные числа, Паскаль воспользовался при сочинении "Трактата об арифметическом треугольнике", в котором описывался треугольник из чисел, построенный следующим образом. Верхняя строка арифметического треугольника содержит одно число, равное 1. Каждая последующая строка содержит на одно число больше, чем предыдущая и немного смещена влево по отношению к предыдущей строке. `i`-е число в строке вычисляется как сумма `i`-го и (`i-1`)-го чисел из предыдущей строки (если `i`-е или (`i-1`)-е число в предыдущей строке отсутствует, то оно считается равным 0).

Напишите программу, которая находит `M`-е число в `N`-й строке треугольника Паскаля.

Первая строка ввода содержит два целых числа `N` и `M` (`1\ ≤\ M\ ≤\ N\ ≤\ 1000`) — номер строки и номер искомого числа в строке.

В первой строке вывести одно число — `M`-е число в `N`-й строке треугольника Паскаля. Если это число содержит более 8 разрядов, то вывести только 8 младших разрядов искомого числа (ведущие нули не выводить).

5 4

4

Первым компьютером можно считать аналитическую машину, спроектированную Чарльзом Бэббиджем в середине 19 века. Машина Бэббиджа состояла из арифметического устройства, которое могло выполнять четыре арифметические операции, сравнение чисел и вычисление квадратного корня, и памяти для 1000 40-разрядных десятичных чисел. Программа и вспомогательные данные хранились на перфокартах, а для вывода использовался принтер.

Вам нужно создать программу для этой машины. Программа должна находить `K`-й элемент в возрастающей последовательности, образованной слиянием двух других возрастающих последовательностей чисел. Первая последовательность содержит `N` чисел, а вторая — `M` чисел. Среди этих `N+M` чисел нет одинаковых. Программа должна находить `K`-й элемент за минимальное количество сравнений в худшем случае. Хотя длина программы не важна, но она не должна превышать `10^5` строк. В программе может использоваться два вида команд (каждая команда программы размещается на отдельной перфокарте):

C `i\ j\ l\ g`

Сравнить `i`-й элемент первой последовательности (`1\ ≤\ i\ ≤\ N`) и `j`-й элемент второй последовательности (`1\ ≤\ j\ ≤\ M`). Если `i`-й элемент меньше, чем `j`-й, то перейти на команду с номером `l`, иначе перейти на команду с номером `g`.

R `p\ i`

Вывести `i`-й элемент из `p`-й последовательности (он должен являться `K`-м элементом в последовательности, образовавшейся при слиянии) и завершить выполнение программы.

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

Первая строка ввода содержит три целых числа `N`, `M` и `K` (`1\ ≤\ N,\ M\ ≤\ 10000`, `1\ ≤\ K\ ≤\ N\ +\ M`), разделенных пробелом — длины последовательностей и номер элемента.

Вывести в первой строке одно целое число `P` – длину сгенерированной программы. Далее должно следовать `P` строк с командами в указанном выше формате.

20 11 31

3
C 20 11 2 3
R 2 11
R 1 20

В НИИ доставили ящики с блоками ЭВМ 4-го поколения и выгрузили их во дворе. При создании этой ЭВМ использовались СБИС (сверхбольшие интегральные схемы, каждая такая схема имела 36 ножек и 4 ручки — для переноски). Сотрудники НИИ должны распаковать блоки и установить их на ВЦ, но никто не захотел заниматься этой тяжелой работой, поэтому все спрятались от начальства между ящиками. Ящики имеют форму параллелепипедов и установлены так, что их стенки параллельны осям координат. Начальство может смотреть во двор из зданий НИИ, расположенных достаточно далеко на западе, востоке, севере или юге. На рисунке невидимая начальству часть двора отмечена штриховкой.

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

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

Вывести одно число — площадь невидимой из-за ящиков части двора.

5
2 1 5 4
1 5 5 10
4 10 9 13
6 1 8 3
8 3 12 9

10

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

На изображении площадки для размещения элементов обозначены прописными буквами латинского алфавита. Площадки имеют прямоугольную форму, разные площадки имеют разное буквенное обозначение. Контакты обозначаются цифрами от 1 до 9. Контакты имеют одну общую сторону с соответствующей площадкой и не имеют общих сторон с другими контактами. Номера контактов для одной площадки не повторяются. Проводник, ведущий горизонтально, обозначен символом '-' (минус), а проводник, ведущий вертикально, символом '|'. Места соединения и поворотов проводников на `90^o` обозначены символом '*'. Кроме '*', местом соединения проводников является любой контакт. Символ '+' обозначает прохождение проводников друг над другом без соединения. Проводники соединяют два или более контактов.

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

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

6 10
.*-------2
.|.......B
.1..*---1B
.A2-+-*..B
.3..1.*-3B
.*3CC2*...

A1 B2
A2 B3 C2
A3 C3
B1 C1

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

+ — добавить к регистру значение на вершине стека и убрать его из стека;

^ — поместить значение регистра в стек.

Первоначально стек пуст, а в регистре находится число, которое нужно умножить на `N`.

Первая строка ввода содержит одно целое число `N` (`2\ ≤\ N\ ≤\ 1000`).

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

5

^^+^++

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

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

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

Первая строка ввода содержит два целых числа — количество спутников `N` (`2\ ≤\ N\ ≤\ 100\ 000`) и радиус планеты `R` (`1\ ≤\ R\ ≤\ 1000`). Далее следует `N` строк с координатами спутников `X_i`, `Y_i` (`R^2\ <\ X_i^2+Y_i^2\ ≤\ 100*R^2`).

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

4 10
-20 -20
20 20
-20 20
20 -20

1 2

Компьютеры для обмена информацией соединялись в сети, которые со временем превратились в глобальную сеть Интернет. Первая многопользовательская игра, основанная на идеях D&D, появилась в 1977 году. В D&D результаты хода игрока определяются с помощью броска игральной кости, у которой может быть разное количество граней. В MMORPG, в которую играет Петя, также используется подобная система, и информация о силе атаки оружия указывается в формате `x`d`y`+`z` или `x`d`y`-`z`. Данная формула означает, что сила атаки определяется как сумма очков, полученная в результате `x` бросков кости с `y` гранями (пронумерованными от 1 до `y`), увеличенная или уменьшенная на `z`. Если получившаяся сила атаки превосходит уровень защиты монстра, то монстр получает урон равный силе атаки. Если сила атаки меньше или равна уровню защиты, то урон уменьшается в два раза. Монстр также атакует игрока, поэтому важно убить монстра наименьшим количеством ударов.

Петя не очень силен в математике и теории вероятностей, поэтому он не может оценить, какое оружие лучше – 3d4+0 или 1d12-1. Напишите программу, которая вычисляет среднюю величину урона, наносимого каждым видом оружия при атаке монстров, уровень защиты которых является целым числом, распределенным равномерно в диапазоне от `A` до `B`.

Первая строка ввода содержит три целых числа — количество видов оружия `N` (`1\ ≤\ N\ ≤\ 2000`) и диапазон уровней защиты монстров (`1\ ≤\ A\ ≤\ B\ ≤\ 1000`). Далее следует `N` строк с информацией об оружии в формате `x`d`y`+`z` или `x`d`y`-`z` (`1\ ≤\ x\ ≤\ 50`, `2\ ≤\ y\ ≤\ 20`, `0\ ≤\ z\ ≤\ 1000`, но в формате `x`d`y`-`z` значение `z` не превышает `x`, т.е. сила атаки всегда неотрицательная величина).

Вывести `N` чисел, каждое на отдельной строке — среднюю величину урона для каждого вида оружия с точностью `10^{-3}`.

2 5 8
3d4+0
1d12-1

6.281
4.458

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

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

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

Первая строка вывода должна содержать два целых числа `R` и `C` (`1\ ≤\ R,\ C\ ≤\ 40`). Далее должно быть `R` строк, содержащих по `C` символов — предлагаемые изменения в плане. Символ '#' означает участок, выделенный под строительство как в оригинальном, так и в исправленном плане. Символ '+' означает участок, который был свободным в оригинальном плане, но выделенный под строительство в новом плане. Символ '-' означает участок, ставший свободным в новом плане, а символ '.' – свободный участок в обоих планах.

2 3
#.#
###

4 3
...
-+#
###
...