Плюсануть
Поделиться
Класснуть
Запинить

Задачи из рубрикатора

Тег: Двумерные массивы

Условие задачи  
ID 27224
Bovine Genomics №3
Темы: Двумерные массивы   

У Фермера Джона есть N коров с пятнами и N коров без пятен. ФД, как генетик, знает, что пятна на коровах вызваны мутациями в одной позиции коровьего генома.
За большие деньги ФД выписал геномы своих коров. Каждый геном есть строка длины M, построенная из четырёх символов A, C, G, T. Когда он выписал их, у него получилась такая таблица (для N=3):
 
Позиция:                  1 2 3 4 5 6 7 ... M
 
Пятнистая корова 1: A A T C C C A ... T
Пятнистая корова 2: G A T T G C A ... A
Пятнистая корова 3: G G T C G C A ... A
 
Без пятен корова 1: A C T C C C A ... G
Без пятен корова 2: A C T C G C A ... T
Без пятен корова 3: A C T T C C A ... T

Внимательно проанализировав эту таблицу, он предположил, что позиция 2 есть потенциальное место в геноме, которое отвечает за пятнистость. Потому что в этой позиции у коров без пятен находится один и тот же символ С, а у пятнистых коров находятся символы A или G. Причём G больше никогда не появлялось на позиции 2. Позиция 1 не может объяснять пятнистость, поскольку A в этой позиции есть и у пятнистых коров.
 
По заданным геномам коров ФД, посчитайте количество позиций, которые потенциально могли бы объяснять пятнистость.
 
ФОРМАТ ВВОДА:
 
Первая строка ввода содержит N и M, оба - положительные целые числа не более 100. Каждая из следующих N строк содержит по M символов. Они описывают геномы пятнистых коров. Следующие N строк описывают геномы коров без пятен.

ФОРМАТ ВВОДА:
 
Вычислите количество позиций генома (целое число в интервале от 0…M), которые потенциально могут объяснять пятнистость. Такие позиции можно предсказывать по заданной информации.
 
Ввод Вывод
3 8
AATCCCAT
GATTGCAA
GGTCGCAA
ACTCCCAG
ACTCGCAT
ACTTCCAT
1

ID 37042
Заполнение по диагоналям
Темы: Двумерные массивы   

Даны числа n и m. Создайте массив A[n][m] и заполните его, как показано на примере.

Входные данные: Программа получает на вход два числа n и m.
Выходные данные: Программа должна вывести полученный массив, отводя на вывод каждого числа ровно 3 символа.

Примеры

Входные данные Выходные данные
1 4 10
  0  1  3  6 10 14 18 22 26 30
  2  4  7 11 15 19 23 27 31 34
  5  8 12 16 20 24 28 32 35 37
  9 13 17 21 25 29 33 36 38 39

ID 37046
12.25б
Темы: Двумерные массивы   

Даны числа n и m. Создайте массив A[n][m] и заполните его, как показано на примере.

Входные данные: Программа получает на вход два числа n и m.
Выходные данные: Программа должна вывести полученный массив, отводя на вывод каждого числа ровно 3 символа.

Примеры

Входные данные Выходные данные
1 4 5
  1   5   9  13  17 
  2   6  10  14  18 
  3   7  11  15  19 
  4   8  12  16  20 

ID 37048
12.25г
Темы: Двумерные массивы   

Даны числа n и m. Создайте массив A[n][m] и заполните его, как показано на примере.

Входные данные: Программа получает на вход два числа n и m.
Выходные данные: Программа должна вывести полученный массив, отводя на вывод каждого числа ровно 3 символа.

Примеры

Входные данные Выходные данные
1 4 5
  4   8  12  16  20 
  3   7  11  15  19 
  2   6  10  14  18 
  1   5   9  13  17

ID 37047
12.25в
Темы: Двумерные массивы   

Даны числа n и m. Создайте массив A[n][m] и заполните его, как показано на примере.

Входные данные: Программа получает на вход два числа n и m.
Выходные данные: Программа должна вывести полученный массив, отводя на вывод каждого числа ровно 3 символа.

Примеры

Входные данные Выходные данные
1 4 5
  5   4   3   2   1 
 10   9   8   7   6 
 15  14  13  12  11 
 20  19  18  17  16

ID 37049
12.25ж
Темы: Двумерные массивы   

Даны числа n и m. Создайте массив A[n][m] и заполните его, как показано на примере.

Входные данные: Программа получает на вход два числа n и m.
Выходные данные: Программа должна вывести полученный массив, отводя на вывод каждого числа ровно 3 символа.

Примеры

Входные данные Выходные данные
1 4 5
 16  17  18  19  20 
 11  12  13  14  15 
  6   7   8   9  10 
  1   2   3   4   5

ID 37050
12.25з
Темы: Двумерные массивы   

Даны числа n и m. Создайте массив A[n][m] и заполните его, как показано на примере.

Входные данные: Программа получает на вход два числа n и m.
Выходные данные: Программа должна вывести полученный массив, отводя на вывод каждого числа ровно 3 символа.

Примеры

Входные данные Выходные данные
1 4 5
 17  13   9   5   1 
 18  14  10   6   2 
 19  15  11   7   3 
 20  16  12   8   4 

ID 37051
12.25и
Темы: Двумерные массивы   

Даны числа n и m. Создайте массив A[n][m] и заполните его, как показано на примере.

Входные данные: Программа получает на вход два числа n и m.
Выходные данные: Программа должна вывести полученный массив, отводя на вывод каждого числа ровно 3 символа.

Примеры

Входные данные Выходные данные
1 4 5
 20  19  18  17  16 
 15  14  13  12  11 
 10   9   8   7   6 
  5   4   3   2   1

ID 37052
12.25к
Темы: Двумерные массивы   

Даны числа n и m. Создайте массив A[n][m] и заполните его, как показано на примере.

Входные данные: Программа получает на вход два числа n и m.
Выходные данные: Программа должна вывести полученный массив, отводя на вывод каждого числа ровно 3 символа.

Примеры

Входные данные Выходные данные
1 4 5
 20  16  12   8   4 
 19  15  11   7   3 
 18  14  10   6   2 
 17  13   9   5   1 

ID 37059
12.25д
Темы: Двумерные массивы   

Даны числа n и m. Создайте массив A[n][m] и заполните его, как показано на примере.

Входные данные: Программа получает на вход два числа n и m.
Выходные данные: Программа должна вывести полученный массив, отводя на вывод каждого числа ровно 3 символа.

Примеры

Входные данные Выходные данные
1 4 5
  1   2   3   4   5 
 10   9   8   7   6 
 11  12  13  14  15 
 20  19  18  17  16 

ID 37060
12.25е
Темы: Двумерные массивы   

Даны числа n и m. Создайте массив A[n][m] и заполните его, как показано на примере.

Входные данные: Программа получает на вход два числа n и m.
Выходные данные: Программа должна вывести полученный массив, отводя на вывод каждого числа ровно 3 символа.

Примеры

Входные данные Выходные данные
1 4 5
  1   8   9  16  17 
  2   7  10  15  18 
  3   6  11  14  19 
  4   5  12  13  20 

ID 37073
12.25л
Темы: Двумерные массивы   

Даны числа n и m. Создайте массив A[n][m] и заполните его, как показано на примере.

Входные данные: Программа получает на вход два числа n и m.
Выходные данные: Программа должна вывести полученный массив, отводя на вывод каждого числа ровно 3 символа.

Примеры

Входные данные Выходные данные
1 4 5
 20  19  18  17  16 
 11  12  13  14  15 
 10   9   8   7   6 
  1   2   3   4   5 

ID 37074
12.25м
Темы: Двумерные массивы   

Даны числа n и m. Создайте массив A[n][m] и заполните его, как показано на примере.

Входные данные: Программа получает на вход два числа n и m.
Выходные данные: Программа должна вывести полученный массив, отводя на вывод каждого числа ровно 3 символа.

Примеры

Входные данные Выходные данные
1 4 5
  5   4   3   2   1 
  6   7   8   9  10 
 15  14  13  12  11 
 16  17  18  19  20 

ID 37075
12.25н
Темы: Двумерные массивы   

Даны числа n и m. Создайте массив A[n][m] и заполните его, как показано на примере.

Входные данные: Программа получает на вход два числа n и m.
Выходные данные: Программа должна вывести полученный массив, отводя на вывод каждого числа ровно 3 символа.

Примеры

Входные данные Выходные данные
1 4 5
 17  16   9   8   1 
 18  15  10   7   2 
 19  14  11   6   3 
 20  13  12   5   4 

ID 37076
12.25о
Темы: Двумерные массивы   

Даны числа n и m. Создайте массив A[n][m] и заполните его, как показано на примере.

Входные данные: Программа получает на вход два числа n и m.
Выходные данные: Программа должна вывести полученный массив, отводя на вывод каждого числа ровно 3 символа.

Примеры

Входные данные Выходные данные
1 4 5
  4   5  12  13  20 
  3   6  11  14  19 
  2   7  10  15  18 
  1   8   9  16  17 

ID 37077
12.25п
Темы: Двумерные массивы   

Даны числа n и m. Создайте массив A[n][m] и заполните его, как показано на примере.

Входные данные: Программа получает на вход два числа n и m.
Выходные данные: Программа должна вывести полученный массив, отводя на вывод каждого числа ровно 3 символа.

Примеры

Входные данные Выходные данные
1 4 5
 16  17  18  19  20 
 15  14  13  12  11 
  6   7   8   9  10 
  5   4   3   2   1 

ID 37078
12.25р
Темы: Двумерные массивы   

Даны числа n и m. Создайте массив A[n][m] и заполните его, как показано на примере.

Входные данные: Программа получает на вход два числа n и m.
Выходные данные: Программа должна вывести полученный массив, отводя на вывод каждого числа ровно 3 символа.

Примеры

Входные данные Выходные данные
1 4 5
 20  13  12   5   4 
 19  14  11   6   3 
 18  15  10   7   2 
 17  16   9   8   1 

ID 7128
Таблица чемпионата - 1
Темы: Двумерные массивы   

Дана таблица некоторого чемпионата. Элементы главной диагонали равны 888.  Каждый элемент массива, находящийся не на главной диагонали, может быть либо однозначным либо двузначным числом, запись которых образована цифрами, обозначающими колмичество забитых (первая цифра числа) и количество пропущенных (вторая цифра числа) в данном матче. 
Например: 32 - три забитых, два пропцщенных.
0 - ноль забитых, ноль пропущенных
5 - ноль забитых, пять пропущенных

Входные данные: Программа получает на вход число N <= 15, являющееся числом строк и столбцов в массиве. Далее во входном потоке идет N строк по N чисел, являющихся элементами массива.

Выходные данные: Программа должна вывести N строк по 2 числа в каждой: общее количество забитых и общее количество пропущенных каждой командой мячей

Входные данные Выходные данные
1
3
888 29 37 
92 888 57 
73 75 888 
5 16
14 9
14 8

ID 7127
Таблица чемпионата - 2
Темы: Двумерные массивы   

Дана таблица некоторого чемпионата. Элементы главной диагонали равны 8.  Каждый элемент массива, находящийся не на главной диагонали, может принимать следующие значения: 3 - если данная команда выиграла игру, 0 - если проиграла, 1 - если игра закончилась в ничью.

Входные данные: Программа получает на вход число N <= 15, являющееся числом строк и столбцов в массиве. Далее во входном потоке идет N строк по N чисел, являющихся элементами массива.

Выходные данные: Программа должна вывести N строк по 3 числа в каждой: количество выигрышей, количество ничьих и количество проигрышей для каждой команды. Первая строка соответствует первой команде  и т.д.

Входные данные Выходные данные
1
3
8 0 3 
3 8 1 
0 1 8  
1 0 1
1 1 0
0 1 1

ID 7126
Минимальный на диагоналях
Темы: Двумерные массивы   

В квадратном массиве размером NxN, где N - нечетное число. Наименьший элемент среди стоящих на главной и побочной диагоналях поменять местами с элементом, расположенным в левом нижнем углу массива. Если наименьших элементов несколько, то поменять тот у которого номер строки и столбца меньше.

Входные данные: Программа получает на вход число N <= 15, являющееся числом строк и столбцов в массиве. Далее во входном потоке идет N строк по N чисел, являющихся элементами массива.
Выходные данные: Программа должна вывродить на экран измененный массив

Входные данные Выходные данные
1
3
80 10 22 
81 90 13 
37 79 80  
80 10 37 
81 90 13 
22 79 80

ID 7125
Наибольший на диагоналях
Темы: Двумерные массивы   

В квадратном массиве размером NxN, где N - нечетное число. Наибольший элемент среди стоящих на главной и побочной диагоналях поменять местами с элементом, стоящим на пересечении этих диагоналей. Если наибольших элементов несколько, то поменять тот у которого номер строки и столбца меньше.

Входные данные: Программа получает на вход число N <= 15, являющееся числом строк и столбцов в массиве. Далее во входном потоке идет N строк по N чисел, являющихся элементами массива.
Выходные данные: Программа должна вывродить на экран измененный массив

Входные данные Выходные данные
1
3
89 10 79 
42 7 5 
94 32 68  
89 10 79 
42 94 5 
7 32 68

ID 7124
Сумма максимума и минимума
Темы: Двумерные массивы   

Входные данные: Программа получает на вход число N <= 15, являющееся числом строк и столбцов в массиве. Далее во входном потоке идет N строк по N чисел, являющихся элементами массива.

Выходные данные: Программа должна вывести одно число - сумму максимального элемента главной диагонали и минимального элемента побочной диагонали

Примеры
Входные данные Выходные данные
1
3
11 24 19 
8 21 10 
16 24 14
37

ID 7123
Сумма на диагоналях
Темы: Двумерные массивы   

Входные данные: программа получает на вход число N <= 15, являющееся числом строк и столбцов в массиве. Далее во входном потоке идет N строк по N чисел, являющихся элементами массива.

Входные данные: программа должна вывести
1) слово YES - если сумма элементов, расположенных на главной диагонали, больше суммы элементов расположенных на побочной диагонали
2) слово NO - если условие 1 не выполняется

Примеры
Входные данные Выходные данные
1
3
24 23 5 
27 19 6 
15 16 25 
YES
2
3
17 20 18 
25 9 26 
30 4 11
NO

ID 7122
Среднее арифметическое на побочной диагонали
Темы: Двумерные массивы   

Входные данные: программа получает на вход число N <= 15, являющееся числом строк и столбцов в массиве. Далее во входном потоке идет N строк по N чисел, являющихся элементами массива.

Выходные данные: программа должна вывести одно число - среднее арифметическое элементов побочной диагонали двумерного массива.

Примеры
Входные данные Выходные данные
1
3
5 26 17 
20 5 29 
29 23 14  
17.000000

ID 7121
Среднее арифметическое на главной диагонали
Темы: Двумерные массивы   

Входные данные: программа получает на вход число N <= 15, являющееся числом строк и столбцов в массиве. Далее во входном потоке идет N строк по N чисел, являющихся элементами массива.

Выходные данные: программа должна вывести одно число - среднее арифметическое элементов главной диагонали двумерного массива.

Примеры
Входные данные Выходные данные
1
5
23 23 2 5 24 
7 21 15 12 18 
14 16 6 19 15 
23 5 23 9 24 
5 7 12 18 28 
17.400000

ID 7120
Сумма диагональных элементов
Темы: Двумерные массивы   

Входные данные: программа получает на вход число N <= 15, являющееся числом строк и столбцов в массиве. Далее во входном потоке идет N строк по N чисел, являющихся элементами массива.

Выходные данные: программа должна вывести строку, в которой через пробел указаны числа являющиеся суммой тех двух элементов каждой строки, которые принадлежат главной и побочной диагоналям

Примеры
Входные данные Выходные данные
1
5
16 17 29 17 30 
26 12 14 12 2 
23 6 30 27 13 
15 7 28 20 2 
11 16 21 26 24
46 24 30 27 35

ID 7119
Симметричный массив
Темы: Двумерные массивы   

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

Входные данные: программа получает на вход число N <= 15, являющееся числом строк и столбцов в массиве. Далее во входном потоке идет n строк по N чисел, являющихся элементами массива.

Выходные данные: программа должна выводить слово yes для симметричного массива и слово no для несимметричного.

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

ID 6025
Обработка столбца в матрице - 2
Темы: Двумерные массивы   

Дан двумерный массив A[N][M] ( 2<=N<=20; M 2<=M<=20).
В первой строке вводятся через пробел количество строк - число от 0 до N-1, и количество столбцов - число от 0 до M-1.
Во второй строке вводится число s (0<=s<=20)
Далее идет ввод элементов массива построчно
Определить cумму всех элементов s-го столбца массива.

Примеры

Входные данные Выходные данные
1 2 2
1
5 5
1 2
7
2 2 3
0
1 5 2
3 4 0
4

ID 6029
Поиск требуемой строки
Темы: Двумерные массивы   

В метании молота состязается n спортcменов. Каждый из них сделал m бросков. (n<=20, m<=20)
Победителем считается тот спортсмен, у которого сумма результатов по всем броскам максимальна. 
Если перенумеровать спортсменов числами от 0 до n-1, а попытки каждого из них – от 0 до m-1, то на вход программа получает массив A[n][m], состоящий из неотрицательных целых чисел (0<A[n][m]<500). Программа должна определить номер строки с максимальной суммой чисел и вывести на экран эту сумму и номер строки, для которой достигается эта сумма.


Входные данные: Программа получает на вход два числа n и m, являющиеся числом строк и столбцов в массиве. Далее во входном потоке идет n строк по m чисел, являющихся элементами массива.

Выходные данные: Программа должна вывести  2 числа: сумму и номер строки, для которой эта сумма достигается. Если таких строк несколько, то выводится номер наименьшей из них. 

Примеры

Входные данные Выходные данные
1 4 3
5 6 7
6 6 7
7 6 6
4 3 5
19 1

ID 6030
Максимум в матрице - 1
Темы: Двумерные массивы   

В метании молота состязается n спортcменов. Каждый из них сделал m бросков. Победителем соревнований объявляется тот спортсмен, у которого максимален наилучший результат по всем броскам. Таким образом, программа должна найти значение максимального элемента в данном массиве, а также его индексы (то есть номер спортсмена и номер попытки).


Входные данные: Программа получает на вход два числа n и m (1<=n<=20;  1<=n<=20), являющиеся числом строк и столбцов в массиве. Далее во входном потоке идет n строк по m чисел, являющихся элементами массива.

Выходные данные: Программа выводит значение максимального элемента, затем номер строки и номер столбца, в котором он встречается. Если в массиве несколько максимальных элементов, то нужно вывести минимальный номер строки, в которой встречается такой элемент, а если в этой строке таких элементов несколько, то нужно вывести минимальный номер столбца. 

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

ID 37169
Игра "Жизнь". Простой вариант
Темы: Двумерные массивы   

В некоторых клетках квадрата \( N\ х\ N\) живут микроорганизмы (не более одного в одной клетке). Каждую секунду происходит следующее:
– все микроорганизмы, у которых менее 2-х соседей, умирают от скуки (соседями называются микроорганизмы, живущие в клетках, имеющих общую сторону или вершину);
– все микроорганизмы, у которых более 3-х соседей, умирают от перенаселенности;
– на всех пустых клетках, у которых ровно в трех соседних клетках жили микроорганизмы, появляются новые микроорганизмы.
Все изменения происходят одновременно, то есть для каждой клетки сначала выясняется ее судьба, а затем происходят изменения сразу во всех клетках.
Требуется по данной конфигурации определить, во что она превратится через \(T\) секунд.

Входные данные: В первой строке вводятся два натуральных числа –\( N\) (\(1 \leq N \leq 10\)) и \(T\) (\(1 \leq T \leq 100\)). Далее записано \( N\) строчек по \( N\) чисел, описывающих начальную конфигурацию (0 – пустая клетка, 1 – микроорганизм). Числа в строках разделены пробелами.
Выходные данные: Требуется вывести \( N\) строк по \( N\) чисел – описание конфигурации через T секунд (в том же формате, как и во входных данных).

Примеры
Входные данные Выходные данные
1 3 1
1 0 1
1 0 1
1 0 1
0 0 0
1 0 1
0 0 0
2 2 2
1 1
1 1
1 1
1 1
3 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

ID 6026
Обработка строки в матрице - 2
Темы: Двумерные массивы   

Дан двумерный массив A[N][M] ( 2<=N<=20; M 2<=M<=20).
В первой строке вводятся через пробел количество строк - число от 0 до N-1, и количество столбцов - число от 0 до M-1.
Во второй строке вводится число  k
Далее идет ввод элементов массива построчно
Определить среднее арифметическое элементов k-ой строки массива.

Примеры

Входные данные Выходные данные
1 2 2
1
5 5
1 2
1.500000
2 2 3
0
1 5 2
3 4 0
2.666666

ID 6027
Обработка строки в матрице - 1
Темы: Двумерные массивы   

Дан двумерный массив A[N][M] ( 2<=N<=20; M 2<=M<=20).
В первой строке вводятся через пробел количество строк - число от 0 до N-1, и количество столбцов - число от 0 до M-1.
Во второй строке вводится число k
Далее идет ввод элементов массива построчно
Определить количество элементов из последней строки кратных k.

Примеры

Входные данные Выходные данные
1 2 2
1
5 5
1 2
2
2 2 3
2
1 5 2
3 4 0
2

ID 6028
Обработка столбца в матрице - 2
Темы: Двумерные массивы   

Дан двумерный массив A[N][M] ( 1<=N<=20; M 1<=M<=20).
В первой строке вводятся через пробел количество строк - (строки массива нумеруются от 0 до N-1), и количество столбцов - (столбцы массива нумеруются от 0 до M-1)
Далее идет ввод элементов массива построчно
Определить количество двухзначных чисел из последнего столбца.

Примеры

Входные данные Выходные данные
1 2 2
5 15
11 22
2
2 2 3
11 15 2
 3   4 10
1

ID 36994
Поиск в матрице
Темы: Двумерные массивы   

Напишите программу, которая определяет, сколько раз встречается в матрице элемент, равный K .

Входные данные
В первой строке записаны через пробел размеры матрицы: количество строк N и количество столбцов M (\(1 <= N , M <= 100\)). В следующих N строках записаны строки матрицы, в каждой – по M натуральных чисел, разделённых пробелами. В следующей строке записано целое число K.

Выходные данные
Программа должна вывести количество элементов матрицы, равных K.
 

Пример
Входные данные Выходные данные
1 4 5
1 2 3 4 5
6 12 8 9 10
11 12 12 14 15
16 17 18 12 20
12
4

ID 36995
Минимум и максимум в матрице
Темы: Двумерные массивы   

Напишите программу, которая находит минимальный и максимальный элементы в матрице. Если в матрице есть несколько одинаковых минимальных (максимальных) элементов, нужно найти индексы первого такого элемента в порядке обхода по строкам: сверху вниз, слева направо.

Входные данные 
В первой строке записаны через пробел размеры матрицы: количество строк N и количество столбцов M (\(1 <= N , M <= 100\)). В следующих N строках записаны строки матрицы, в каждой – по M натуральных чисел, разделённых пробелами.


Выходные данные 
В первой строке программа должна вывести индексы минимального элемента (строку и столбец), а затем – его значение. Нумерация строк и столбцов начинается с единицы. Все числа разделены пробелами. Во второй строке выводится информация о максимальном элементе в том же формате.
 

Пример
Входные данные Выходные данные
1 4 5
1 3 2 54 24
75 12 3 46 9
13 26 56 9 12
14 90 97 6 34
1 1 1
4 3 97

ID 36998
Вывод столбцов с максимумом
Темы: Двумерные массивы   

Напишите программу, которая находит в матрице столбцы, в которых есть элемент, равный максимальному.

Входные данные 
В первой строке записаны, через пробел, размеры матрицы: количество строк N и количество столбцов M (\(1 <= N , M <= 100\)). В следующих N строках записаны строки матрицы, в каждой – по M натуральных чисел, разделённых пробелами.

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

 
Примеры
Входные данные Выходные данные
1 4 5
1 897 2 54 234
75 12 3 46 9
13 26 56 9 12
14 90 897 6 34
897 12 26 90
2 3 56 897

ID 27238
Строка с минимальной суммой
Темы: Двумерные массивы   

Напишите программу, которая находит в матрице строку с минимальной суммой.

Входные данные
В первой строке записаны через пробел размеры матрицы: количество строк N и количество столбцов M (\(1 <= N, M <= 100 \)). В следующих N строках записаны строки матрицы, в каждой – по M натуральных чисел, разделённых пробелами.

Выходные данные
Программа должна вывести все элементы найденной строки с минимальной суммой, разделив их пробелами. Если строк с одинаковой минимальной суммой несколько, нужно выбрать из них строку с минимальным индексом.
 

Примеры
Входные данные Выходные данные
1 4 5
1 3 2 54 234
75 12 3 46 9
13 26 56 9 12
14 90 897 6 34
13 26 56 9 12

ID 36996
Подсчет по сумме
Темы: Двумерные массивы   

Напишите программу, которая определяет, сколько в матрице есть -значных чисел, сумма цифр каждого из которых кратна .

Входные данные
В первой строке записаны, через пробел, размеры матрицы: количество строк N и количество столбцов M (\(1 <= N , M <= 100\)). В следующих N строках записаны строки матрицы, в каждой – по M натуральных чисел, разделённых пробелами. Затем в двух разных строках вводятся числа K и R .

Выходные данные
Программа должны вывести одно число – количество K -значных чисел, сумма цифр каждого из которых кратна R .

 
Пример
Входные данные Выходные данные
1 5 5
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25
2
3
5

ID 27237
Магический квадрат?
Темы: Двумерные массивы   

Магическим квадратом порядка N называется квадратная матрица размера NхN , составленная из чисел 1, 2, ..., NхN так, что суммы по каждому столбцу, каждой строке и каждой из двух больших диагоналей равны между собой. Напишите программу, которая проверяет, является ли заданная квадратная матрица магическим квадратом.

Входные данные 
В первой строке вводится размер матрицы N (\(0<N<=25\)) . В следующих N строках вводятся строки матрицы, по N значений в каждой, разделённые пробелами.

Выходные данные
Программа должна вывести слово 'YES', если матрица является магическим квадратом, и слово 'NO', если не является.

 
Пример
Входные данные Выходные данные
1 3
8 1 6
3 5 7
4 9 2
YES

ID 27235
Нестандартное заполнение - 1. Диагонали
Темы: Двумерные массивы   

Напишите программу, которая заполняет матрицу неотрицательными числами по диагоналям (см. пример). Значение элемента матрицы равно расстоянию от левого верхнего угла матрицы.

Входные данные
Во входной строке записаны через пробел размеры матрицы: количество строк N и количество столбцов M (\(1 <=N, M <= 100\)).

Выходные данные
Программа должна вывести полученную матрицу по строкам.

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

ID 27236
Нестандартное заполнение - 2. Змейка
Темы: Двумерные массивы   

Напишите программу, которая заполняет матрицу из N строк и M столбцов натуральными числами змейкой, как показано в примере.

Входные данные
Входная строка содержит числа N и M, разделённые пробелом.

Выходные данные
Программа должна вывести матрицу, заполненную заданным способом.

 
Пример
Входные данные Выходные данные
1 4 5 1 2 3 4 5
10 9 8 7 6
11 12 13 14 15
20 19 18 17 16

ID 27234
Простая задача
Темы: Двумерные массивы   

Дан двумерный массив N*M (\(0<N,M<=20\)).
Значения элементов массива вводятся с клавиатуры
Вывести в первой строке все угловые элементы массива, начиная с левого верхнего угла и далее, двигаясь по часовой стрелке.

Входные данные
В первой строке задается размер массива. N - количество строк, M - количество столбцов (\(0<N,M<=20\))
Далее идут N строк по M чисел в каждой строке - элементы двумерного массива (каждый элемент по модулю не больше 50)

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

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

ID 37026
Квадратная матрица
Темы: Двумерные массивы   

Дано число n. Создайте двумерный массив размером nхn и заполните его по следующему правилу. На главной диагонали должны быть записаны числа 0. На двух диагоналях, прилегающих к главной, числа 1. На следующих двух диагоналях числа 2 и т.д.

Входные данные
На вход подается одно единственное число n.

Выходные данные
Выведите на экран заполненную матрицу.
 

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

ID 37030
Побочная диагональ
Темы: Двумерные массивы   

Дано число n. Создайте массив размером nхn и заполните его по следующему правилу:

Числа на диагонали, идущей из правого верхнего в левый нижний угол, равны 1.
Числа, стоящие выше этой диагонали, равны 0.
Числа, стоящие ниже этой диагонали, равны 2.

Полученный массив выведите на экран. Числа в строке разделяйте одним пробелом.

Входные данные
На вход подается одно число n.

Выходные данные
Выведите на экран заполненный массив.
 
Пример
Входные данные Выходные данные
1 4 0 0 0 1
0 0 1 2
0 1 2 2
1 2 2 2

ID 37032
Симметричный массив
Темы: Двумерные массивы   

Дано число n и двумерный массив размером nхn. Проверьте, является ли этот двумерный массив симметричным относительно главной диагонали. Выведите слово “YES”, если двумерный массив симметричный, и слово “NO” - в противном случае.

Входные данные
В первой строке задается число n - размер двумерного массива. Далее идут n строк по n чисел в каждой - элементы двумерного массива.

Выходные данные
Выведите на экран слово "YES", если массив симметричен, или "NO" - в противном случае
 

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

ID 37033
Диагональ ниже главной
Темы: Двумерные массивы   

Дан квадратный двумерный массив размером nхn и число k. Выведите элементы k-й по счету диагонали ниже главной диагонали (т.е. если k=1, то нужно вывести элементы первой диагонали, лежащей ниже главной, если k=2, то второй диагонали и т.д.).

Значение k может быть отрицательным, например, если k=−1, то нужно вывести значение первой диагонали, лежащей выше главной. Если k=0, то нужно вывести элементы главной диагонали.

Входные данные 
Программа получает на вход число n, затем идут элементы массива  n строк по n символов в каждой строке, затем с новой строки, число k.

Выходные данные
Элементы k-й по счету диагонали ниже главной диагонали, через пробел, в одной строке.
 
Примеры
Входные данные Выходные данные
1 4
1 2 3 4
5 6 7 8
0 1 2 3
4 5 6 7
1
5 1 6
2 4
1 2 3 4
5 6 7 8
0 1 2 3
4 5 6 7
-2
3 8

ID 37034
Обмен диагоналей
Темы: Двумерные массивы   

Дан квадратный массив. Поменяйте местами элементы, стоящие на главной и побочной диагоналях, при этом каждый элемент должен остаться в том же столбце (то есть в каждом столбце нужно поменять местами элемент на главной диагонали и на побочной диагонали).

Входные данные
На вход подается число n  - размер квадратного массива. Далее идут n строк по n чисел в каждой - элементы массива.

Выходные данные
Выведите на экран массив после преобразования.
 

Пример
Входные данные Выходные данные
1 3
1 2 3
4 5 6
7 8 9
7 2 9
4 5 6
1 8 3

ID 37038
Квадранты
Темы: Двумерные массивы   

Заполните квадратный массив целыми числами по образцу. На главной и побочных диагоналях стоят нули, эти диагонали делят массив на четыре части. В верхней части записаны единицы, в правой записаны двойки, в нижней записаны тройки, в левой записаны четверки.

Входные данные
На вход подается одно число - размер квадратного массива.

Выходные данные
Выведите на экран заполненную квадратную матрицу.
 

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

ID 37083
Замена столбца на элементы массива
Темы: Двумерные массивы   

Дана матрица размером NxM и массив чисел размером N. В данной матрице заменить все элементы столбца с максимальной суммой элементов на элементы заданного массива чисел. Если таких столбцов несколько, то заменить элементы в столбце с меньшим индексом.

Входные данные
В первой строке задаются числа N и M (\(0<N,M<=10\)). Далее идут N строк по M чисел в каждой. Каждое число по модулю не более 100. В последней строке идут N чисел массива.

Выходные данные 
Выведите на экран преобразованную матрицу, отводя под каждый элемент три знакоместа.
 

Пример
Входные данные Выходные данные
1 3 4
52 16 61 93 
5 5 33 41 
37 34 14 16 
76 69 26
 52  16  61  76 
  5   5  33  69 
 37  34  14  26 

ID 37085
Обмен строк
Темы: Двумерные массивы   

Дана матрица размером NxM и два числа k1 и k2. Поменяйте местами строки с индексами k1 и k2.

Входные данные
В первой строке задаются числа N и M (\(0<N,M<=10\)). Далее идут N строк по M чисел в каждой. Каждое число по модулю не более 100. Далее с новой строки идут два числа k1, k2 (\(0<k1,k2<=N\)).

Выходные данные
Выведите на экран преобразованную матрицу, отводя под каждый элемент три знакоместа.
 

Пример
Входные данные Выходные данные
1 4 5
72 50 18 79 74 
48 93 27 9 76 
33 76 69 59 58 
19 65 53 90 77 
2 0
 33  76  69  59  58 
 48  93  27   9  76 
 72  50  18  79  74 
 19  65  53  90  77

ID 37087
Удаление строк
Темы: Двумерные массивы    Двумерные массивы   

В двумерном массиве хранятся результаты (время в минутах), показанные каждым из N автогонщиков на каждом из 10-ти этапов соревнований "Формула-1" (в нулевой строке - результаты первого гонщика, в первой - второго и т.д.). После десятого этапа гонщик с порядковым номером K выбыл из соревнований. Судейской коллегией было принято решение удалить результаты данного участника из таблицы.
Измените массив соответствующим образом и выведите его на экран.

Под удалением строки в двумерном массиве будем понимать:
1) исключение этой строки из массива путем смещения всех следующих за ней строк на одну вверх;
2) присваивание всем элементам последней строки значения 0 (или уменьшение количества строк на 1).

Входные данные
В первой строке задаётся число N (\(0<N<=30\)). Далее идут N строк по 10 чисел в каждой. Каждое число по модулю не более 100. Далее с новой строки идет число K (\(1<=K<=N\)).

Выходные данные 
Выведите на экран преобразованную матрицу, отводя под каждый элемент три знакоместа.
 

Пример
Входные данные Выходные данные
1 5
38 43 82 95 20 100 99 83 77 42 
94 92 74 30 93 75 99 6 79 68 
4 20 25 54 15 31 81 39 79 76 
62 97 14 40 70 31 3 84 33 74 
99 30 91 15 41 54 87 31 71 74 
3
 38  43  82  95  20 100  99  83  77  42 
 94  92  74  30  93  75  99   6  79  68 
 62  97  14  40  70  31   3  84  33  74 
 99  30  91  15  41  54  87  31  71  74 

ID 37087
Удаление строк
Темы: Двумерные массивы    Двумерные массивы   

В двумерном массиве хранятся результаты (время в минутах), показанные каждым из N автогонщиков на каждом из 10-ти этапов соревнований "Формула-1" (в нулевой строке - результаты первого гонщика, в первой - второго и т.д.). После десятого этапа гонщик с порядковым номером K выбыл из соревнований. Судейской коллегией было принято решение удалить результаты данного участника из таблицы.
Измените массив соответствующим образом и выведите его на экран.

Под удалением строки в двумерном массиве будем понимать:
1) исключение этой строки из массива путем смещения всех следующих за ней строк на одну вверх;
2) присваивание всем элементам последней строки значения 0 (или уменьшение количества строк на 1).

Входные данные
В первой строке задаётся число N (\(0<N<=30\)). Далее идут N строк по 10 чисел в каждой. Каждое число по модулю не более 100. Далее с новой строки идет число K (\(1<=K<=N\)).

Выходные данные 
Выведите на экран преобразованную матрицу, отводя под каждый элемент три знакоместа.
 

Пример
Входные данные Выходные данные
1 5
38 43 82 95 20 100 99 83 77 42 
94 92 74 30 93 75 99 6 79 68 
4 20 25 54 15 31 81 39 79 76 
62 97 14 40 70 31 3 84 33 74 
99 30 91 15 41 54 87 31 71 74 
3
 38  43  82  95  20 100  99  83  77  42 
 94  92  74  30  93  75  99   6  79  68 
 62  97  14  40  70  31   3  84  33  74 
 99  30  91  15  41  54  87  31  71  74 

ID 37088
Удаление столбцов
Темы: Двумерные массивы   

В двумерном массиве хранятся результаты (время в минутах), показанные каждым из \(N\) велогонщиков на каждом из 12-ти этапов соревнований (в нулевом столбце - результаты первого этапа, в первом - второго и т.д.) Судейской коллегией результаты K-го этапа были признаны недействительными и были удалены из таблицы.
Измените массив соответствующим образом и выведите его на экран.

Под удалением столбца в двумерном массиве будем понимать:
1) исключение этого столбца из массива путем смещения всех следующих за ним столбцов на один влево;
2) присваивание всем элементам последнего столбца значения 0 (или уменьшение количества столбцов на 1).

Входные данные
В первой строке задаётся число N (0<N<=30). Далее идут N строк по 12 чисел в каждой. Каждое число по модулю не более 100. Далее с новой строки идет число K (1<=K<=12).

Выходные данные
Выведите на экран преобразованную матрицу, отводя под каждый элемент три знакоместа.
 

Пример
Входные данные Выходные данные
1 4
65 2 22 62 41 18 80 15 35 20 21 27 
7 28 35 98 15 27 87 95 73 45 26 28 
1 99 11 69 11 13 80 78 3 53 76 73 
87 37 11 85 72 33 59 79 61 53 80 67 
4
 65   2  22  41  18  80  15  35  20  21  27 
  7  28  35  15  27  87  95  73  45  26  28 
  1  99  11  11  13  80  78   3  53  76  73 
 87  37  11  72  33  59  79  61  53  80  67 

ID 37084
Циклический сдвиг построчно
Темы: Двумерные массивы   

Каждую строку заданной прямоугольной матрицы NxM сдвинуть циклически вправо на количество позиций, равных номеру строку (нумерация строк и столбцов с 0). Вывести на экран преобразованную матрицу.

Входные данные
В первой строке находятся два числа N и M (\(0 < N,M <= 10\)). Далее идут N строк по M чисел в каждой - элементы матрицы (каждый элемент не более 100 по модулю).

Выходные данные
Вывести измененную матрицу. На каждый элемент в выводе отводить ровно 3 символа (знакоместа).

Оформите сдвиг вправо на K позиций в виде подпрограммы.
 

Пример
Входные данные Выходные данные
1 3 4
47 63 22 75 
69 69 12 70 
70 90 13 31 
 47  63  22  75 
 70  69  69  12 
 13  31  70  90 

ID 37086
Обмен столбцов
Темы: Двумерные массивы   

Дана матрица размером NxM и два числа k1 и k2. Выполните циклическую перестановку столбцов влево, находящихся между столбцами k1 и k2 (включая столбцы k1 и k2, т.е. столбец k1 должен оказаться на месте столбца k2, столбец k2 не месте столбца k2-1 и т.д.).

Входные данные
В первой строке задаются числа N и M (\(0<N,M<=10\)). Далее идут N строк по M чисел в каждой. Каждое число по модулю не более 100. Далее с новой строки идут два числа k1, k2 (\(0<k1,k2<=M\)).

Выходные данные
Выведите на экран преобразованную матрицу, отводя под каждый элемент три знакоместа.
 

Пример
Входные данные Выходные данные
1 3 4
56 32 94 12 
15 72 51 60 
43 4 97 38 
0 2
 32  94  56  12 
 72  51  15  60 
  4  97  43  38 

ID 37089
Вставка столбцов
Темы: Двумерные массивы   

В двумерный массив записаны годовые оценки по десяти предметам каждого из N учеников класса (в нулевом столбце - оценки по первому предмету, в первом - по второму и т.д.), но по ошибке забыли вписать в массив оценки еще по одному предмету, который должен находиться в столбце K. Измените массив так, чтобы он был заполнен надлежащим образом. 

Под добавлением столбца в двумерный массив будем понимать:
1) увеличение числа столбцов массива на 1;
2) смещение всех столбов после K-го на один вправо;
3) присваивание заданных значений элементам K-го столбца.

Входные данные
В первой строке задаётся число N (0<N<=30). Далее идут N строк по 10 чисел в каждой. Каждое число в диапазоне от 2 до 5. В следующей строке идет число K (1<=K<=10). Далее, в последней строке (без пропуска строк) идет N чисел, оценки соответствующего ученика по новому предмету.

Выходные данные
Выведите на экран преобразованную матрицу, отделяя каждый элемент одним пробелом.
 

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

ID 37082
Изменение строки с максимумом
Темы: Двумерные массивы   

В матрице размером NхM заменить на значение -1 все элементы тех строк, в которых находится максимальный элемент.

Входные данные
В первой строке находятся два числа N и M (\(0 < N,M <= 10\)). Далее идут N строк по M чисел в каждой - элементы матрицы (каждый элемент не более 100 по модулю).

Выходные данные
Вывести измененную матрицу. На каждый элемент в выводе отводить ровно 3 символа (знакоместа).
 

Пример
Входные данные Выходные данные
1 5 5
15 68 54 79 89 
91 57 21 70 24 
14 22 5 26 76 
51 59 92 98 96 
50 62 50 58 1 
 15  68  54  79  89 
 91  57  21  70  24 
 14  22   5  26  76 
 -1  -1  -1  -1  -1 
 50  62  50  58   1 

ID 38140
Комфорт для коров
Темы: Циклы    Двумерные массивы   

Пастбище Фермера Джона может быть представлено как огромная 2D-решётка ячеек (огромная шахматная доска). Изначально пастбище пустое.
Фермер Джон добавит N (1≤N≤105) коров на пастбище одну за одной. i-ая корова занимает ячейку (xi,yi), которая отличается от ячеек, занятых всеми другими коровами (0≤xi,yi≤1000).

Говорят, что корове "комфортабельно", если по горизонтали и вертикали она имеет ровно три других коровы. Фермер Джон хочет посчитать, скольким коровам комфортабельно на его пастбище. Для каждого i в интервале 1…N, выведите общее количество коров, которым комфортабельно после того, как i-ая корова добавлена на пастбище.

Входные данные: 
Первая строка содержит одно целое число N. Каждая из последующих N строк содержит два разделённых пробелом целых числа, указывающих (x,y) - координаты ячейки коровы. Гарантируется, что все ячейки различны.
Выходные данные: 
i-ая строка вывода должна содержать общее количество коров, которым комфортабельно после добавления i-ой коровы на пастбище.
 

Примеры
Входные данные Выходные данные Пояснение
1 8
0 1
1 0
1 1
1 2
2 1
2 2
3 1
3 2
0
0
0
1
0
0
1
2
После того, как добавлены первые 4 коровы, корове в ячейке (1,1) стало комфортабельно.
После того, как добавлены первые 7 коров, корове в ячейке (2,1) стало комфортабельно.
После того, как добавлены первые 8 коров, корове в ячейках (2,1) и (2,2) стало комфортабельно.

ID 38194
Шахматная доска
Темы: Двумерные массивы    Клеточная геометрия   

Из шахматной доски по границам клеток выпилили связную (не распадающуюся на части) фигуру без дыр. Требуется определить ее периметр.

Входные данные
Сначала вводится число N (1 ≤ N ≤ 64) – количество выпиленных клеток. В следующих N строках вводятся координаты выпиленных клеток, разделенные пробелом (номер строки и столбца – числа от 1 до 8). Каждая выпиленная клетка указывается один раз.

Выходные данные
Выведите одно число – периметр выпиленной фигуры (сторона клетки равна единице).

Примеры
Входные данные Выходные данные Пояснения
1 3
1 1
1 2
2 1
8 Вырезан уголок из трех клеток. Сумма длин его сторон равна 8.
2 1
8 8
4 Вырезана одна клетка. Ее периметр равен 4.

ID 38202
Шахматное домино
Темы: Двумерные массивы   

Комплект шахматного домино состоит из 32 костяшек 2x1, каждая из квадратов которой окрашен в черный или белый цвет (часть костяшек состоит из двух белых квадратов, часть – из двух черных, а часть из одного белого и одного черного). Комплект такого домино выложен на шахматную доску. Разрешается поворачивать костяшки домино на 180 градусов (менять местами их квадраты), оставляя каждую костяшку на своем месте. Требуется выяснить, можно ли так повернуть часть костей домино, чтобы в каждом горизонтальном ряду были квадраты только одного цвета.


Входные данные
Вводится 8 строк по 8 чисел. Каждое число соответствует номеру доминошки, которая покрывает данную клетку. Число положительное, если квадрат доминошки белый и отрицательное – если черный.


Выходные данные
Требуется вывести одно слово – YES или NO (заглавными буквами).

Примеры
Входные данные Выходные данные
1 1   2   2   7   7   8   8   9
  1   3   6  10  10  11  11   9
  4   3   6  31  31  24  23  12
  4   5   5  30  32  24  23  12
 28  29  29  30  32  25  22  13
 28  27  27  26  26  25  22  13
 18  19  19  20  20  21  21  14
 18  17  17  16  16  15  15  14
YES

Примечание:
Доминошки нумеруются числами от 1 до 32 в произвольном порядке.
 

ID 38222
Магический квадрат
Темы: Двумерные массивы   

Магическим квадратом называют таблицу, в которой записаны числа 123…  по одному разу, так что сумма чисел в каждой строке и в каждом столбце равные. Мы расскажем вам об одном из методов построения магических квадратов (его называют сиамским). Он годится только для построения квадратов с нечетной стороной (3355…) .

Поставим число 1 в верхнюю клетку центрального столбца. Далее будем двигаться по диагонали вправо-вверх, расставляя в клетки последовательно числа 234… . Если мы вышли за пределы таблицы вверх, то нужно перейти к нижней клетке того же столбца и продолжить с нее. Если мы вышли за правую границу, нужно перейти к левой клетке той строки, куда мы должны были попасть. Если же мы одновременно вышли и вверх, и вправо, то нужно перейти в левую нижнюю клетку квадрата.

Если в следующей клетке на нашем пути уже стоит число, то вместо хода “вправо-вверх” нужно сделать ход “вниз” (опять же, если мы при этом выйдем за границы квадрата, нужно перейти к верхней клетке того же столбца). Примеры для квадратов 33 и 55 показаны на рисунках.



Входные данные
На вход подается одно натуральное нечетное число N, не превосходящее 30 – размер квадрата.

Выходные данные
Выведите числа, записанные в квадрате. Выравнивать числа по столбцам не обязательно. Обратите внимание: требуется вывести именно магический квадрат, полученный применением указанного метода.

Примеры
Входные данные Выходные данные
1 3 8 1 6 
3 5 7 
4 9 2 
2 5 17 24 1 8 15 
23 5 7 14 16 
4 6 13 20 22 
10 12 19 21 3 
11 18 25 2 9 

ID 38252
Муравьиная ферма
Темы: Двумерные массивы   

На прошлый день рождения Олегу подарили муравьиную ферму и трех больших муравьев для нее. Ферма представляет собой поле размером a × b клеток. Клетка с координатой (1, 1) находится в левом верхнем углу. Вскоре он заметил, что передвигаясь по своему вольеру, муравьи оставляют на белом песке следы разных цветов. На протяжении нескольких месяцев Олег наблюдал за своей фермой и, наконец, смог строго описать происходящее в вольере.

Клетки бывают четырех цветов:

  • белая (это значит, что клетка не покрашена ни одним из муравьев, обозначается цифрой 0)
  • красная (это — цвет следа первого муравья, обозначается цифрой 1)
  • желтая (это — цвет следа второго муравья, обозначается цифрой 2)
  • зеленая (это — цвет следа третьего муравья, обозначается цифрой 3)
Муравей умеет оставлять на клетке свой след, стирать с нее все следы, поворачиваться и делать шаг вперед. То, как он изменит цвет клетки и куда он повернется, зависит только от цвета клетки, на которой он сейчас стоит. Опишем один ход муравья.

Если муравей стоит на белой клетке, то он:
  • красит ее в свой цвет
  • поворачивается на 90°  вправо и делает шаг вперед
Если же муравей стоит не на белой клетке, то он:
  • стирает с нее след (то есть красит клетку в белый цвет)
  • поворачивается на 90º влево и делает шаг вперед
Если на пути муравья встречается граница фермы, шаг вперед он не делает.

Каждую минуту все три муравья по очереди делают один ход, причем сначала ходит первый, потом второй, потом третий.

Утром, уходя в школу, Олег чистит вольер так, что в начальный момент времени песок на всей ферме белый (то есть на нем нет никаких следов). Однако перемещения муравьев такие интересные, что мальчик не может нормально учиться, а вместо этого думает о своих любимцах. Сидя на занятиях, он старается понять, какой узор он увидит, когда вернется домой. Перед тем, как уйти на учебу, он записывает координаты всех своих питомцев. Олегу известно, что дома он будет ровно через T минут. Для того, чтобы Олег не отвлекался во время занятий на размышления о муравьях, напишите программу, которая сама воспроизведет рисунок, который получится на песке вольера через T минут.

Входные данные
В первой строке вводятся 3 числа a, b, T (1 ≤ a ≤ 100, 1 ≤ b ≤ 100, 1 ≤ T ≤ 103) — высота вольера, ширина вольера и время, которое Олега не будет дома, соответственно. Следующие три строки содержат описание положения муравьев. В каждой строке записано по 2 числа i, j (1 ≤ i ≤ a, 1 ≤ j ≤ b) — координаты муравьев (сначала записан номер строки, а затем номер столбца), причем в первой из строчек записаны координаты первого муравья, во второй — второго, а в третьей — третьего. Гарантируется, что в одной и той же клетке изначально не находилось двух муравьев. Изначально все муравьи смотрят вверх.

Выходные данные
Выведите состояние поля на момент времени T: a строк по b чисел в каждой через пробел. Каждое число обозначает цвет следа, оставленного в данной клетке вольера.

ID 38259
"Сапер" с подсказками
Темы: Двумерные массивы   

На весенних каникулах Оля долго обдумывала свое поведение и решила в четвертой четверти заниматься учебой побольше. Но уже первый урок биологии в новой четверти уничтожил все Олины благие намерения. Оле скучно, просто невыносимо скучно. От нечего делать она начала играть на своем телефоне в известную игру «Сапер».

На всякий случай напомним, в чем заключается эта игра. Игра происходит на поле размером N × M клеток, некоторые из которых «заминированы». Целью игры является открытие всех клеток, не содержащих мины.

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

Оля играет в версию «Сапера» со встроенными подсказками. Одна из подсказок, «Показать ошибки», работает следующим образом. Если по соседству с клеткой, в которой записано некоторое число, находится больше флажков, чем может соседствовать с этой клеткой (то есть больше флажков, чем число, записанное в клетке), все флажки вокруг этой клетки подсвечиваются желтым цветом. Другие ошибки эта подсказка находить не умеет, иначе играть было бы совсем не интересно.

Ваша задача — по текущему состоянию игрового поля определить, какие флажки окажутся подсвечены желтым после запуска подсказки.

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

F — флажок;

* — закрытая клетка;

Цифра от 0 до 8 — открытая клетка. Сама цифра обозначает, сколько суммарно мин находится в клетках, соседствующих с данной.

Выходные данные
В первой строке выведите количество флажков, которые окажутся подсвечены желтым, а в следующих N строчках выведите для каждого такого флажка его координаты — номер строки, а затем номер столбца, в котором стоит флажок. Флажки можно выводить в любом порядке.

Если подсвеченных флажков не будет, выведите единственное число 0
 

Примеры
Входные данные Выходные данные Пояснения
1 2 3
FFF
*2*
3
1 2
1 3
1 1
В тесте в клетке с координатами (2, 2) записано число 2, а касается она трех флажков, что больше двух. Значит, все эти три флажка будут подсвечены.

ID 38336
Остров
Темы: Двумерные массивы   

На клетчатой бумаге нарисована карта острова (клетки острова закрашены). При этом остров является клетчато-выпуклой фигурой, то есть каждая горизонтальная или вертикальная линия на карте либо не пересекает остров, либо пересекает его по отрезку (линия пересечения не содержит разрывов). Также остров является связной фигурой, то есть любые две клетки острова соединены путём, каждые две соседние клетки которого имеют общую сторону.

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


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

Выходные данные
Программа получает на вход два числа N и M, записанные в отдельных строках, — количество строк и столбцов карты острова (3 ≤ N ≤ 100, 3 ≤ M ≤ 100). Далее записана карта острова — N строк, каждая содержащая M символов. Каждый символ карты может быть либо символом «.», что означает клетку, не принадлежащую острову, либо символом «#», что означает клетку острова. При этом остров не касается края карты.

Введём на карте систему координат. Первая координата является номером строки, строки нумеруются сверху вниз числами от 1 до N. Вторая координата — номер столбца, столбцы нумеруются слева направо числами от 1 до M.

Входные данные
Программа должна вывести координаты клеток карты в порядке их облёта самолётом. Каждая строка вывода должна содержать два числа x и y — координаты самолёта, записанные через пробел (1 ≤ x ≤ N, 1 ≤ y ≤ M). Самолёт должен побывать в каждой соседней с островом клетке ровно один раз. Каждые две клетки, идущие подряд в выводе, должны иметь общую сторону. Можно вывести любой возможный маршрут облёта острова.

Примеры
Входные данные Выходные данные
1
6
7
.......
.......
.......
.###...
.###...
.......
3 1
3 2
3 3
3 4
3 5
4 5
5 5
6 5
6 4
6 3
6 2
6 1
5 1
4 1

ID 38360
Луч света в темном царстве
Темы: Задачи на моделирование    Двумерные массивы   

Темное царство представляет собой лабиринт NxM, некоторые клетки которого окружены зеркальными стенами, а остальные — пустые. Весь лабиринт также окружен зеркальной стеной. В одной из пустых клеток лабиринта поставили светофор, который испускает лучи в 4 направлениях: под 45 градусов относительно стен лабиринта. Требуется изобразить траекторию этих лучей.

Когда луч приходит в угол, через который проходят зеркальные стены, дальше он идет так, как показано на рисунках (серым цветом показаны клетки, которые окружены зеркальными стенами). Аналогичным образом луч ведет себя, когда приходит на границу лабиринта.


Входные данные
В первой строке входного файла записаны два натуральных числа N и M — число строк и столбцов в лабиринте (каждое из чисел не меньше 1 и не больше 100). В следующих N строках записано ровно по M символов в каждой — карта лабиринта. Символ * (звездочка) обозначает клетку, окруженную зеркальными стенками, . (точка) — пустую клетку, символ X (заглавная латинская буква X) — клетку, в которой расположен светофор (такая клетка ровно одна).

Выходные данные
В выходной файл выведите N строк по M символов в каждой — изображение лабиринта с траекториями лучей. Здесь, как и раньше, * (звездочка) должна обозначать клетки, окруженные зеркальными стенами, . (точка) — пустые клетки, через которые лучи света не проходят, / (слеш) — клетки, через которые луч света проходит из левого нижнего угла в правый верхний (или обратно — из правого верхнего в левый нижний), \ (обратный слеш) — клетки, через которые луч проходит из левого верхнего угла в правый нижний (или обратно), а символ X (заглавная латинская буква X) — клетки, через которые лучи проходят по обеим диагоналям.

Примеры
Входные данные Выходные данные
1
3 5
X....
.....
.....
XXXXX
XXXXX
XXXXX
2
3 3
...
..X
...
/X\
X.X
\X/

ID 38377
Флаг
Темы: Двумерные массивы   

Иннокентий работает на блошином рынке, продавая посетителям всякий хлам необычные вещи. Недавно он нашёл у себя на складе старое прямоугольное покрывало. Как оказалось, это покрывало имеет сетчатую форму, то есть покрывало состоит из nm цветных лоскутков, разбитых на n строк и m столбцов.

Цветные лоскутки привлекли внимание Иннокентия, и он сразу же придумал, как можно заработать на своей находке. Если вырезать из покрывала подпрямоугольник, состоящий из трёх цветных полос, то потом этот подпрямоугольник можно будет продать как флаг какой-нибудь страны. В частности, Иннокентий считает, что подпрямоугольник будет достаточно похож на флаг какой-нибудь страны, если он будет состоять из трёх одноцветных полос одинаковой высоты, находящихся друг под другом. Разумеется, цвет верхней полосы не должен совпадать с цветом средней полосы, а цвет средней не должен совпадать с цветом нижней.

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



Входные данные
Первая строка содержит два целых числа n и m (1 ≤ n, m ≤ 1000 ) — количество строк и столбцов в покрывале.

Каждая из следующих n строк описывает очередную строку покрывала и состоит из m строчных латинских букв от « a » до « z », где одинаковым цветам соответствуют одинаковые буквы, а разным цветам — разные буквы.

Выходные данные
В единственной строке выведите одно целое число — количество подпрямоугольников, являющихся флагами.

Примечание

Примеры
Входные данные Выходные данные
1 4 3
aaa
bbb
ccb
ddd
6

ID 38463
Мирные ладьи
Темы: Двумерные массивы   

На шахматной доске размером N × N расставлено N шахматных ладей не бьющих друг друга, то есть на каждой вертикали и каждой горизонтали стоит ровно одна ладья.


Шахматную доску повернули на 90? по часовой стрелке. Выведите получившуюся расстановку ладей.


Формат входных данных
Первая строка входных данных содержит целое число N, 1 ≤ N ≤ 105 — размер доски. Следующие N строк содержат по одному числу от 1 до N, а именно, в i-й строке записано число ai — номер вертикали, в которой стоит ладья на i-й горизонтали. В этой задаче горизонтали нумеруются числами от 1 до N сверху вниз, вертикали нумеруются числами от 1 до N слева направо (см.рисунок).

Формат выходных данных
Программа должна вывести N чисел — расстановку ладей после поворота в таком же формате.

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

Замечание
Пример в условии соответствует рисункам. Первоначально ладьи стояли в столбцах 4, 2, 3, 5, 1
при перечислении их по строкам сверху вниз. После поворота ладьи стоят в столбцах 1, 4, 3, 5, 2.

 

ID 38471
Гипер-минимум
Темы: Двумерные массивы   

Имеется 4-мерный массив X, каждый индекс которого может принимать значения от 1 до N. Вы должны построить новый 4-мерный массив Y , элементы которого должны принимать следующие значения: Y [i1, i2, i3, i4] = min(X[j1, j2, j3, j4]), где 1 ≤ ik ≤ N − M + 1, ik ≤ jk ≤ ik + M − 1, а M -  заданное число.

Входные данные
В первой строке входного файла задаются N и M (1 ≤ M ≤ N). Остальные строки файла содержат элементы массива X. Количество элементов не будет превышать 1500000 и сами они будут целыми числами, не превышающими по абсолютному значению 109. Они расположены в таком порядке, что считать их можно с помощью псевдокода:

for i = 1 to N:
for j = 1 to N:
for k = 1 to N:
for l = 1 to N:
read X[i, j, k, l]

Выходные данные
Выведите искомый массив Y в том же формате, в котором был дан массив X.
 

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

ID 38434
Игра с фишками
Темы: Обход в ширину    Двумерные массивы   

Вы являетесь одним из разработчиков новой компьютерной игры. Игра происходит на прямоугольной доске, состоящей из W×H клеток. Каждая клетка может либо содержать, либо не содержать фишку (см. рисунок).
Важной частью игры является проверка того, соединены ли две фишки путем, удовлетворяющим следующим свойствам:
1.    Путь должен состоять из отрезков вертикальных и горизонтальных прямых.
2.    Путь не должен пересекать других фишек.
При этом часть пути может оказаться вне доски. Например:

Фишки с координатами (1, 3) и (4, 4) могут быть соединены. Фишки с координатами (2, 3) и (5, 3) тоже могут быть соединены. А вот фишки с координатами (2, 3) и (3, 4) соединить нельзя — любой соединяющий их путь пересекает другие фишки.
Вам необходимо написать программу, проверяющую, можно ли соединить две фишки путем, обладающим вышеуказанными свойствами, и, в случае положительного ответа, определяющую минимальную длину такого пути (считается, что путь имеет изломы, начало и конец только в центрах клеток (или “мнимых клеток”, расположенных вне доски), а отрезок, соединяющий центры двух соседних клеток, имеет длину 1).

Формат входных данных
Первая строка входного файла содержит два натуральных числа: W — ширина доски, H — высота доски (1 ≤ W, H ≤ 75). Следующие H строк содержат описание доски: каждая строка состоит ровно из W символов: символ “X” (заглавная английская буква “экс”) обозначает фишку, символ “.” (точка) обозначает пустое место. Все остальные строки содержат описания запросов: каждый запрос состоит из четырех натуральных чисел, разделенных пробелами — X1, Y1, X2, Y2, причем 1 ≤ X1, X2 ≤ W, 1 ≤ Y1, Y2 ≤ H. Здесь (X1, Y1) и (X2, Y2) — координаты фишек, которые требуется соединить (левая верхняя клетка имеет координаты (1, 1)). Гарантируется, что эти координаты не будут совпадать (кроме последнего запроса). Последняя строка содержит запрос, состоящий из четырех чисел 0; этот запрос обрабатывать не надо. Количество запросов не превосходит 20.

Формат выходных данных
Для каждого запроса необходимо вывести одно целое число на отдельной строке — длину кратчайшего пути, или 0, если такого пути не существует.
Примеры
Входные данные Выходные данные
1
5 4
XXXXX
X...X
XXX.X
.XXX.
2 3 5 3
1 3 4 4
2 3 3 4
0 0 0 0
5
6
0
2
4 4
XXXX
.X..
..X.
X...
1 1 3 1
0 0 0 0
4