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

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

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

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

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

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

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

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

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

Решение (Python)

f = open(’m6_26_18_04__3u8y8.txt’)
n = map(int, f.readline().split())
# Сортировка по ряду и номеру пикселя
a = sorted([list(map(int, i.split())) for i in f])
l_max = 0; l = 1; num_r = -1
for i in range(1, len(a)-1):
    # Если номер ряда совпадает и пиксели соседние увеличиваем счетчик
    if (a[i][0] == a[i+1][0]) and (a[i+1][1]-a[i][1] == 1):
        l += 1
    # Если нет, то обновляем максимум и обнуляем счетчик
    else:
        if l > l_max:
            l_max = l
            num_r = a[i][0]
        l = 1
if l > l_max:
    l_max = l
    num_r = a[-1][0]
print(l_max, num_r)

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

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

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

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

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

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

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

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

С её помощью мы посчитаем количество точек в каждом ряду. В ячейку запишем и растянем до конца таблицы следующую формулу:

С помощью неё мы отделим ряды, и начавшиеся и кончившиеся светлой точкой.

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

Решение (Python)

f = open(’m7_26_18_04__3u8yv.txt’)

n = int(f.readline())

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

new_tr = [[0] * 10_001 for i in range(10_001)] # матрица свободных и занятых мест
for x, y in tr:
    new_tr[x][y] = 1 # отмечаем, что место - занято

max_count = 1
row = 0

for i in range(len(new_tr)):
    # если первое и последнее место в ряду - заняты и при этом в ряду максимальное количество светлых точек
    if new_tr[i][1] == new_tr[i][-1] == 1 and sum(new_tr[i]) > max_count:
        max_count = sum(new_tr[i])
        row = i
print(max_count, row)

Решение при помощи электронных таблиц:

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

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

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

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

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

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

Условие обеспечивает попадание трех прижившихся саженцов в один ряд, - нахождение трёх прижившихся саженцев через одно свободное место друг от друга. Если условия выполнились - записываем в ячейку номер первого неприжившегося саженца из 2-х.

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

 

Программное решение

f = open(’26_dif_2__40zqo.txt’)

n = int(f.readline())

tr = [list(map(int, i.split())) for i in f] # считываем файл
tr.sort() # сортируем значения в столбцах по возрастанию

max_row = 0 # максимальный ряд
min_place = 10 ** 10 # минимальной подходящее место в максимальном ряду

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:
            if max_row == tr[i][0]:
                min_place = min(min_place, tr[i][1] + 1) # вычисляем минимальное место в максимальном ряду
            else:
                min_place = tr[i][1] + 1
            max_row = tr[i][0]

print(max_row, min_place)

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

Откроем файл в электронной таблице и удалим первую строку. С помощью настраиваемой сортировки отсортируем файл следующим образом: Столбец А по убыванию и столбец В по возрастанию. В ячейку запишем 0 и в ячейку запишем формулу:

С помощью сочетания клавиш откроем меню поиска в столбце С найдём первую 1. Как видим, между местами 698 и 704 ряда 1928 есть 5 свободных мест. В ответ указываем номер ряда и номера мест в порядке возрастания.

Решение (Python)

f = open(’26_4.txt’)
n = int(f.readline())
a = [] # список, в котором будут записаны координаты занятых мест
for line in f:
    numbers = list(map(int, line.split()))
    a.append(numbers)
a = sorted(a) # сортируем по возрастанию значения в столбцах
for i in range(len(a)-1):
    # если ряд двух рядом стоящих в списке мест совпадает и между ними есть 5 свободных мест
    if (a[i][0] == a[i+1][0]) and (a[i+1][1] - a[i][1] == 6):
        print(a[i], a[i+1])

Решение 1

f = open("26.txt")
n, m, k = map(int, f.readline().split())
row = [[] for i in range(k + 1)]

for i in range(n):
    x, y = map(int, f.readline().split())
    row[y].append(x)

mn_r =  10 ** 10# минимальный ряд
mn_i = 0 # минимальное место
for i in range(1, len(row) - 1):
    # из двух (вертикальных) соседних рядов берем макс место
    # (номер горизонтального ряда  - mn_r), за ним все будут свободны;
    # соответствеенно, чем он меньше, тем ближе к сцене
    if max(row[i + 1] + row[i]) <= mn_r:
        mn_r = max(row[i + 1] + row[i])
        mn_i = i
print(mn_r+1, mn_i)

Решение 2

f = open("26.txt")
n, m, k = map(int, f.readline().split())
a = [[0, m + 1] for i in range(k)]

for i in f:
    x, y = map(int, i.split())
    a[y-1].append(x)

mx = 0 # максимальная длина пустых мест
mn_r = 0 # минимальный ряд
mn_i = 0 # минимальное место
for i in range(k - 1):
    t1 = sorted(a[i], reverse=True)
    t2 = sorted(a[i + 1], reverse=True)
    spot1 = t1[0] - t1[1] - 1 # выясняем сколько пустых мест за текщум
    spot2 = t2[0] - t2[1] - 1 # и за соседним
    if min(spot1, spot2) > mx: # если пустых мест больше чем нашлось раньше
        mx = min(spot1, spot2) # то обновляем максимум
        mn_r = m - mx + 1 # соханяем номер ряда
        mn_i = i # сохраняем номер места
print(mn_r, mn_i + 1)

Решение 1

f = open("2.txt")
n, m, k = map(int, f.readline().split())
row = [[m+1] for i in range(k)]

for i in range(n):
    x, y = map(int, f.readline().split())
    row[y-1].append(x)

mx_r = 0# максимальный ряд
mx_i = 0 # максимальное место
for i in range(len(row) - 1):
    # из двух (вертикальных) соседних рядов берем макс место
    # (номер горизонтального ряда  - mx_r), перед ним все будут свободны;
    # соответствеенно, чем он больше, тем дальше от сцене
    if max(row[i + 1] + row[i]) >= mx_r:
        x = max(row[i + 1] + row[i])
        while (x in row[i] or x in row[i + 1]
               or len([p for p in row[i] if p < x]) > 2
               or len([p for p in row[i + 1] if p < x]) > 2):
            x -= 1
        if x >= mx_r:
            mx_r = x
            mx_i = i
print(mx_r, mx_i+2)

Решение 2

f = open("26.txt")
n, m, k = map(int, f.readline().split())
a = [[0, m + 1] for i in range(k)]

for i in f:
    x, y = map(int, i.split())
    a[y-1].append(x)

# дублируем массив a удаляя из него до 2х занятых мест минимальных рядов
b = []
for i in range(k):
    b.append(sorted(a[i]))
    if len(b[i]) >= 4:
        b[i].pop(2)
        b[i].pop(1)
    elif len(b[i]) == 3:
        b[i].pop(1)

mx = 0
mx_i = 0 # минимальное место
for i in range(k - 1):
    # print(i, sorted(a[i]))
    t1 = sorted(b[i])
    t2 = sorted(b[i + 1])
    spot1 = t1[1] - t1[0] - 1 # выясняем сколько пустых мест перед текущим
    spot2 = t2[1] - t2[0] - 1 # и перед соседним

    # так как мы ранее удалили часть занятых мест, то нужно проверить, не заняты ли
    # найденные места, если заняты, то спускаемся на ряд ниже, в нем гарантированно
    # выполняются условия задачи
    row = min(spot1, spot2)
    while row in a[i] or row in a[i + 1]:
        row -= 1

    if row >= mx: # если найденный ряд выше чем нашлось ранее
        mx = row # то обновляем максимум
        mx_i = i # и сохраняем номер места
print(mx, mx_i + 2)