🐍🧩 Задача об определении латинского квадрата

Хочешь уверенно проходить IT-интервью?

Мы понимаем, как сложно подготовиться: стресс, алгоритмы, вопросы, от которых голова идёт кругом. Но с AI тренажёром всё гораздо проще.

💡 Почему Т1 тренажёр — это мастхэв?

• Получишь настоящую обратную связь: где затык, что подтянуть и как стать лучше
• Научишься не только решать задачи, но и объяснять своё решение так, чтобы интервьюер сказал: "Вау!".
• Освоишь все этапы собеседования, от вопросов по алгоритмам до диалога о твоих целях.

Зачем листать миллион туториалов? Просто зайди в Т1 тренажёр, потренируйся и уверенно удиви интервьюеров. Мы не обещаем лёгкой прогулки, но обещаем, что будешь готов!

Реклама. ООО «Смарт Гико», ИНН 7743264341. Erid 2VtzqwP8vqy

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

Входные данные:

• число n – количество строк и столбцов в матрице;

• n строк, c n чисел в каждой.

Выходные данные:

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

        # Пример ввода:
4
2 3 4 1
3 4 1 2
4 1 2 3
1 2 3 4


Пример вывода:
#YES
    

Решение

Первый способ– с использованием функции sorted():

        n = int(input())
matrix = [[int(i) for i in input().split()] for _ in range(n)]
for i in range(n):
    if sorted(matrix[i]) != list(range(1, n + 1)) or sorted([matrix[j][i] for j in range(n)]) != list(range(1, n + 1)):
        print('NO')
        break
else:
    print('YES')
    

Второй способ – с использованием функции all():

        n = int(input())
square = [[*map(int,input().split()) ] for i in range(n)]
a = all([all([c in row for c in range(1,n + 1)]) for row in square])
b = all([all([c in row1 for c in range(1, n + 1)]) for row1 in zip(*square)])

print(('NO','YES')[a and b])

    

Третий способ – с использованием транспонирования и множеств:

        n = int(input())
sq_set = set(range(1, n + 1))
square = []
for i in range(n):
    square.append(list(map(int, input().split())))
tr_square = list(map(list, zip(*square)))
vector_1 = [set(row) == sq_set for row in square]
vector_2 = [set(row) == sq_set for row in tr_square]
vector = vector_1 + vector_2
if all(vector):
    print('YES')
else:
    print('NO')

    

Материалы по теме

• 🐍 Словари в Python: 12 задач для начинающих с решениями
• 🐍 Python и динамическое программирование на примере задачи о рюкзаке
  
• 🐍 Известная задача с потерянным билетом: реализация на Python