Ряды, серии и группы

В строках файла — номер ряда и номер занятого места, вперемешку. Как узнать, что происходит в каждом ряду?

Разложить позиции по рядам в словарь «ряд → множество мест», а потом в каждом ряду отсортировать места и смотреть на соседние.

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

data = [(5, 3), (9, 13), (5, 2), (5, 8),        (9, 10), (5, 4), (9, 20), (5, 3)]rows = {}for row, position in data:    if row not in rows:        rows[row] = set()    rows[row].add(position)for row in sorted(rows):    print(row, sorted(rows[row]))

if row not in rows проверяет, встречался ли такой ряд; rows[row] = set() создаёт для нового ряда пустое множество, rows[row].add(position) добавляет позицию. Повторное попадание (5, 3) новой позиции не создало.

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

несколько попаданий в одну светящуюся точку

да, если важен только факт свечения

несколько записей об одном занятом месте

да, если это повторные сведения

два файла одинакового размера

нет, это два файла

два товара одинаковой цены

нет, это два товара

несколько заявок на один объект

зависит от того, нужны ли ID и число заявок

Если для одинаковой позиции нужно сохранить, например, минимальный номер заявки, одного множества недостаточно. Нужно хранить соответствие «позиция → минимальный ID заявки» — тоже словарём.

В ряду заняты места 4, 7, 12, 16. Где есть ровно два свободных места подряд между занятыми?

Между соседними занятыми местами a и b свободно b − a − 1 мест: ровно два — там, где b − a = 3.

Между местами 4 и 7 свободны 5 и 6: сами занятые места в промежуток не входят.

Соседними здесь называются соседние элементы отсортированного списка занятых мест, а не соседние строки файла.

Для условия «выбрать максимальный номер ряда, а внутри него минимальный номер подходящего свободного места» можно сразу задать нужный порядок просмотра: ряды по убыванию, места по возрастанию. Тогда подходит первое найденное решение:

data = [(5, 4), (8, 11), (5, 12), (8, 3),        (5, 7), (8, 8), (5, 16)]places = sorted(set(data), key=lambda x: (-x[0], x[1]))answer = Nonefor i in range(len(places) - 1):    row1, seat1 = places[i]    row2, seat2 = places[i + 1]    if row1 == row2 and seat2 - seat1 == 3:        answer = (row1, seat1 + 1)        breakprint(*answer)

Сама сортировка уже учитывает приоритеты ответа. Проверка row1 == row2 обязательна: соседние записи списка могут относиться к разным рядам. Выводим seat1 + 1, потому что seat1 — занятое место, а нужно первое свободное после него. В ряду 5 тоже есть пара 4 и 7, но ряд 8 больше и просматривается раньше.

Различай условия — выбери формулировку:

ровно два свободных, с обеих сторон занятые

b - a == 3

не менее двух свободных между занятыми

b - a >= 3

любые два соседних свободных места

подходят и части длинного промежутка, и края ряда

«Перед креслом свободны все кресла с тем же номером» — как искать, если важны не места в ряду, а один номер кресла во всех рядах?

Собрать столбец: ключом словаря служит номер кресла, а значениями — номера рядов. Дальше всё как с местами в ряду.

Так же решается и «перед ним как можно больше свободных кресел подряд». Ряды нумеруются от сцены, поэтому «перед» значит «в рядах с меньшими номерами».

Пусть в зале 10 рядов, а кресло номер 5 занято в рядах 3 и 7. Свободные участки столбца — ряды 1–2, 4–6 и 8–10. Перед креслом в конце участка свободны все остальные кресла участка: в ряду 6 перед ним свободны ряды 4 и 5. Чтобы не обрабатывать отдельно последний участок, после всех занятых рядов добавляют условный занятый ряд M + 1, а до них считают занятым ряд 0:

m = 10column = [3, 7]best = Noneprev = 0for occupied in sorted(column) + [m + 1]:    if occupied - prev >= 2:        free_before = occupied - prev - 2        seat_row = occupied - 1        if best is None or free_before > best[0]:            best = (free_before, seat_row)    prev = occupiedprint(*best)

Участок от prev + 1 до occupied − 1 содержит occupied − prev − 1 свободных кресел, а перед последним из них — на одно меньше. Строгое сравнение > оставляет ряд ближе к сцене при равенстве: участок 8–10 тоже даёт 2, но ряд 10 дальше. Совсем пустой столбец даёт M − 1 свободных кресел перед последним рядом — его нельзя пропустить, хотя в файле этого номера нет.

Отмечены позиции 2, 3, 4, 8, 9, 10, 11, 20. Как найти самую длинную непрерывную серию?

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

Здесь три непрерывные серии — 2–4, 8–11 и 20 — длиной 3, 4 и 1.

Код для максимальной длины серии:

positions = sorted(set([10, 2, 3, 4, 8, 9, 11, 20, 3]))current = 0best = 0previous = Nonefor position in positions:    if previous is not None and position == previous + 1:        current += 1    else:        current = 1    if current > best:        best = current    previous = positionprint(best)

Почему при разрыве current = 1? Потому что текущая позиция уже начинает новую серию. Повтор позиции 3 убран множеством: дважды светящаяся точка — одна точка.

Если нужно количество максимальных непрерывных серий длиной не менее трёх, серию учитывают в момент разрыва — и ещё раз после цикла. Пройди программу по шагам на позициях, где последняя серия заканчивает ряд:

positions = [5, 8, 9, 10]line_count = 0current = 0previous = Nonefor position in positions:    if previous is not None and position == previous + 1:        current += 1    else:        if current >= 3:            line_count += 1        current = 1    previous = positionif current >= 3:    line_count += 1print(line_count)

Последняя проверка после цикла обязательна. Серия обычно учитывается при появлении разрыва, а после последнего элемента нового значения уже нет — завершающего разрыва программа не увидит, и единственная линия 8, 9, 10 потерялась бы: программа вывела бы 0. В подборке есть именно такие задачи о линиях, ограниченных тёмными точками или краем экрана: длинная непрерывная серия считается одной линией.

Одна и та же серия 10, 11, 12, 13, 14 даёт разные ответы в зависимости от вопроса — выбери вопрос:

максимальную длину серии

5

максимальные непрерывные серии длиной ≥ 3

1

все последовательные тройки внутри неё

310 11 12, 11 12 13, 12 13 14

Для сравнения результатов по рядам два приоритета записывают явно: больше линий, а при равенстве больше номер ряда — line_count > best_count or (line_count == best_count and row > best_row). То же самое делает сравнение кортежей (line_count, row) > (best_count, best_row).

А если внутри линии разрешены тёмные точки — не больше k подряд?

Это та же серия, только продолжается она, пока промежуток между соседними светлыми точками не больше k.

Длина такой линии — количество всех её точек, светлых и тёмных. Тогда новая позиция продолжает серию, если position - previous <= k + 1: между ними position − previous − 1 ≤ k тёмных точек. Длина линии — последняя позиция − первая + 1, а не число отмеченных позиций.

positions = [2, 3, 7, 8, 15]k = 3best = 0first = previous = Nonefor position in positions:    if previous is None or position - previous > k + 1:        first = position    best = max(best, position - first + 1)    previous = positionprint(best)

Между 3 и 7 три тёмные точки — допустимо, линия идёт от 2 до 8 и содержит 7 точек. Между 8 и 15 тёмных шесть, поэтому 15 начинает новую линию.

Как найти светлые точки, у которых все другие светлые точки ряда дальше чем на D?

Достаточно проверить двух ближайших соседей в отсортированном ряду: если и они дальше D, остальные — тем более.

Для позиции с индексом i отсортированного списка:

positions = [2, 3, 10, 20, 24]distance = 4count = 0for i in range(len(positions)):    left_ok = (i == 0               or positions[i] - positions[i - 1] > distance)    right_ok = (i == len(positions) - 1                or positions[i + 1] - positions[i] > distance)    if left_ok and right_ok:        count += 1print(count)

Изолирована только точка 10. У точки 20 сосед 24 на расстоянии ровно 4 — «дальше чем на 4» не выполнено. Проверки i == 0 и i == len(positions) - 1 стоят первыми: у крайних точек соседа с одной стороны нет, и короткое вычисление or не обращается к несуществующему индексу.

Нужен лидер продаж: по каждому артикулу — сколько продано и сколько осталось. Как собрать эти числа?

Накапливать суммы и количества в словаре по ключу-артикулу, а лучший ключ выбирать кортежем приоритетов.

Например, по каждому товару известны артикул, цена и статус: 0 — продан, 1 — ещё в магазине. Дорогими считаются товары дороже средней цены всех товаров. Нужно найти лидера продаж среди дорогих артикулов: больше всего проданных единиц, при равенстве — дороже, затем — меньше осталось. Количества по артикулу считают через get:

items = [(101, 500, 0), (101, 500, 0), (101, 500, 1),         (205, 900, 0), (205, 900, 1), (205, 900, 1),         (307, 120, 0), (307, 120, 0), (307, 120, 0),         (412, 700, 0), (412, 700, 0), (412, 700, 1)]average = sum(p for _, p, _ in items) / len(items)sold, left, price = {}, {}, {}for art, p, status in items:    price[art] = p    if status == 0:        sold[art] = sold.get(art, 0) + 1    else:        left[art] = left.get(art, 0) + 1best = max((sold.get(a, 0), price[a], -left.get(a, 0), a)           for a in price if price[a] > average)print(best[3], best[0] * best[1], -best[2])

Средняя цена 555, дорогих артикулов два: 205 и 412. У 412 продано больше — 2 единицы на 1400 рублей, осталась одна. Артикул 307 продан трижды, но он дешёвый и в выбор не входит. Кортеж (продано, цена, −осталось, артикул) записывает приоритеты так же, как ключ сортировки в рейтинге: минус у «меньше осталось».

Так же решаются задачи о домах и подъездах: словарь «дом → (подъезд → номер заявки)» хранит для каждого подъезда наибольший или наименьший номер заявки, а самая длинная серия подряд идущих подъездов ищется счётчиком серии.

• По рядамсловарь «ряд → множество позиций»
• Свободные местамежду a и b свободно b − a − 1
• Столбецключ — номер кресла, значения — ряды
• Серия+1 — продолжение, иначе заново; после цикла — ещё раз
• Изолированная точкапроверить двух ближайших соседей
• По ключусуммы в словаре, лучший — кортежем приоритетов