Задачи открытого командного чемпионата 2000

Числа, обладающие свойством самовоспроизводимости при выполнении некоторых действий над ними, называют автоморфами. Например, `9376^2=87909376`, четыре последние цифры квадрата совпадают с исходным числом. Найдите все `n`-значные числа `x`, удовлетворяющие уравнению `x^2\ mod\ 10^n\ =\ x`.

Во входном файле в первой строке содержится число `n` (`0\ <\ n\ <\ 100`).

В выходной файл вывести все целые неотрицательные `n`-значные числа, удовлетворяющие уравнению, в порядке возрастания, по одному числу в строке.

4

9376

Числа Фибоначчи хорошо известны. Они определяются рекуррентным соотношением:

`F_0\ =\ 0`, `F_1\ =\ 1`, `F_n\ =\ F_{n-1}\ +\ F_{n-2}` для `n\ >\ 1`.

Фибоначчиева система счисления (ФСС) основана на теореме Цеккендорфа, утверждающей, что любое целое положительное число имеет единственное представление вида

`N\ =\ F_{k_1}\ +\ F_{k_2}\ +\ …\ +\ F_{k_r}`, где `F_{k_i}` – числа Фибоначчи, а `k_1\ ">>"\ k_2\ ">>"\ …\ ">>"\ k_r\ ">>"\ 0`.

Здесь `i\ ">>"\ \ j` означает, что `i\ ≥\ j+2`. Целое неотрицательное число можно записать в виде последовательности нулей и единиц:

`N\ =\ (b_m\ b_{m-1}…b_2)_F\ hArr\ N\ =\ sum_{k=2}^m\ b_k\ F_k`, где `b_i\ =\ 1`, если `F_i` входит в представление, и 0, в противном случае.

Например, `1000000\ =\ 832040\ +\ 121393\ +\ 46368\ +\ 144\ +\ 55` = `F_30\ +\ F_26\ +\ F_24\ +\ F_12\ +\ F_10` или `(1000000)_10=(10001010000000000010100000000)_F`. Эта система счисления напоминает двоичное представление, за исключением того, что в ней никогда не встречаются две 1 подряд. При прибавлении 1 к числу в ФСС возникают два случая. Если младший разряд есть 0, он заменяется на 1 (так как `F_2=1`), в противном случае в двух младших разрядах будет 01, и они заменяются на 10 (так как `F_3\ =\ F_2\ +\ 1`). Затем мы должны заменять набор цифр 011 на 100 (так как `F_n\ =\ F_{n-1}\ +\ F_{n-2}`), до тех пор, пока в строке цифр имеются две рядом стоящие единицы.

Напишите программу для сложения двух чисел в ФСС.

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

В выходной файл вывести результат сложения этих двух чисел также в ФСС.

1010
100

10010

В лабиринте размером `N\ times\ N` с одним выходом кладоискатель нашел клад и хочет вынести его из лабиринта за минимальное количество ходов. У него есть `r` единиц взрывчатки, которая позволяет уничтожить единичную часть внутренней (но не внешней!) стены лабиринта. Ход – это переход в соседнюю клетку по горизонтали или вертикали с возможным одновременным взрывом мешающей части стены. Верхняя левая клетка лабиринта имеет координаты (1,1).

Во входном файле в первой строке содержится целые числа `N` (`2\ ≤\ N\ ≤\ 50`) и `r` (`0\ ≤\ r\ ≤\ 3`), координаты кладоискателя `x,\ y` (`0\ <\ x,\ y\ ≤\ N`, `x` – столбец, `y` – строка) и координаты выхода `u,\ v` (`0\ ≤\ u,\ v\ ≤\ N+1`). Во второй строке указывается количество единичных частей внутренних стен `m` (`0\ ≤\ m\ ≤\ 2*(N-1)*N`). В последующих `m` строках находятся координаты клеток `a_i`, `b_i` и `c_i`, `d_i` (`0\ <\ a_i,b_i,c_i,d_i\ ≤\ N`), между которыми находится `i`-я единичная часть стены.

В выходной файл вывести минимальное количество ходов и количество использованной взрывчатки. Если есть несколько путей одинаковой длины, то выбрать путь с минимальным использованием взрывчатки. Если путь до выхода не найден, то вывести 0 0.

4 1 1 1 3 0
9
1 1 2 1
2 2 1 2
1 3 2 3
2 1 3 1
3 2 3 1
4 2 4 3
3 3 2 3
3 3 3 4
2 4 3 4

7 1

В колодец размером 4 (ширина) на 16 (высота) поочередно падают `N` Т-образных фигурок тетриса, которые можно поворачивать по часовой стрелке на 90`°` и сдвигать влево или вправо. Фигурки состоят из 5 блоков и повернуты при появлении, как показано на рисунке.

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

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

Во входном файле в первой строке содержится целое число `N` (`0\ <\ N\ <\ 200`).

В выходной файл в первой строке вывести количество использованных фигурок (может быть меньше `N`, если game over) и количество уничтоженных рядов. Во второй строке вывести найденную последовательность действий. Для каждой фигурки указывается количество поворотов по часовой стрелке (от 0 до 3) и к какой стенке колодца ее следует приблизить (L – к левой, R – к правой).

2

2 2
3L1R

В реляционной СУБД «DUMP» информация, содержащаяся в базе данных (БД), представлена в виде одной таблицы, являющейся, например, декартовым произведением всех отношений в БД. К ней можно обращаться с помощью запроса выделения необходимых столбцов и строк таблицы, не отбрасывающего дублирующиеся записи. Таблица хранится в следующем виде: в первой строке – список имен столбцов таблицы, затем набор строк, содержащих списки значений полей таблицы. Элементы списка разделяются запятой, за которой следует один или более пробелов: значение{, значение}… (здесь и далее метасимволы { } показывают часть формата, которая повторяется 0 или более раз). Символы запятая и = служат для разделения и не встречаются в именах и значениях БД.

Во входном файле в первой строке содержится список отбираемых для показа столбцов таблицы. Формат строки: ИМЯ 1{, ИМЯ 2}… Во второй строке – список (возможно пустой) условий для отбора записей. Формат строки: ИМЯ 1=значение 1{, ИМЯ 2=значение 2}… Если условий для отбора записей нет, то строка будет пустой. Запись попадает в выходной файл, если значения указанных полей в записи равны указанным значениям. В третьей строке находится список имен столбцов единственной таблицы БД, а в следующих строках – записи таблицы (списки значений полей). Количество записей в таблице не превышает 1000. Длина всех строк входного файла не более 250 символов. Прописные и строчные буквы различаются, в 1-й и 2-й строке используются только имена столбцов таблицы из 3-й строки, имена в 1-й, 2-й и 3-й строке не повторяются.

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

City, Suppler
City=Paris
Suppler, Detail, City,   Total Qty
Smith,   Bolt,   London, 120
Jones,   Screw,  Paris,  100
Adams,   Nut,    Paris,  400
Jones,   Bolt,   Paris,  120

City, Suppler
Paris, Jones
Paris, Adams
Paris, Jones

In this problem you are to generate a triangular wave form according to a specified pair of Amplitude and Frequency.

The input will contain two integers, each on a separate line. The first integer is the Amplitude; the second integer is the Frequency.

For the output of your program, you will be printing wave forms each separated by a blank line. The total number of wave forms equals the Frequency, and the horizontal "height" of each wave equals the Amplitude. The Amplitude will never be greater than nine. The waveform itself should be filled with integers on each line which indicate the "height" of that line. NOTE: There is a blank line after each separate waveform, excluding the last one.

3
2

1
22
333
22
1
 
1
22
333
22
1