Обработка и вывод вложенных списков

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

A = [ [1, 2, 3], [4, 5, 6] ]

Здесь первая строка списка A[0] является списком из чисел [1, 2, 3]. То есть 

A[0][0] == 1,   A[0][1] == 2,   A[0][2] == 3

A[1][0] == 4,   A[1][1] == 5,   A[1][2] == 6

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

for i in range(len(A)):
    for j in range(len(A[i])):
        print(A[i][j], end = ' ')
    print()

То же самое, но циклы не по индексу, а по значениям списка: 

for row in A:
    for elem in row:
        print(elem, end = ' ')
    print()

Естественно для вывода одной строки можно воспользоваться методом join: 

for row in A:
    print(' '.join(map(str, row)))

Используем два вложенных цикла для подсчета суммы всех чисел в списке: 

S = 0
for i in range(len(A)):
    for j in range(len(A[i])):
        S += A[i][j]

Или то же самое с циклом не по индексу, а по значениям строк: 

S = 0
for row in A:
    for elem in row:
        S += elem

Ввод списка

Пусть программа получает на вход двумерный массив, в виде n строк, каждая из которых содержит m чисел, разделенных пробелами. Как их считать? Например, так: 

A = []
for i in range(n):
    A.append(list(map(int, input().split())))

Или, без использования сложных вложенных вызовов функций: 

A = []
for i in range(n):
    row = input().split()
    for i in range(len(row)):
        row[i] = int(row[i])
    A.append(row)

Можно сделать то же самое и при помощи генератора: 

A = [list(map(int, input().split())) for i in range(n)]

A: Максимум

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

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

3 4
0 3 2 4
2 3 5 5
5 1 2 3

1 2
IDE

Создание пустого многомерного списка

Пусть даны два числа: количество строк n и количество столбцов m. Необходимо создать список размером n×m, заполненный нулями.

Очевидное решение оказывается неверным: 

A = [[0] * m ] * n

В этом легко убедиться, если присвоить элементу A[0][0] значение 1, а потом вывести значение другого элемента A[1][0] — оно тоже будет равно 1! Дело в том, что [0] * m возвращает ccылку на список из m нулей. Но последующее повторение этого элемента создает список из n элементов, которые являются ссылкой на один и тот же список (точно так же, как выполнение операции B = A для списков не создает новый список), поэтому все строки результирующего списка на самом деле являются одной и той же строкой.

Таким образом, двумерный список нельзя создавать при помощи операции повторения одной строки. Что же делать?

Первый способ: сначала создадим список из n элементов (для начала просто из n нулей). Затем сделаем каждый элемент списка ссылкой на другой одномерный список из m элементов: 

A = [0] * n
for i in range(n):
    A[i] = [0] * m

Другой (но похожий) способ: создать пустой список, потом n раз добавить в него новый элемент, являющийся списком-строкой: 

A = []
for i in range(n):
    A.append([0] * m)

Но еще проще воспользоваться генератором: создать список из n элементов, каждый из которых будет списком, состоящих из m нулей: 

A = [[0] * m for i in range(n)]

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

Сложный пример обработки массива

Пусть дан квадратный массив из n строк и n столбцов. Необходимо элементам, находящимся на главной диагонали, проходящей из левого верхнего угла в правый нижний (то есть тем элементам A[i][j], для которых i == j) присвоить значение 1, элементам, находящимся выше главной диагонали — значение 0, элементам, находящимся ниже главной диагонали — значение 2. То есть получить такой массив (пример для n==4): 

     1 0 0 0
     2 1 0 0
     2 2 1 0
     2 2 2 1

Рассмотрим несколько способов решения этой задачи. Элементы, которые лежат выше главной диагонали — это элементы A[i][j], для которых i < j, а для элементов ниже главной диагонали i > j. Таким образом, мы можем сравнивать значения i и j и по ним определять значение A[i][j]. Получаем следующий алгоритм: 

for i in range(n):
    for j in range(n):
        if i < j:
            A[i][j] = 0
        elif i > j:
            A[i][j] = 2
        else:
            A[i][j] = 1

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

Сначала заполним главную диагональ, для чего нам понадобится один цикл: 

for i in range(n):
    A[i][i] = 1

Затем заполним значением 0 все элементы выше главной диагонали, для чего нам понадобится в каждой из строк с номером i присвоить значение элементам A[i][j] для j=i+1, ..., n-1. Здесь нам понадобятся вложенные циклы: 

for i in range(n):
    for j in range(i + 1, n):
        A[i][j] = 0

Аналогично присваиваем значение 2 элементам A[i][j] для j=0, ..., i-1: 

for i in range(n):
    for j in range(0, i):
        A[i][j] = 2

Можно также внешние циклы объединить в один и получить еще одно, более компактное решение: 

for i in range(n):
    for j in range(0, i):
        A[i][j] = 2
    A[i][i] = 1
    for j in range(i + 1, n):
        A[i][j] = 0

А вот такое решение использует операцию повторения списков для построения очередной строки списка. i-я строка списка состоит из i чисел 2, затем идет одно число 1, затем идет n-i-1 число 0: 

for i in range(n):
    A[i] = [2] * i + [1] + [0] * (n - i - 1)

А можно заменить цикл на генератор: 

A = [ [2] * i + [1] + [0] * (n - i - 1) for i in range(n)]

B: Снежинка

Дано нечетное число n. Создайте двумерный массив из n×n элементов, заполнив его символами "." (каждый элемент массива является строкой из одного символа). Затем заполните символами "*" среднюю строку массива, средний столбец массива, главную диагональ и побочную диагональ. В результате единицы в массиве должны образовывать изображение звездочки. Выведите полученный массив на экран, разделяя элементы массива пробелами. 

5

* . * . *
. * * * .
* * * * *
. * * * .
* . * . *
IDE

C: Шахматная доска

Даны два числа n и m. Создайте двумерный массив размером n×m и заполните его символами "." и "*" в шахматном порядке. В левом верхнем углу должна стоять точка. 

3 4

. * . *
* . * .
. * . *
IDE

D: Диагонали параллельные главной

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

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
IDE

E: Побочная диагональ

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

Числа на диагонали, идущей из правого верхнего в левый нижний угол равны 1.

Числа, стоящие выше этой диагонали, равны 0.

Числа, стоящие ниже этой диагонали, равны 2.

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

4

0 0 0 1
0 0 1 2
0 1 2 2
1 2 2 2
IDE

F: Поменять столбцы

Дан двумерный массив и два числа: i и j. Поменяйте в массиве столбцы с номерами i и j.

Решение оформите в виде функции swap_columns(a: list, i: int, j:int), модифицирующей переданный список, но не возвращающей значение.

На проверку сдайте только тело функции.

a = [[11, 12, 13, 14], [21, 22, 23, 24], [31, 32, 33, 34]]
swap_columns(a, 0, 1)

[[12, 11, 13, 14], [22, 21, 23, 24], [32, 31, 33, 34]]
Код вызова функции для тестирования
n, m = map(int, input().split()) source_list = [list(map(int, input().split())) for i in range(n)] source_i, source_j = map(int, input().split()) source_list_copy = copy.copy(source_list) del n del m res = swap_columns(source_list, source_i, source_j) if len(source_list) != len(source_list_copy): print("Функция изменила длину внешнего списка") sys.exit(0) for i in range(len(source_list)): if source_list[i] is not source_list_copy[i]: print("Функция изменила ссылки на вложенные списки") sys.exit(0) if res is not None: print("Функция не должна возвращать результат") sys.exit(0) for row in source_list: print(" ".join(map(str, row)))
IDE

G: Симметричен ли массив?

Дан массив размером \(n\times n\). Проверьте, является ли этот массив симметричным относительно главной диагонали.

Решение оформите в виде функции is_symmetric(a: list) -> bool, возвращающей True или False. 

is_symmetric([[0, 1, 2], [1, 2, 3], [2, 3, 4]])

True
Код вызова функции для тестирования
n = int(input()) source_list = [list(map(int, input().split())) for i in range(n)] source_list_copy = copy.copy(source_list) source_list_deep_copy = copy.deepcopy(source_list) del n res = is_symmetric(source_list) if len(source_list) != len(source_list_copy): print("Функция изменила длину внешнего списка") sys.exit(0) for i in range(len(source_list)): if source_list[i] is not source_list_copy[i]: print("Функция изменила ссылки на вложенные списки") sys.exit(0) if source_list != source_list_deep_copy: print("Функция изменила содержимое переданного списка") sys.exit(0) if res is True: print("YES") elif res is False: print("NO") else: print("Функция должна возвращать значение типа bool")
IDE

H: k-я диагональ

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

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

Решение оформите в виде функции kth_diagonal(a: list, k: int) -> list

Сложность алгоритма должна быть \(O(n)\), то есть нельзя осуществлять проход по всему двумерному массиву. 

kth_diagonal([[1, 2, 3, 4], [5, 6, 7, 8], [0, 1, 2, 3], [4, 5, 6, 7]], 1)

[5, 1, 6]

kth_diagonal([[1, 2, 3, 4], [5, 6, 7, 8], [0, 1, 2, 3], [4, 5, 6, 7]], -2)

[3, 8]
Код вызова функции для тестирования
n = int(input()) source_list = [list(map(int, input().split())) for i in range(n)] source_k = int(input()) source_list_copy = copy.copy(source_list) source_list_deep_copy = copy.deepcopy(source_list) del n res = kth_diagonal(source_list, source_k) if len(source_list) != len(source_list_copy): print("Функция изменила длину внешнего списка") sys.exit(0) for i in range(len(source_list)): if source_list[i] is not source_list_copy[i]: print("Функция изменила ссылки на вложенные списки") sys.exit(0) if source_list != source_list_deep_copy: print("Функция изменила содержимое переданного списка") sys.exit(0) if type(res) is not list: print("Функция должна возвращать список") sys.exit(0) for elem in res: if type(elem) is not int: print("Функция дожна возвращать список, элементы которого имеют тип int") sys.exit(0) print(*res)
IDE

Как сделать выровненную таблицу

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

rjust — метод объекта типа str, принимающий два параметра: длину новой строки (ширина поля вывода) и символ-заполнитель: rjust(n, ch). Например, s.rjust(10, '.'). Метод возвращает новую строку, длина которой равна n символов, исходная строка находится в конце результата (то есть исходная строка “выравнивается” по правому краю), лишние позиции заполняются символом ch. Если опустить ch, то в качестве символа-заполнителя используется пробел. Если длина исходной строки была больше n, то возвращается исходная строка без изменений (строка не обрезается).

Аналогично есть методы ljust, выравнивающий строку по левому краю и center, выравнивающий строку по центру результата.

Ещё один способ — при помощи метода format: 

>>> x = 13
  13
>>> print('*' + str(x).rjust(4) + '*')
*  13*
>>> print('*' + '{:>4}'.format(x) + '*')
*  13*

I: Таблица умножения

По данным числам n и m создайте массив из n строк и m столбцов и заполните его таблицей умножения чисел от 1 до n на числа от 1 до m (должен получиться массив, заполненный значениями типа int).

Выведите полученную таблицу, отводя на вывод каждого числа ровно 4 символа, то есть таблица при выводе должна состоять из столбцов шириной в 4 символа, числа должны быть выровнены по правому краю столбца (в каждой строке должно быть выведено 4*m символов). 

4 5

   1   2   3   4   5
   2   4   6   8  10
   3   6   9  12  15
   4   8  12  16  20
IDE

J: Заполнение змейкой

По данным числам n и m заполните двумерный массив размером n×m числами от 1 до n×m “змейкой”, как показано в примере (должен получиться массив, заполненный значениями типа int).

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

3 5

   1   6   7  12  13
   2   5   8  11  14
   3   4   9  10  15
IDE

K: Транспонировать прямоугольную матрицу

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

Для данного массива постройте транспонированный массив. Решение оформите в виде функции transpose(a: list) -> list, получающей на вход список списков (и не модифицирующей его) и возвращающей новый список. 

transpose([[11, 12, 13, 14], [21, 22, 23, 24], [31, 32, 33, 34]])

[[11, 21, 31], [12, 22, 32], [13, 23, 33], [14, 24, 34]]
Код вызова функции для тестирования
n, m = map(int, input().split()) source_list = [list(map(int, input().split())) for i in range(n)] source_list_copy = copy.copy(source_list) source_list_deep_copy = copy.deepcopy(source_list) del n del m res = transpose(source_list) if len(source_list) != len(source_list_copy): print("Функция изменила длину внешнего списка") sys.exit(0) for i in range(len(source_list)): if source_list[i] is not source_list_copy[i]: print("Функция изменила ссылки на вложенные списки") sys.exit(0) if source_list != source_list_deep_copy: print("Функция изменила содержимое переданного списка") sys.exit(0) if type(res) is not list: print("Функция должна возвращать список") sys.exit(0) if len(res) != len(source_list[0]): print("Функция должна возвращать список длины m =", len(source_list[0])) sys.exit(0) for row in res: if type(row) is not list: print("Функция дожна возвращать список, элементы которого являются списком") sys.exit(0) if len(row) != len(source_list): print("Функция должна возвращать список, элементы которого являются списком длины n = ", len(source_list)) sys.exit(0) for elem in row: if type(elem) is not int: print("Функция должна возвращать список, элементы которого являются списками элементов типа int") sys.exit(0) for row in res: print(*row)
IDE

L: Транспонировать квадратную матрицу

Дан двумерный массив размером n×n. Транспонируйте его, записав результат в тот же массив. Вспомогательный список использовать нельзя.

Решение оформите в виде функции transpose(a: list), получающей на вход данный массив. Функция переставляет элементы внутри массива a, и не возвращает никакого значения. 

a = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
transpose(a)

[[1, 4, 7], [2, 5, 8], [3, 6, 9]]
Код вызова функции для тестирования
n = int(input()) source_list = [list(map(int, input().split())) for i in range(n)] source_list_copy = copy.copy(source_list) source_list_deep_copy = copy.deepcopy(source_list) del n res = transpose(source_list) if res is not None: print("Функция не должна возвращать значение") sys.exit(0) if len(source_list) != len(source_list_copy): print("Функция изменила длину внешнего списка") sys.exit(0) for i in range(len(source_list)): if source_list[i] is not source_list_copy[i]: print("Функция изменила ссылки на вложенные списки") sys.exit(0) for elem in source_list[i]: if type(elem) is not int: print("Изменился тип элементов вложенных списков") sys.exit(0) for row in source_list: print(*row)
IDE

M: Поменять две диагонали

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

Решение оформите в виде функции swap_diagonals(a). Функция переставляет элементы внутри массива a, и не возвращает никакого значения. 

a = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
swap_diagonals(a)

[[7, 2, 9], [4, 5, 6], [1, 8, 3]]
Код вызова функции для тестирования
n = int(input()) source_list = [list(map(int, input().split())) for i in range(n)] source_list_copy = copy.copy(source_list) source_list_deep_copy = copy.deepcopy(source_list) del n res = swap_diagonals(source_list) if res is not None: print("Функция не должна возвращать значение") sys.exit(0) if len(source_list) != len(source_list_copy): print("Функция изменила длину внешнего списка") sys.exit(0) for i in range(len(source_list)): if source_list[i] is not source_list_copy[i]: print("Функция изменила ссылки на вложенные списки") sys.exit(0) for elem in source_list[i]: if type(elem) is not int: print("Изменился тип элементов вложенных списков") sys.exit(0) for row in source_list: print(*row)
IDE

N: Число маршрутов короля

В левом верхнем углу доски размером n×m стоит шахматный король. За один ход он может сделать ход вправо, вниз или на одну клетку по диагонали вправо-вниз. Посчитайте количество маршрутов, ведущий из левого верхнего угла доски в правый нижний.

Программа получает на вход размеры доски (числа n и m) и должна вывести число искомых маршрутов. 

3 4

25
IDE

O: Одномерный список в двумерный

Дан одномерный список элементов. Сделайте из него двумерный список, содержащий по \(n\) элементов в каждой строке (быть может, кроме последней). В последней строке может быть меньше \(n\) элементов (но должен быть хотя бы один элемент).

Решение оформите в виде функции to_2d(a: list, n: int) -> list, принимающей в качестве параметра список чисел и значение \(n\) и возвращающей новый список чисел. 

to_2d([1, 2, 3, 4, 5, 6, 7, 8, 9], 5)

[[1, 2, 3, 4, 5], [6, 7, 8, 9]]
Код вызова функции для тестирования
source_n = int(input()) source_list = input().split() source_list_copy = copy.copy(source_list) res = to_2d(source_list, source_n) if source_list != source_list_copy: print("Функция изменила переданный список") sys.exit(0) if type(res) is not list: print("Функция должна вернуть список") print("Функция вернула: ", res) sys.exit(0) for i in range(len(res)): if i < len(res) - 1 and len(res[i]) != source_n: print("Строка с индексом", i, "содержит неверное число элементов") print("Функция вернула: ", res) sys.exit(0) if i == len(res) - 1 and (len(res[i]) == 0 or len(res[i]) > source_n): print("Строка с индексом", i, "содержит неверное число элементов") print("Функция вернула: ", res) sys.exit(0) print("\n".join(map(lambda row: " ".join(row), res)))
IDE

P: Заполнение диагоналями

По данным числам n и m заполните двумерный массив размером n×m числами от 1 до n×m “диагоналями”, как показано в примере. (должен получиться массив, заполненный значениями типа int).

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

3 5

   1   2   4   7  10
   3   5   8  11  13
   6   9  12  14  15
IDE

Q: Поворот прямоугольного массива

Дан прямоугольный массив размером \(n\times m\). Поверните его на 90 градусов по часовой стрелке, записав результат в новый массив размером \(m\times n\).

Решение оформите в виде функции rotate(a: list) -> list, получающей на вход данный массив и возвращающей новый массив, не модифицируя исходный массив. 

rotate([[11, 12, 13, 14], [21, 22, 23, 24], [31, 32, 33, 34]])

[[31, 21, 11], [32, 22, 12], [33, 23, 13], [34, 24, 14]]
Код вызова функции для тестирования
n, m = map(int, input().split()) source_list = [list(map(int, input().split())) for i in range(n)] source_list_copy = copy.copy(source_list) source_list_deep_copy = copy.deepcopy(source_list) del n del m res = rotate(source_list) if len(source_list) != len(source_list_copy): print("Функция изменила длину внешнего списка") sys.exit(0) for i in range(len(source_list)): if source_list[i] is not source_list_copy[i]: print("Функция изменила ссылки на вложенные списки") sys.exit(0) if source_list != source_list_deep_copy: print("Функция изменила содержимое переданного списка") sys.exit(0) if type(res) is not list: print("Функция должна возвращать список") sys.exit(0) if len(res) != len(source_list[0]): print("Функция должна возвращать список длины m =", len(source_list[0])) sys.exit(0) for row in res: if type(row) is not list: print("Функция дожна возвращать список, элементы которого являются списком") sys.exit(0) if len(row) != len(source_list): print("Функция должна возвращать список, элементы которого являются списком длины n = ", len(source_list)) sys.exit(0) for elem in row: if type(elem) is not int: print("Функция должна возвращать список, элементы которого являются списками элементов типа int") sys.exit(0) for row in res: print(*row)
IDE

R: Поворот квадратного массива

Дан квадратный массив. Поверните его на 90 градусов по часовой стрелке. Результат запишите в этот же массив, вспомогательный массив использовать нельзя.

Решение оформите в виде функции rotate(a: list), получающей на вход данный массив. Функция переставляет элементы внутри массива a, и не возвращает никакого значения. 

a = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
rotate(a)

[[7, 4, 1], [8, 5, 2], [9, 6, 3]]
Код вызова функции для тестирования
n = int(input()) source_list = [list(map(int, input().split())) for i in range(n)] source_list_copy = copy.copy(source_list) del n res = rotate(source_list) if len(source_list) != len(source_list_copy): print("Функция изменила длину внешнего списка") sys.exit(0) for i in range(len(source_list)): if source_list[i] is not source_list_copy[i]: print("Функция изменила ссылки на вложенные списки") sys.exit(0) if res is not None: print("Функция не должна возвращать значение") sys.exit(0) for row in source_list: print(*row)
IDE

S: Заполнение в шахматном порядке

Даны числа n и m. Заполните массив размером \(n\times m\) в шахматном порядке: клетки одного цвета заполнены нулями, а другого цвета — заполнены числами натурального ряда сверху вниз, слева направо (должен получиться массив, заполненный значениями типа int). В левом верхнем углу записано число 1.

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

3 5

   1   0   2   0   3
   0   4   0   5   0
   6   0   7   0   8
IDE

T: Сапер

На поле для игры в сапер клеточки с минами обозначаются символом “*”, а в каждой пустой клеточке записано число от 0 до 8, равное количеству мин в 8 клетках, соседних с данной.

Дан список мин на поле. Постройте по данному списку изображение поля.

Программа получает на вход числа N и M - количество строк и столбцов на поле, а также количество мин на поле K. Далее идет K пар чисел - координат мин. Первое число - номер строки, второе число - номер столбца.

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

3 2 2
1 1
2 2

* 2
2 *
1 1

2 2 0

0 0
0 0
IDE

U: Ходы коня

Дана шахматная доска из \(N\) строк и \(M\) столбцов. На ней стоит \(K\) шахматных коней. Постройте изображение доски, отметив на ней коней и клетки, которые бьют кони.

Клетку, где стоит конь, отметьте буквой “K”, клетки, которые бьет конь (но в ней нет коня), отметьте символами “*”, остальные клетки заполните точками.

Первая строка входных данных содержит три числа \(N\), \(M\), \(K\): количество строк доски, количество столбцов в доске и количество коней на доске (\(1\le N\le 300\), \(1\le M\le 300\), \(0\le K \le 10000\)).

В следующих \(K\) строках содержатся координаты коней  по два числа \(x_i\), \(y_i\) (\(0\le x_i\lt N\), \(0\le y_i\lt M\)), номер строки и номер столбца очередного коня соответственно (нумерация с нуля сверху вниз, слева направо).

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

Решение должно иметь сложность \(O(NM + K)\), решение сложности \(O(NMK)\), то есть перебирающее все клетки доски, и для каждой клетки перебирающее всех коней, не пройдет по времени.

Решение, в котором все возможные ходы коня перебираются “ручным” разбором случаев, приниматься не будут. Как красиво перебирать ходы коня: 

MOVES = [[2, 1], [2, -1], [1, 2], [1, -2], [-1, 2], [-1, -2], [-2, 1], [-2, -1]]
...
for dx, dy in MOVES:
    nx, ny = x + dx, y + dy

4 7 2
1 1
3 6

. . . * . . .
. K . . . * .
. . . * * . .
* . * . . . K

3 3 2
1 0
2 2

. * *
K . .
. . K
IDE

V: Ходы ферзя

Решите предыдущую задачу для ферзя. Ферзь обозначается буквой “Q”. Ограничение на количество ферзей: \(0\le K\le 300\). Требуемая сложность алгоритма: \(O(NM + K(N + M))\). 

4 7 1
1 1

* * * . . . .
* Q * * * * *
* * * . . . .
. * . * . . .

3 3 2
0 0
2 0

Q * *
* * .
Q * *
IDE

W: Заполнение спиралью

По данным числам n и m заполните двумерный массив размером n×m числами от 1 до n×m по спирали, выходящей из левого верхнего угла и закрученной по часовой стрелке, как показано в примере (должен получиться массив, заполненный значениями типа int).

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

Тесты к этой задаче закрытые.

4 5

   1   2   3   4   5
  14  15  16  17   6
  13  20  19  18   7
  12  11  10   9   8
IDE

X: K-мерный массив

Дано натуральное число \(k\). Сделайте \(k\)-мерный массив (систему списков уровня вложенности \(k\)) размера 2 по каждому измерению, то есть общее число элементов в списке должно быть \(2^k\). Заполните его нулями.

Решение оформите в виде функции gen_x(k: int) -> list.

На проверку сдайте только тело функции.

Обязательное требование - каждый элемент массива должен содержать различные вложенные массивы, а не ссылки на один и тот же массив. Как проверить своё решение?

Проверка 1. Пусть функция вернула список: a = gen_x(k). Проверьте, что условие a[0] is a[1]  — ложно.

Проверка 2. Измените элемент массива, у которого все индексы равны 0, присвоив ему значение 1. Это можно сделать при помощи следующего кода (A — исходный массив): 

b = a
for i in range(k - 1):
    b = b[0]
b[0] = 1

Выведите массив после изменения. В массиве должна быть только одна единица. 

1

[0, 0]

2

[[0, 0], [0, 0]]

3

[[[0, 0], [0, 0]], [[0, 0], [0, 0]]]
Код вызова функции для тестирования
def check(a): if type(a) is int: return if type(a) is not list: print("Один из внутренних списков имеет тип отличный от int и list") sys.exit(0) for i in range(len(a)): if type(a[i]) is list: for j in range(i): if a[i] is a[j]: print("Среди вложенных списков есть ссылки на один и тот же список") sys.exit(0) for elem in a: check(elem) def set0(a): if type(a[0]) is int: a[0] = 1 else: set0(a[0]) def rec_sum(a): if type(a) is int: return a else: s = 0 for elem in a: s += rec_sum(elem) return s a = gen_x(int(input())) if type(a) is not list: print("Функция должна возвращать список") sys.exit(0) check(a) print(a) set0(a) if rec_sum(a) != 1: print("После модификации одного элемента списка, в списке изменилось много элементов") print("Состояние списка после изменения:") print(a)
IDE

Y: K-мерный массив - 2

Дано натуральное число \(k\). Сделайте \(k\)-мерный массив размера 2 по каждому измерению.

Массив заполните строковыми значениями по формуле: \[ a[i_1][i_2]...[i_k] = \mbox{str}(i_1)+\mbox{str}(i_2)+...+\mbox{str}(i_k) \]

Например, если k == 4, то a[0][0][1][0] == '0010'.

Решение оформите в виде функции gen_y(k: int) -> list.

На проверку сдайте только тело функции. 

gen_y(1)

['0', '1']

gen_y(2)

[['00', '01'], ['10', '11']]

gen_y(3)

[[['000', '001'], ['010', '011']], [['100', '101'], ['110', '111']]]
Код вызова функции для тестирования
a = gen_y(int(input())) if type(a) is not list: print("Функция должна возвращать список") sys.exit(0) print(a)
IDE

Z: K-мерный массив - 3

Дан набор из \(k\) натуральных чисел \(n_1\), \(n_2\), ..., \(n_k\).

Создайте \(k\)-мерный массив размера \(n_1\times n_2\times ... \times n_k\). Заполните его целыми числами по формуле: \[ a[i_1][i_2]...[i_k] = i_1 + 2i_2 + ... + ki_k. \]

Решение оформите в виде функции gen_z(dimensions: list) -> list. Передаваемый параметр: список размеров массива по каждому измерению.

На проверку сдайте только тело функции. 

gen_z([2, 3])

[[0, 2, 4], [1, 3, 5]]

gen_z([3, 2])

[[0, 2], [1, 3], [2, 4]]

gen_z([2, 2, 2])

[[[0, 3], [2, 5]], [[1, 4], [3, 6]]]
Код вызова функции для тестирования
a = gen_z(list(map(int, input().split()))) if type(a) is not list: print("Функция должна возвращать список") sys.exit(0) print(a)
IDE

ZA: Крестики-нолики

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

Напомним, что игра в «Крестики-нолики» ведется на поле 3×3. Два игрока ходят по очереди. Первый ставит крестик, а второй – нолик. Ставить крестик и нолик разрешается в любую еще не занятую клетку поля. Когда один из игроков поставит три своих знака в одной горизонтали, вертикали или диагонали, или когда все клетки поля окажутся заняты, игра заканчивается.

Вводится три строки по три числа в каждой, описывающих игровое поле. Число 0 обозначает пустую клетку, 1 – крестик, 2 – нолик. Числа в строке разделяются пробелами.

Требуется вывести слово YES, если указанная ситуация могла возникнуть в ходе игры, и NO в противном случае.

Тесты к этой задаче закрытые.

1 1 1
1 1 1
1 1 1

NO

2 1 1
1 1 2
2 2 1

YES

1 1 1
2 0 2
0 0 0

YES

0 0 0
0 1 0
0 0 0

YES

1 1 1
2 2 2
0 0 0

NO
IDE

ZB: Жизнь

Автор игры “Жизнь” британский математик Джон Конвей скончался 11 апреля 2020 г. от осложнений коронавирусной инфекции в Нью-Джерси, США.

Наиболее известный пример клеточного автомата  — игра “Жизнь” — устроен по следующим правилам. В каждой клетке клетчатого поля может жить микроорганизм. Для клетки подсчитывается количество соседних с ней клеток (по стороне или по углу), в которых есть микроорганизмы.

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

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

В первой строке входных данных записаны два натуральных числа — размер квадратного поля \(N\) (\(1 \le N \le 10\)) и время \(T\) (\(1 \le T \le 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
IDE

ZC: Робот

Петя написал программу движения робота. Программа состоит из следующих команд:

S — сделать шаг вперед.

L — повернуться на 90 градусов влево.

R — повернуться на 90 градусов вправо.

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

Программа получает на вход строку из заглавных латинских букв S, L, R, описывающую программу для робота. Общее число команд в программе не превышает 200, при этом команд S — не более 50.

Программа должна вывести, сколько шаго будет сделано (то есть выполнено команд S) прежде, чем робот впервые окажется в том месте, через которое он уже проходил. Если такого не произойдет, выведите в выходной файл число –1. 

SSLSLSLSSRSRS

5

LSSSS

-1
IDE

ZD: Магический квадрат

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

Программа получает на вход одно число \(N\), \(3\le N\le 100\) и должна вывести магический квадрат порядка \(N\). 

4

16 2 3 13
5 11 10 8
9 7 6 12
4 14 15 1
IDE