Question

В мире животных проходит турнир по шахматам на доске n*m! В решающем матче встречаются коала и акула, а судит этот матч слон. Коала выигрывает, поэтому акула прибегла к нечестной тактике: она запугала слона своими зубами, и он разрешил ей поставить сколько угодно слонов на поле. Теперь акула доставляет на доску слонов. Она хочет, чтобы никакие два из поставленных ею слонов не били друг друга. Также она хочет, чтобы число слонов было максимально (ведь чем больше фигур - тем лучше). Акула рассказала вам, на каких позициях находятся фигуры в данный момент (и дала вам достаточную мотивацию). Срочно помогите ей выбрать места для слонов! Шахматный слон ходит по диагонали и не может перепрыгивать через другие фигуры. Слонов можно ставить только на пустые клетки. Формат входных данных В первой строке вводятся целые числа n, m и k (1 ≤ n, m, k ≤ 500) - размеры доски (доска размера n*m) и число фигур на доске. В следующих k строках выводятся по 2 числа: xi и yi (1 ≤ xi ≤ n, 1 ≤ yi ≤ m) - координаты i-й фигуры. Формат результата В первой строке выведите x (0 ≤ x ≤ n*m) - максимальное число слонов, которое вы можете поставить так, чтобы они не били друг друга. В следующих x строках выведите по 2 числа: xi и yi - координаты i-го слона, которого вы поставили. 1 ≤ ri ≤ n, 1 ≤ ci ≤ m. Примеры Входные данные 3 3 0 Результат работы 4 1 1 1 2 1 3 3 2 Входные данные 3 4 2 3 3 2 3 Результат работы 7 1 1 1 2 2 4 1 4 3 2 3 1 3 4 Входные данные 1 3 2 1 2 1 3 Результат работы 1 1 1

Answer 1

n, m, k = map(int, input().split())

l = []

ans = []

for i in range(k):

   a, b = map(int, input().split())

   l.append(b)

if n == 1:

   for j in range(1, m + 1):

       if not j in l:

           ans += [1, j]

   print(len(ans) // 2)

   for i in range(0, len(ans), 2):

       print(ans[i], ans[i + 1])

Решение на 11 баллов

Answer 2

Для решения данной задачи можно воспользоваться следующим алгоритмом:

1. Создать пустой список для хранения координат слонов.

2. Проанализировать текущее расположение фигур на доске.

3. Для каждой фигуры, которая не может быть атакована другими фигурами, добавить ее координаты в список слонов.

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

Вот реализация данного алгоритма на языке Python:

pythonCopy code
def can_place(x1, y1, x2, y2):
    return abs(x1 - x2) != abs(y1 - y2)

def find_max_bishops(n, m, k, positions):
    bishops = []
    
    for i in range(k):
        x1, y1 = positions[i]
        can_place_bishop = True
        for x2, y2 in bishops:
            if not can_place(x1, y1, x2, y2):
                can_place_bishop = False
                break
        if can_place_bishop:
            bishops.append((x1, y1))
    
    print(len(bishops))
    for x, y in bishops:
        print(x, y)

# Чтение входных данных
n, m, k = map(int, input().split())
positions = []
for _ in range(k):
    x, y = map(int, input().split())
    positions.append((x, y))

# Вызов функции для поиска максимального количества слонов
find_max_bishops(n, m, k, positions)

Вы можете ввести данные в формате, указанном в примерах входных данных, и программа выдаст вам ответ в требуемом формате.