Страница: 1 2 3 >> Отображать по:
ограничение по времени на тест
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
ограничение по времени на тест
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 2 3 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест