Ваня очень любит шахматы. Причем он не только любит просто играть в шахматы, но часто придумывает разные головоломки и просто забавные задачки с использованием шахматных фигур. Также вместо стандартной шахматной доски 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
Год назад Флатландию потряс серьезный экономический кризис, после которого, с целью снижения издержек, фермер Джон и фермер Билл решили объединить свои фермы. За год совместной продуктивной работы на объединенной территории было построено четыре сарая.
Однако последствия кризиса в последнее время ощущаются все меньше, да и совместное ведение хозяйства – дело непростое. Поэтому фермеры решили снова разделить свои фермы.
Для раздела ферм решено было построить забор. Разумеется, прежде чем приступить к строительству, фермеры взяли карту совместного хозяйства и стали обсуждать возможное положение забора. Забор должен представлять собой прямую линию. Поскольку по закону границы участков должны быть направлены либо с севера на юг, либо с запада на восток, забор на карте должен представлять собой прямую, параллельную краю карты – вертикальную либо горизонтальную.
Единственная проблема – четыре построенных за год совместной работы сарая. Разумеется, каждому фермеру в результате раздела должно достаться по два сарая. Поэтому после постройки забора два сарая должны оказаться с одной стороны от него, а два других – с другой.
Помогите фермерам найти такое положение для забора. Забор может проходить непосредственно вдоль стены сарая.
На вход программы поступают четыре четверки целых чисел. Каждая четверка описывает один сарай. Первые два числа в описании сарая – это координаты на карте его левого нижнего угла, следующие два числа – координаты правого верхнего угла.
Система координат размещена таким образом, что ось 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
Выполняя очередное задание Министерства образования и сельского хозяйства, программисты Флатландского государственного университета информационных технологий, удобрений и ядохимикатов создали специального робота по прокладке оросительных каналов.
Программа для робота представляет собой последовательность команд. Команды робота приведены в следующей таблице:
| Команда | Обозначение | Действия робота |
| Перемещение | (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)
В одну транспортную компанию поступил заказ на перевозку двух ящиков из одного города в другой. Для перевозки ящики решено было упаковать в специальный контейнер.
Ящики и контейнер имеют вид прямоугольных параллелепипедов. Длина, ширина и высота первого ящика – \(l_1\), \(w_1\) и \(h_1\), соответствующие размеры второго ящика – \(l_2\), \(w_2\) и \(h_2\). Контейнер имеет длину, ширину и высоту \(l_c\), \(w_c\) и \(h_c\).
Поскольку ящики содержат хрупкое оборудование, после упаковки в контейнер каждый из них должен остаться в строго вертикальном положении. Таким образом, ящики можно разместить рядом или один на другом. Для надежного закрепления в контейнере стороны ящиков должны быть параллельны его сторонам. Иначе говоря, если исходно ящики были расположены так, что все их стороны параллельны соответствующим сторонам контейнера, то каждый из них разрешается перемещать и поворачивать относительно вертикальной оси на угол, кратный 90 градусам.
Разумеется, после упаковки оба ящика должны полностью находиться внутри контейнера и не должны пересекаться.
Выясните, можно ли поместить ящики в контейнер с соблюдением указанных условий.
Первая строка входных данных содержит \(l_1\), \(w_1\) и \(h_1\), вторая – \(l_2\), \(w_2\) и \(h_2\), третья – \(l_c\), \(w_c\) и \(h_c\). Все размеры – целые положительные числа, не превышающие 1000. Числа в строках разделены пробелами.
Выведите YES, если ящики можно упаковать в контейнер, и NO в противном случае.
В первых двух примерах ящики можно разместить рядом, при этом во втором один из них следует повернуть на 90 градусов. В третьем примере ящики можно разместить один на другом. В четвертом примере первый ящик слишком высокий и не влезает в контейнер. В пятом примере ящики нельзя разместить ни рядом, ни один на другом.
2 2 3 3 3 3 3 5 3
YES
2 3 3 3 2 3 4 4 4
YES
4 1 2 3 3 2 4 3 4
YES
1 1 4 1 1 3 10 10 3
NO
3 2 2 3 1 2 5 2 3
NO
Недавно Билл устроился на работу полицейским. Теперь ему предстоит каждый вечер обходить свой участок, который представляет собой прямоугольник, состоящий из N×M кварталов. Каждый квартал имеет вид квадрата размером 100×100 метров, кварталы отделены друг от друга прямыми улицами.
Совершая обход, Билл выходит из полицейского управления, расположенного около юго-западного угла его участка, обходит свой участок и возвращается в управление. Во время обхода Билл должен пройти по каждому отрезку улицы на территории своего участка как минимум один раз. Известно, что во время обхода Билл проходит отрезок длиной 100 метров за одну минуту. Выясните, какое минимальное число минут потребуется Биллу, чтобы совершить обход.
Вводятся целые числа N и M, разделенные пробелом (1\( \le\)N, M\( \le\)10 000).
Выведите минимальное время, за которое Билл может совершить обход.
Один из возможных оптимальных путей для Билла во втором примере показан на рисунке.
1 1
4
2 2
16
3 4
38