--->
232 задач
<---
Источники
#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
#482
Темы:
[Условный оператор (if)]
[Одномерные массивы]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Лавочки в парке устроены следующим образом. Несколько одинаковых кубических гранитных блоков ставятся в ряд, а на них кладется гранитная плита (см. рисунок). Архитектор-модернист решил, что будет интереснее, если у всех лавочек расположение гранитных блоков-ножек будет разным (и не обязательно симметричным). При этом они располагаются так, чтобы плита не падала: для этого достаточно, чтобы и слева, и справа от центра плиты был хотя бы один гранитный блок или его часть (в частности, если центр плиты приходится на середину какого-нибудь блока, то и слева, и справа от центра плиты находится часть блока, и плита не падает).
Грабители обнаружили, что можно по одному вытаскивать гранитные блоки, находящиеся с краю (как слева, так и справа). Они хотят вытащить из-под лавочки как можно больше блоков так, чтобы она при этом не упала (передвигать оставшиеся блоки нельзя). Определите, какие блоки они должны оставить.
Входные данные
В первой строке входных данных содержатся два числа: L - длина лавочки и K - количество гранитных блоков-ножек. Оба числа натуральные и не превышают 10 000.
Во второй строке следуют K различных целых неотрицательных чисел, задающих положение каждой ножки. Положение ножки определяется расстоянием от левого края плиты до левого края ножки (ножка - это куб размером 1×1×1). Ножки перечислены слева направо (то есть начиная с ножки с меньшим расстоянием до левого края).
Выходные данные
Требуется перечислить ножки, которые грабителям нужно оставить. Для каждой ножки нужно выдать ее положение, как оно задано во входных данных. Ножки следует перечислять слева направо, в том порядке, в котором они встречаются во входных данных.
Пример
| Входные данные | Выходные данные |
| 5 2 0 2 |
2 |
| 13 4 1 4 8 11 |
4 8 |
| 14 6 1 6 8 11 12 13 |
6 8 |
Второй пример соответствует лавочке на рисунке.
#495
Темы:
[Двумерные массивы]
[Условный оператор (if)]
Источники:
[
Личные олимпиады,
Московская олимпиада школьников,
10-11 классы,
2007,
2 день,
Задача B
]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Дан набор натуральных чисел: a1, …, aN. По этому набору строится таблица чисел размером N x N по следующему правилу: в клетку i-го столбца j-й строки записывается большее из чисел ai и aj при i ≠ j (если ai = aj, то записывается это число); на пересечении i-го столбца и i-й строки записывается число 0.
Дана таблица чисел. Требуется определить, могла ли она быть построена по данным правилам из какого-либо набора чисел a1, …, aN.
Входные данные
В первой строке входных данных задается натуральное число N – размер таблицы (1 ≤ N ≤ 500). В следующих N строках содержится по N чисел – числа соответствующей строки из таблицы (все числа целые неотрицательные и не превосходят 1 000).
Выходные данные
В одну строку выведите через пробел числа a1, …, aN. Если решений несколько, выведите любое из них. Если набора, удовлетворяющего данной таблице, не существует, выведите одно число "-1".
Примеры
Входные данные
3 0 4 6 4 0 6 6 6 0
Выходные данные
4 4 6
Входные данные
2 0 1 2 0
Выходные данные
-1
#505
Темы:
[Двумерные массивы]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
В некоторых клетках квадрата \(N\) x \(N\) живут микроорганизмы (не более одного в одной клетке). Каждую секунду происходит следующее:
– все микроорганизмы, у которых менее 2-х соседей, умирают от скуки (соседями называются микроорганизмы, живущие в клетках, имеющих общую сторону или вершину);
– все микроорганизмы, у которых более 3-х соседей, умирают от перенаселенности;
– на всех пустых клетках, у которых ровно в трех соседних клетках жили микроорганизмы, появляются новые микроорганизмы.
Все изменения происходят одновременно, то есть для каждой клетки сначала выясняется ее судьба, а затем происходят изменения сразу во всех клетках.
Требуется по данной конфигурации определить, во что она превратится через \(T\) секунд.
Входные данные
В первой строке вводятся два натуральных числа – \(N\) (1 ≤ \(N\) ≤ 10) и \(T\) (1 ≤ \(T\) ≤ 100). Далее записано \(N\) строчек по \(N\) чисел, описывающих начальную конфигурацию (0 – пустая клетка, 1 – микроорганизм). Числа в строках разделены пробелами.
Выходные данные
Требуется вывести \(N\) строк по \(N\) чисел – описание конфигурации через \(T\) секунд (в том же формате, как и во входных данных).
Примеры
Входные данные
3 1 1 0 1 1 0 1 1 0 1
Выходные данные
0 0 0 1 0 1 0 0 0
Входные данные
2 2 1 1 1 1
Выходные данные
1 1 1 1
Входные данные
5 10 1 0 1 1 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0
Выходные данные
0 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
#507
Темы:
[Одномерные массивы]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Последовательность чисел назовем симметричной, если она одинаково читается как слева направо, так и справа налево. Например, следующие последовательности являются симметричными:
1 2 3 4 5 4 3 2 1
1 2 1 2 2 1 2 1
Вашей программе будет дана последовательность чисел. Требуется определить, какое минимальное количество и каких чисел надо приписать в конец этой последовательности, чтобы она стала симметричной.
Входные данные
Сначала вводится число \(N\) — количество элементов исходной последовательности (1 ≤ \(N\) ≤ 100). Далее идут \(N\) чисел — элементы этой последовательности, натуральные числа от 1 до 9.
Выходные данные
Выведите сначала число \(M\) — минимальное количество элементов, которое надо дописать к последовательности, а потом \(M\) чисел (каждое — от 1 до 9) — числа, которые надо дописать к последовательности.
Примеры
Входные данные
9 1 2 3 4 5 4 3 2 1
Выходные данные
0
Входные данные
5 1 2 1 2 2
Выходные данные
3 1 2 1
Входные данные
5 1 2 3 4 5
Выходные данные
4 4 3 2 1
Выбрано
:
|