Открытый командный чемпионат по программированию Южно-Уральского ГУ

Во всех задачах ввод данных производится из файла INPUT.TXT, а вывод результатов - в файл OUTPUT.TXT. Формат входного файла соответствует спецификации, дополнительные проверки не нужны. Время теста указано для процессора 486/100.

Задача 1. Автоморфы [Д. Кнут] (5 сек на тест)

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

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

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

Пример INPUT.TXT:

4

OUTPUT.TXT для примера:

9376

Задача 2. Сложение в фибоначчиевой системе счисления [Д. Кнут] (5 сек на тест)

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

F₀=0, F₁=1, F_n=F_n-1+F_n-2 для n>1.

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

N=F_k1+F_k2+…+F_kr, где F_ki – числа Фибоначчи, а k1 >> k2 >> … >> kr >> 0.

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

N=(b_mb_m-1…b₂)_F <=> , где b_i = 1, если F_i входит в представление, и 0, в противном случае.

Например, 1000000 = 832040 + 121393 + 46368 + 144 + 55 = F₃₀ + F₂₆ + F₂₄ + F₁₂ + F₁₀ или (1000000)₁₀=(10001010000000000010100000000)_F. Эта система счисления напоминает двоичное представление, за исключением того, что в ней никогда не встречаются две 1 подряд. При прибавлении 1 к числу в ФСС возникают два случая. Если младший разряд есть 0, он заменяется на 1 (так как F₂=1), в противном случае в двух младших разрядах будет 01, и они заменяются на 10 (так как F₃=F₂+1). Затем мы должны заменять набор цифр 011 на 100 (так как F_n=F_n-1+F_n-2), до тех пор, пока в строке цифр имеются две рядом стоящие единицы.

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

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

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

Пример INPUT.TXT:

1010

100

OUTPUT.TXT для примера:

10010

Задача 3. Прорыв через лабиринт (5 сек на тест)

В лабиринте размером N´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.

Пример INPUT.TXT для рисунка:

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

OUTPUT.TXT для примера:

7 1

Задача 4. TeTpuc (15 сек на тест)

В колодец размером 4 (ширина) на 16 (высота) поочередно падают N Т-образных фигурок тетриса, которые можно поворачивать по часовой стрелке на 90^o и сдвигать влево или вправо. Фигурки состоят из 5 блоков и повернуты при появлении, как показано на рисунке. Фигурка падает до тех пор, пока ее движение не будет остановлено дном колодца или блоком. После этого происходит удаление заполненных горизонтальных рядов (блоки в верхней части колодца при этом сдвигаются на одну строку вниз) и появляется новая фигурка. Игра заканчивается, если высота кучи в колодце перед появлением фигурки стала больше 13. В первоначальный момент времени в правом нижнем углу колодца находится 1 блок. Необходимо определить последовательность действий, максимизирующую количество уничтоженных рядов.

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

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

Пример INPUT.TXT:

2

OUTPUT.TXT для примера:

2 2

3L1R

Задача 5. СУБД «DUMP» (10 сек на тест)

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

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

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

Пример INPUT.TXT:

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

OUTPUT.TXT для примера:

City, Suppler

Paris, Jones

Paris, Adams

Paris, Jones

Problem 6. Triangle Wave (5 сек на тест)

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.

Sample INPUT.TXT:

3

2

Sample OUTPUT.TXT:

1

22

333

22

1

1

22

333

22

1