Темы --> Информатика --> Алгоритмы --> Эвристические методы
---> 29 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: 1 2 3 4 5 6 >> Отображать по:
ограничение по времени на тест
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
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

На складе хранятся контейнеры с товарами N различных видов. Все контейнеры составлены в N стопок. В каждой стопке могут находиться контейнеры с товарами любых видов (стопка может быть изначально пустой).Автопогрузчик может взять верхний контейнер из любой стопки и поставить его сверху в любую стопку. Необходимо расставить все контейнеры с товаром первого вида в первую стопку, второго вида — во вторую стопку и т.д.

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

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

В первой строке задается одно натуральное число N, не превосходящее 500. В следующих N строках описаны стопки контейнеров: сначала записано число ki количество контейнеров в стопке, а затем ki чисел — виды товара в контейнерах в данной стопке, снизу вверх. В каждой стопке вначале не более 500 контейнеров (в процессе переноса контейнеров это ограничение может быть нарушено).

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

Выведите описание действий автопогрузчика: для каждого действия укажите два числа — из какой стопки брать контейнер и в какую стопку класть. (Обратите внимание, что минимизировать количество операций автопогрузчика не требуется.) Если задача не имеет решения, выдайте одно число 0. Если контейнеры изначально правильно размещены по стопкам, выводить ничего не надо.

Оценка задачи

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

Комментарий к примеру:

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

Примеры
Входные данные
3
4 1 2 3 2
0
0
Выходные данные
1
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Даны эльфы, обладающие темпераментом Bi и олени со строптивостью Ai. С каждым оленем должны ехать два эльфа, причем Bk < Ai < Bj. Необходим выбрать наибольшее количество оленей.

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

Но волшебные олени – строптивые животные, поэтому не любые два эльфа могут ехать на любом олене. А именно, каждый олень характеризуется некоторой строптивостью ai, а каждый эльф – темпераментом bi. Два эльфа j и k могут ехать на i-м олене в том и только в том случае, если либо bj < ai < bk, либо bk < ai < bj.

Чтобы его появление было максимально зрелищным, Санта-Клаус хочет, чтобы в его упряжке было как можно больше оленей. Про каждого оленя Санта знает его строптивость, а про каждого эльфа – его темперамент.

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

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

В первой строке вводятся два целых числа m и n – количество оленей и эльфов, соответственно ( 1$ le$m, n$ le$100 000).

Вторая строка содержит m целых чисел ai – строптивость оленей ( 0$ le$ai$ le$109). В третьей строке записаны n целых чисел bi – темперамент эльфов ( 0$ le$bi$ le$109).

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

В первой строке  выведите одно число k – максимальное количество оленей, которое Санта-Клаус может включить в свою упряжку. В следующих k строках выведите по три целых числа: di, ei, 1, ei, 2 – для каждого оленя в упряжке выведите его номер и номера эльфов, которые на нем поедут. Если решений несколько, выведите любое.

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

Примеры
Входные данные
4 6
2 3 4 5
1 3 2 2 5 2
Выходные данные
2
1 1 2
2 4 5
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
На плоскости заданы начальная и конечная точка. Перемещение разрешено поворотом на 90 градусов по или против часовой стрелки относительно точек (0, 0) и (0, 1). Необходимо попасть из начальной точки в конечную.

На планете Плюк, поверхность которой мы будем считать абсолютно плоской, был разработан новый принцип перемещения единственного имеющегося там транспортного средства – пепелаца. А именно, на расстоянии одного километра друг от друга в точках (0, 0) и (1, 0) были построены две станции управления пепелацами A и B. С помощью них можно мгновенно переместить любой пепелац, повернув его на 90 градусов по или против часовой стрелки относительно точки A или B. Расстояние от пепелаца до соответствующей станции при этом не меняется. Следующее перемещение можно делать как относительно той же станции, так и относительно другой.

Например, если повернуть пепелац, находящийся в точке (3, 1) на 90 градусов против часовой стрелки относительно станции A, то он переместится в точку (- 1, 3), если его затем повернуть на 90 градусов по часовой стрелке относительно станции B, то он переместится в точку (4, 2), если затем повернуть его вокруг станции B по часовой стрелке еще раз, он переместиться в точку (3, - 3).

Один житель планеты недавно решил отправиться на своем пепелаце в гости к другу. Житель проживает около точки с координатами (x1, y1), а его друг – около точки с координатами (x2, y2). Помогите жителю с помощью станций управления пепелацем оказаться как можно ближе к месту, где проживает его друг, чтобы потом меньше было идти по пустыне.

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

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

На вход программы поступают четыре целых числа – x1, y1, x2 и y2, они не превышают 104 по абсолютной величине.

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

Выведите  последовательность перемещений с использованием станций управления, которая перемещает пепелац из точки (x1, y1) как можно ближе к точке (x2, y2).

Поворот по часовой стрелке относительно станции A обозначается как «+A», поворот против часовой стрелки относительно станции A обозначается как «-A», соответствующие повороты относительно станции B обозначаются как «+B» и «-B». Выводите по одному перемещению на строке.

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

begin{textblock}{8}(12,0)%% includegraphics{pics/pluk.1}%% end{textblock}

Примеры
Входные данные
3 1
3 -3
Выходные данные
+A
-B
-B
+A
+A
-B
-B
+A
Входные данные
0 0
3 0
Выходные данные
-A
+B
+A
-B
ограничение по времени на тест
0.0 second;
ограничение по памяти на тест
0 megabytes
Взаимной удаленностью двух вершин невзвешенного графа называется кратчайшее расстояние между ними. Необходимо построить граф, в котором сумма взаимных удаленностей вершин равна задана числу.

Сверхсекретный завод, расположенный высоко в горах, занимается изготовлением новейших систем контроля торсионных полей – нанокристаллов. Нанокристалл состоит из нескольких атомов, некоторые из которых попарно связаны сверхпрочными торсионными связями.

Нанокристалл стабилен, если между любыми двумя его атомами можно построить соединяющую их цепочку связей, возможно с использованием других атомов. Например, нанокристалл $ cal {X}$ из четырех атомов A, B, C и D, в котором между собой связаны пары A - B, A - C, B - C и B - D, стабилен. Если же, например, в нанокристалле из данных четырех атомов связаны только пары A - B и C - D, то кристалл нестабилен, поскольку, например, A и C не соединены никакой цепочкой связей.

Для любой пары атомов стабильного нанокристалла определена их взаимная удаленность – минимальная длина цепочки из связей, которая их соединяет. Например, рассмотрим описанный выше нанокристалл $ cal {X}$. Взаимная удаленность атомов A и B равна единице (они соединены напрямую), а взаимная удаленность C и D равна двум (они соединены цепочками C - B - D и C - A - B - D, длина кратчайшей цепочки равна двум).

Важнейшей характерикой стабильного нанокристалла является его емкость. Емкость нанокристалла равна сумме взаимных удаленностей всех пар его атомов. Например, емкость нанокристалла $ cal {X}$ равна 8.

Недавно на завод поступил заказ – разработать стабильный нанокристалл заданной емкости c. При этом как число атомов в нанокристалле, так и число связей может быть произвольным. Помогите ученым разработать такой кристалл!

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

На вход программы поступает число c ( 1$ le$c$ le$10 000).

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

В первой строке  выведите два целых числа n и m – количество атомов и связей в разработанном нанокристалле, соответственно. Будем считать, что атомы нанокристалла пронумерованы от 1 до n. Следующие m строк должны содержать по два целых числа – пары атомов, которые следует соединить торсионными связями. Если решений несколько, выведите любое.

Если искомого нанокристалла не существует, выведите в первой и единственной строке  выходных данных два нуля.

Примеры
Входные данные
2
Выходные данные
0 0
Входные данные
8
Выходные данные
4 4
1 2
1 3
1 4
3 4

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