26.05 Поиск мест на поле (билеты, саженцы, матрицы)

Решение (Excel/LibreOffice)

Сначала перенесем данные из файла в Excel, скопировав и вставив с разделителем пробел, а также удалим первую строчку.

Настраиваемой сортировкой отсортируем в первую очередь по столбцу по возрастанию, во вторую - по столбцу по возрастанию.

Выделим полностью столбцы и , перейдём в раздел Данные и нажимаем на инструмент Удалить дубликаты, в появившемся окне выбираем Выделить все и нажимаем ОК (это удалит деревья, которые были по ошибке сняты дважды).

В LibreOffice Calc необходимо также выделить оба столбца, применить фильтр и перейти в раздел Фильтр по условию -> Стандартный фильтр.

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

Чтобы определить тройку мест в необходимом нам порядке, запишем в ячейку и растянем до конца таблицы следующую формулу:

Условия и обеспечивает попадание трех мест в один ряд, и - свободные места в нужных промежутках.

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

Решение (Python)

f = open(’m5_26_18_04__3u8xl.txt’)

n = int(f.readline())

old_tr = [list(map(int, i.split())) for i in f]
old_tr.sort()

tr = [] # список, в котором будут только уникальные координаты
for i in old_tr:
    if not(i in tr):
        tr.append(i)
#словарь, в котором в качестве ключа будет указан номер ряда,
#а в качестве значения будет список из занятых мест на этом ряду

matrix = [[0 for j in range(1001)] for i in range(1001)]
for i in tr:
    matrix[i[0]][i[1]] = 1
max_row = 0
place = 0
c = 0
for i in range(len(tr) - 2):
    # проверка, что у трёх рядом стоящих в списке мест совпадает ряд
    if tr[i][0] == tr[i + 1][0] == tr[i + 2][0]:
        # проверка, что между двумя подряд идущими местами есть одно место свободное
        if tr[i + 1][1] - tr[i][1] == tr[i + 2][1] - tr[i + 1][1] == 2:
            # проверка того, что слева и справа от этой тройки занятых мест есть свободные места
            temp_row = matrix[tr[i][0]] # список занятых и свободных мест текущего ряда
            # для проверки есть ли свободные места слева и справа от тройки используем функцию index,
            # которая возвращает индекс первого вхождения данного элемента
            # для проверки того, что слева есть свободные места мы начинаем поиск с 1-ого индекса,
            # так как отсчёт мест в ряду начинается с 1.
            if (tr[i][1] - temp_row.index(0,1,tr[i][1]) > 1
                    and tr[i+2][1] - temp_row.index(0,tr[i+2][1],len(temp_row))):
                max_row = tr[i][0]
                place = tr[i + 1][1]
print(max_row, place)