--->
2 задач
<---
Страница:
1
Отображать по:
#18
Темы:
[Эвристические методы]
[Задачи на моделирование]
Источники:
[
Личные олимпиады,
Всероссийская олимпиада школьников,
Заключительный этап,
2006,
2 день,
Задача B
]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Известный математик Соломон В. Голомб предложил название полимино для связной фигуры, вырезанной из клетчатой бумаги по линиям сетки. Фигура называется связной, если из любой ее клетки можно добраться в любую другую, переходя из клетки в клетку через их общую сторону. Шахматист, добавил Голомб, сказал бы, что из любой клетки полимино можно дойти ладьей в любую другую. На рис. 1 приведены примеры восьми полимино.
Рис. 1
Саша увлекается полимино. Для своих экспериментов она вырезает новое полимино из бумаги в клеточку или из старых полимино, оставшихся после предыдущих попыток. Далеко не всегда из старого полимино (рис. 2а, слева) можно вырезать новое (рис. 2а, справа). Поэтому Саша может перед вырезанием нового полимино разделить каждую клетку старого полимино на K2 одинаковых квадратных клеток меньшего размера (см. рис. 2б, здесь K = 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
#1337
Источники:
[
Личные олимпиады,
Всероссийская олимпиада школьников,
Заключительный этап,
2009,
Задача A
]
ограничение по времени на тест
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 |
Страница:
1
Отображать по:
Выбрано
:
|