--->
3 задач
<---
Страница:
1
Отображать по:
#427
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Ваня очень любит шахматы. Причем он не только любит просто играть в шахматы, но часто придумывает разные головоломки и просто забавные задачки с использованием шахматных фигур. Также вместо стандартной шахматной доски 8×8 Ваня часто использует в своих задачах доски другого размера.
Недавно он придумал новую головоломку и рассказал ее своим друзьям. Суть головоломки заключается в следующем. На одно из полей доски размером m×n записывается некоторое положительное целое число и затем на него ставится ферзь.
После этого Ваня делает k ходов ферзем, каждый раз перемещая его по шахматным правилам на одно из полей, на котором он еще не был. При этом каждый раз, перед тем как поставить ферзя на некоторое поле, он записывает на это поле целое число, причем это число всегда больше всех чисел, уже записанных на доске.
Задача друзей Вани – по числам, записанным на доске, восстановить маршрут ферзя или выяснить, что Ваня где-то ошибся. Поскольку Ваня часто выбирает достаточно большие m, n и k, друзья устали решать эту головоломку вручную и решили написать для ее решения программу. Помогите им
Напомним, что по шахматным правилам ферзь может пойти на любое поле доски, находящееся на одной вертикали, горизонтали или диагонали с тем полем, на котором он находится.
Входные данные
В первой строке вводятся числа m, n и k ( 1
m, n300, 0k < mn). Следующие m строк содержат по n целых чисел и описывают поля доски (пустому полю соответствует число 0, а полю, на котором записано число – это число). Все числа, записанные на доске, положительные, целые и не превышают 109.
Выходные данные
Если Ваня ошибся при построении головоломки, выведите сообщение «Wrong Board».
В противном случае выведите m строк по n чисел – для каждого поля выведите номер хода, перед которым ферзь побывал на этом поле, а для последнего поля, на котором он оказался – число k + 1. Для полей, на которые ферзь не попадал, выведите число 0.
Примеры
Входные данные
4 4 7 10 20 0 100 30 0 0 40 0 0 0 0 45 42 0 70
Выходные данные
1 2 0 8 3 0 0 4 0 0 0 0 6 5 0 7
Входные данные
2 4 4 10 20 30 40 0 50 0 0
Выходные данные
Wrong Board
Входные данные
2 2 2 1 2 4 3
Выходные данные
Wrong Board
#428
Темы:
[Условный оператор (if)]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Год назад Флатландию потряс серьезный экономический кризис, после которого, с целью снижения издержек, фермер Джон и фермер Билл решили объединить свои фермы. За год совместной продуктивной работы на объединенной территории было построено четыре сарая.
Однако последствия кризиса в последнее время ощущаются все меньше, да и совместное ведение хозяйства – дело непростое. Поэтому фермеры решили снова разделить свои фермы.
Для раздела ферм решено было построить забор. Разумеется, прежде чем приступить к строительству, фермеры взяли карту совместного хозяйства и стали обсуждать возможное положение забора. Забор должен представлять собой прямую линию. Поскольку по закону границы участков должны быть направлены либо с севера на юг, либо с запада на восток, забор на карте должен представлять собой прямую, параллельную краю карты – вертикальную либо горизонтальную.
Единственная проблема – четыре построенных за год совместной работы сарая. Разумеется, каждому фермеру в результате раздела должно достаться по два сарая. Поэтому после постройки забора два сарая должны оказаться с одной стороны от него, а два других – с другой.
Помогите фермерам найти такое положение для забора. Забор может проходить непосредственно вдоль стены сарая.
Входные данные
На вход программы поступают четыре четверки целых чисел. Каждая четверка описывает один сарай. Первые два числа в описании сарая – это координаты на карте его левого нижнего угла, следующие два числа – координаты правого верхнего угла.
Система координат размещена таким образом, что ось OX направлена слева направо, а ось OY – снизу вверх. Оси координат параллельны краям карты. Стороны сараев также параллельны краям карты. Сараи не имеют общих точек. Каждый сарай имеет ненулевую площадь. Все координаты неотрицательны и не превышают 109.
Выходные данные
Если построить забор, удовлетворяющий всем условиям, невозможно, выведите слово «Impossible».
В противном случае в первой строке выведите слово «Vertical», если забор следует построить параллельно вертикальному краю карты, или слово «Horizontal», если забор следует построить параллельно горизонтальному краю карты.
В следующей строке выведите координату x всех точек забора, если он должен быть вертикальным, либо координату y всех точек забора, если он должен быть горизонтальным. Выведенная координата должна быть целым числом (несложно показать, что если забор можно построить, то его можно построить так, чтобы искомая координата была целой).
Приведенные ниже рисунки соответствуют примерам входных данных.
Примеры
Входные данные
0 0 1 1 1 2 3 3 4 0 5 3 3 4 6 7
Выходные данные
Vertical 3
Входные данные
0 0 1 1 1 2 3 3 4 0 5 2 2 4 6 7
Выходные данные
Horizontal 2
Входные данные
0 0 1 1 1 2 3 3 4 0 5 3 2 4 6 7
Выходные данные
Impossible
#431
Темы:
[Условный оператор (if)]
[Эвристические методы]
Источники:
[
Личные олимпиады,
Открытая олимпиада школьников,
2004,
Задача M
]
[
Командные олимпиады,
ВКОШП,
2004,
Задача I
]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Выполняя очередное задание Министерства образования и сельского хозяйства, программисты Флатландского государственного университета информационных технологий, удобрений и ядохимикатов создали специального робота по прокладке оросительных каналов.
Программа для робота представляет собой последовательность команд. Команды робота приведены в следующей таблице:
| Команда | Обозначение | Действия робота |
| Перемещение | (X) | Переместиться вперед на X километров, прокладывая за собой оросительный канал |
| Поворот налево | L | Повернуть налево на 90o |
| Поворот направо | R | Повернуть направо на 90o |
Любая программа начинается и заканчивается командами перемещения и не содержит двух команд перемещения или двух команд поворота подряд.
Исходно робот размещается в некоторой точке поля, на котором требуется создать оросительную систему. После запуска робот последовательно выполняет команды своей программы. Программа считается корректной, если полученный в результате ее выполнения канал не имеет самопересечений или самокасаний.
Программисты университета написали программу и собрались отправить ее по электронной почте в министерство. Однако, в результате поражения сети университета вирусом программа оказалась испорчена. А именно, из нее исчезли все команды перемещения. Теперь программистам требуется восстановить программу. Поскольку времени очень мало, решено было оставить сохранившиеся команды поворота, вставив между ними команды перемещения так, чтобы получившаяся программа была корректной.
Входные данные
Входные данные содержат команды поворота исходной программы в том порядке, в котором они в ней следовали. Каждая команда представляет собой символ «L» либо «R», команды друг от друга не отделяются. Количество команд не превышает 30 000.
Выходные данные
Выведите любую корректную программу, последовательность команд поворота в которой совпадает с последовательностью, заданной во входных данных. Параметр X каждой команды перемещения должен быть положительным целым числом и не должен превышать 109. Все команды выведите в одной строке и друг от друга не отделяйте.
Примеры
Входные данные
LLLRRR
Выходные данные
(4)L(3)L(1)L(2)R(2)R(1)R(1)
Страница:
1
Отображать по:
Выбрано
:
|