Страница: 1 Отображать по:
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

 

Полимино


Рис. 1


Саша увлекается полимино. Для своих экспериментов она вырезает новое полимино из бумаги в клеточку или из старых полимино, оставшихся после предыдущих попыток. Далеко не всегда из старого полимино (рис. 2а, слева) можно вырезать новое (рис. 2а, справа). Поэтому Саша может перед вырезанием нового полимино разделить каждую клетку старого полимино на K2 одинаковых квадратных клеток меньшего размера (см. рис. 2б, здесь K = 2).

2


         Рис. 2а                                                                   Рис. 2б


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

Например, на рис. 2б приведены все возможные способы вырезания полимино, приведенного на рис. 2а, при K = 2.

Напишите программу, которая ответит на интересующий Сашу вопрос.

Входные данные

Первая строка входных данных содержит число K (1 ≤ K ≤ 10 000).

Далее следуют описания двух полимино, сначала нового, затем старого. Каждое полимино задается следующим образом — в первой строке описания задаются размеры H (высота) и W (ширина) минимально возможного прямоугольника, в котором можно разместить данное полимино. Следующие Н строк содержат по W символов описания клеток. При этом клетка, входящая в полимино, обозначается символом «X» (прописная латинская буква «икс»), а не входящая — символом «.» (точка). Количество клеток в каждом полимино не превышает 300.

Выходные данные

Выведите одно число — количество различных способов вырезать заданное новое полимино из старого, каждая клетка которого разбита на K2 клеток.


Примеры
Входные данные
2
6 6
XXXXXX
X....X
X....X
X....X
X....X
XXXXXX
5 5
XXXXX
XXXXX
XX.XX
XXXXX
XXXXX
Выходные данные
9
ограничение по времени на тест
0.0 second;
ограничение по памяти на тест
0 megabytes
Задана последовательность команд "поворот налево" и "поворот направо". Требуется каждой команде сопоставить число шагов, чтобы путь не пересекал и не касался самого себя.

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

Программа для робота представляет собой последовательность команд. Команды робота приведены в следующей таблице:

 

Команда

Обозначение

Действия робота

Перемещение

(X)

Переместиться вперед на X километров, прокладывая за собой оросительный канал
Поворот налево L Повернуть налево на 90o
Поворот направо

R

Повернуть направо на 90o

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

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

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

Входные данные

Входные данные содержат команды поворота исходной программы в том порядке, в котором они в ней следовали. Каждая команда представляет собой символ «L» либо «R», команды друг от друга не отделяются. Количество команд не превышает 30 000.

Выходные данные

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

includegraphics{pics/program.1}
Примеры
Входные данные
LLLRRR
Выходные данные
(4)L(3)L(1)L(2)R(2)R(1)R(1)
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

Перед оргкомитетом возникла задача распределить эти призы между K участниками так, чтобы все участники получили одинаковое количество призов, и, кроме того, суммарные стоимости призов, полученных разными участниками, совпадали.

Гарантируется, что N делится на K

Входные данные

На вход программы поступают два числа: N и K (1≤<N≤200, 1≤K≤200, K является делителем N).

Выходные данные

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

Если распределить призы требуемым образом невозможно, выведите одно число 0.

Примеры
Входные данные
8 2
Выходные данные
1 4 6 7
2 3 8 5
Входные данные
6 3
Выходные данные
1 6
3 4
5 2
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

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

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

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

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

1.Компьютеры размещаются на плоскости в точках с целочисленными координатами.

2.Координаты компьютеров x и y лежат в диапазоне 0  x, y  106.

3.Никакие два компьютера не располагаются в одной точке.

4.Кабели являются отрезками прямых.

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

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

Входные данные

В первой строке входного файла содержатся числа N и M  количество компьютеров и количество кабелей в схеме (1  N  100 000, 0  M  200 000). В последующих M строках содержатся пары чисел, разделенных пробелами. Каждая такая пара описывает один кабель, числа представляют собой номера соединенных компьютеров. Компьютеры пронумерованы от 1 до N. Никакая пара не встречается дважды, и никакой кабель не соединяет компьютер с самим собой.

Выходные данные

Выходной файл должен содержать N строк. Строка с номером i должна содержать координаты i-го компьютера, разделенные пробелом. Сначала выводится координата x, затем y. Разрешается вывести любой вариант размещения компьютеров, при котором выполняются условия 1–5.

Примечания

Решения, корректно работающие при отсутствии циклов, будут оцениваться из 40 баллов.

Решения, корректно работающие при наличии только одного цикла, будут оцениваться из 60 баллов.

Пример входных и выходных данных

Ввод

Вывод

13 14

11 12

11 13

1 3

3 5

5 8

8 9

8 6

6 3

4 6

4 2

6 10

10 11

10 7

7 4

1 0

3 0

1 1

3 1

0 2

2 2

4 2

1 3

1 4

3 3

3 4

2 5

4 5


ограничение по времени на тест
4.0 second;
ограничение по памяти на тест
64 megabytes

Недавно на уроке информатики ученики одного из классов изучили булевы функции. Напомним, что булева функция $f$ сопоставляет значениям двух булевых аргументов, каждый из которых может быть равен 0 или 1, третье булево значение, называемое результатом. Для учеников, которые выразили желание более подробно изучать эту тему, учительница информатики на дополнительном уроке ввела в рассмотрение понятие цепного вычисления булевой функции $f$.

Если задана булева функция $f$ и набор из $N$ булевых значений $a_1,a_2,\ldots,a_N$, то результат цепного вычисления этой булевой функции определяется следующим образом:

* если $N=1$, то он равен $a_1$;

* если $N>1$, то он равен результату цепного вычисления булевой функции $f$ для набора из $(N-1)$ булевого значения $f(a_1,a_2),a_3,\ldots,a_N$, который получается путём замены первых двух булевых значений в наборе из $N$ булевых значений на единственное булево значение — результат вычисления функции $f$ от $a_1$ и $a_2$.

Например, если изначально задано три булевых значения: $a_1=0$, $a_2=1$, $a_3=0$, а функция $f$ — ИЛИ (OR), то после первого шага получается два булевых значения — (0 OR 1) и 0, то есть 1 и 0. После второго (и последнего) шага получается результат цепного вычисления, равный 1, так как 1 OR 0 = 1.

В конце дополнительного урока учительница информатики написала на доске булеву функцию $f$ и попросила одного из учеников выбрать такие $N$ булевых значений $a_i$, чтобы результат цепного вычисления этой функции был равен единице. Более того, она попросила найти такой набор булевых значений, в котором число единиц было бы как можно бо́льшим.

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

Входные данные

Первая строка входного файла содержит одно натуральное число $N$ ($2\le N\le100\,000$).

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

Выходные данные

В выходной файл необходимо вывести строку из $N$ символов, определяющих искомый набор булевых $a_i$ с максимально возможным числом единиц. Если ответов несколько, требуется вывести любой из них. Если такого набора не существует, выведите в выходной файл фразу «No solution».

Пояснения к примерам

В первом примере процесс вычисления цепного значения булевой функции $f$ происходит следующим образом: $1011\to111\to01\to1$

Во втором примере вычисление цепного значения булевой функции $f$ происходит следующим образом: $11111\to0111\to111\to01\to1$

В третьем примере получить цепное значение булевой функции $f$, равное 1, невозможно.

Примеры
Входные данные
4
0110
Выходные данные
1011
Входные данные
5
0100
Выходные данные
11111
Входные данные
6
0000
Выходные данные
No solution

Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест