Задание 26 · Обработка данных с сортировкой
Практика и итог
Вся тема на одной странице: как решилась задача темы, главное из подтем, порядок решения и частые ошибки.
Одна задача — вся тема
Задача темы — камера хранения: сколько пассажиров сдадут багаж и в какую ячейку положит последний — читается как в подтеме 1, а решается в подтеме 6 исполнением правил. Пролистай версии: точками отмечены строки, которых не было в предыдущей.
- Подтема 1, «Записи и сортировка»: записи — кортежи, порядок прихода. Точками отмечены новые строки.
- Подтема 6, «Состояние процесса»: что помнить: время каждой ячейки.
- Подтема 6, «Правило дословно»: наименьший номер, строго раньше. Ответ задачи темы — 859 11.
Записи и сортировка нужны всем задачам темы. Где выбирают лучшее — работает жадный выбор (подтема 2), цепочки и пары (3), серии в рядах (4) и интервалы (5); где правила заданы — их исполняют дословно, как здесь. Дополнительный урок добавляет окно, кучу и сложные цепочки.
Карта темы
Каждая подтема дала свой приём для одного прохода по записям, и любое решение собирается из них. Сверху — путь от файла к ответу, ниже — по блоку на подтему. Заголовок блока ведёт на подтему.
- Файлпо описанию формата
- Записисортировка по ключу
- Проходвыбрать лучшее или исполнить правила
1Записи, сортировка и рейтинг
- записькортеж полей одного объекта
key=lambda r: (-r[1], r[0])минус — «больше выше», второе поле — при равенстве
2Жадный выбор
- больше всегобрать от самых маленьких
- второй критерийзакрепить количество, потом улучшать
3Цепочки коробок и пары
- матрёшкабрать самую большую подходящую
- парыдва указателя с концов
4Ряды, серии и группы
- свободно междуb − a − 1 мест
- последняя серияучесть после цикла
5Интервалы и события
- мероприятиябрать по раннему окончанию
- нагрузкасобытия +1 и −1 по времени
6Моделирование процесса
free_atкогда освободится каждая ячейка- правилодословно: «со следующей минуты» — строго <
7Пары, окно и сложные цепочкидополнительный урок
- окнолевая граница догоняет правую
- кучабыстро достаёт наименьшее
Как решать
Любое задание 26 решается одним порядком из пяти шагов. Каждому шагу ты уже учился — под ним номера подтем:
Если ответ — два числа, проверь второе отдельно: оно часто считается другим приёмом, чем первое.
Частые ошибки
Шесть ошибок встречаются чаще других, и каждую ловит один вопрос к себе. Выбери ошибку — увидишь, как её исправить, и вопрос, который её ловит:
- заголовок как данные
- количество объектов прочитано как объект → первые строки — заголовок. Спроси себя: совпадает ли длина списка с N из файла?подтема 1
- поля по отдельности
- начала и окончания отсортированы раздельно → сортируют записи целиком. Спроси себя: есть ли каждая запись в исходных данных?подтема 1
- break без сортировки
- цикл остановлен на первом неподходящем → сначала сортировка, потом break. Спроси себя: а если маленький объект стоит в конце?подтема 2
- второй критерий сразу
- сразу выбран наибольший объект → закрепить количество, потом улучшать. Спроси себя: не стало ли объектов меньше?подтема 2
- последняя серия
- серия в конце ряда не учтена → проверка ещё раз после цикла. Спроси себя: что, если ряд кончается серией?подтема 4
- та же минута
free_at[i] <= start→free_at[i] < start. Спроси себя: можно ли занять ячейку в минуту освобождения?подтема 6
Итог
Тема пройдена: задача темы решена от чтения файла до ответа 859 11. Вот что взять с собой.
- ПорядокЗаписи, порядок, способ, проход, проверка.
- ЗаписиКортежи и сортировка по ключу.
- ВыборЖадно: от маленьких, по раннему окончанию, указатели.
- ПравилаИсполняются дословно — «со следующей минуты» строго.
- Задача темы859 пассажиров, последний — в ячейке 11.
Проверьте себя
Ответь сначала сам, потом открой ответ.
Нужно сохранить на диск как можно больше файлов. В каком порядке их брать?
ОтветСкрыть ответ
От самых маленьких: каждый маленький оставляет больше места остальным.
Ячейка освободилась в минуту 404. Можно ли положить в неё багаж в 404? А в 405?
ОтветСкрыть ответ
В 404 нельзя — только со следующей минуты, поэтому в программе free_at[i] < start. В 405 можно.
Почему заявки задачи темы сортируют перед проходом?
ОтветСкрыть ответ
Пассажиров обслуживают в порядке прихода, а в файле заявки перемешаны: requests.sort() упорядочивает их по времени сдачи.
Места в ряду заняты под номерами 3 и 8. Сколько свободных мест между ними?
ОтветСкрыть ответ
8 − 3 − 1 = 4: места 4, 5, 6 и 7.
Практика
Для проверки ответов нужен JavaScript. Условия, подсказки и решения доступны ниже.
Свободные кресла перед местом
В файле 26-8.txt в первой строке записаны количество занятых мест N, число рядов M и число мест в каждом ряду K, в каждой следующей — номер ряда и номер занятого места. Ряды нумеруются от сцены. Нужно купить билет на свободное место, перед которым (в рядах с меньшими номерами) как можно больше идущих подряд свободных кресел с тем же номером места. Если подходящих мест несколько, выбирают ряд ближе к сцене. Запиши номер ряда, затем количество свободных кресел перед выбранным местом. (Подтема 4.)
Введите два числа через пробел в том порядке, в каком их спрашивают.
Подсказка
Словарь «номер места → занятые ряды» и условные занятые ряды 0 и M + 1.
Решение
523 115: словарь «номер места → занятые ряды» и условные занятые ряды 0 и M + 1; пустые столбцы тоже проверяются.
Решение программой
with open('26-8.txt') as f: n, m, k = map(int, f.readline().split()) data = [list(map(int, line.split())) for line in f] col = {}for r, s in data: col.setdefault(s, set()).add(r)best = Nonefor s in range(1, k + 1): prev = 0 for o in sorted(col.get(s, set())) + [m + 1]: if o - prev >= 2: cand = (o - prev - 2, -(o - 1)) if best is None or cand > best: best = cand prev = oprint(-best[1], best[0])Ответ: 523 115
Самое позднее окончание
В файле 26-10.txt в первой строке записано количество заявок N, в каждой следующей — время начала и время окончания мероприятия в минутах от начала суток. Следующее мероприятие можно начать в момент окончания предыдущего. Определи максимальное количество мероприятий, которые можно провести, и самое позднее время окончания последнего мероприятия при таком количестве. (Подтема 5.)
Введите два числа через пробел в том порядке, в каком их спрашивают.
Подсказка
Жадный выбор по окончанию; последнее — с самым поздним окончанием.
Решение
57 1439: первые 56 мероприятий жадные, последнее — с самым поздним окончанием среди начинающихся не раньше окончания предпоследнего.
Решение программой
with open('26-10.txt') as f: f.readline() data = [list(map(int, line.split())) for line in f] def greedy(meetings, pause): sel = [] for s, f in sorted(meetings, key=lambda m: (m[1], m[0])): if not sel or s >= sel[-1][1] + pause: sel.append((s, f)) return sel sel = greedy(data, 0)end = sel[-2][1]print(len(sel), max(f for s, f in data if s >= end))Ответ: 57 1439
Скидка на каждый второй
В файле 26-5.txt в первой строке записано количество товаров N, в каждой следующей — цена товара в рублях. На каждый второй товар дороже 1000 рублей предоставляется скидка 20 %; порядок товаров в чеке определяет продавец так, чтобы общая скидка была наименьшей; итоговая стоимость покупки округляется вверх до целого числа рублей. Запиши итоговую стоимость, затем цену самого дорогого товара, на который предоставлена скидка. (Подтема 2.)
Введите два числа через пробел в том порядке, в каком их спрашивают.
Подсказка
Скидку получает дешёвая половина товаров дороже 1000; округляется только итог.
Решение
7211541 3038: скидку получают самые дешёвые из товаров дороже 1000 — половина из них; округляется только общая сумма.
Решение программой
with open('26-5.txt') as f: f.readline() a = [int(line) for line in f] big = sorted(p for p in a if p > 1000)disc = big[:len(big) // 2]rest = sum(a) - sum(disc)print(rest + (4 * sum(disc) + 4) // 5, max(disc))Ответ: 7211541 3038
Матрёшка изнутри наружу
В файле 26-6.txt в первой строке записано количество коробок N, в каждой следующей — длина стороны коробки. Одну коробку можно вложить в другую, если её сторона хотя бы на 10 меньше. Определи наибольшее количество коробок в одной «матрёшке» и наименьшую возможную сторону самой большой коробки при таком количестве. (Подтема 3.)
Введите два числа через пробел в том порядке, в каком их спрашивают.
Подсказка
Для наименьшей внешней коробки цепочку строят от самой маленькой.
Решение
944 9993: цепочку строят изнутри наружу, от самой маленькой коробки.
Решение программой
with open('26-6.txt') as f: f.readline() a = [int(line) for line in f] sel = []for x in sorted(a): if not sel or x - sel[-1] >= 10: sel.append(x)print(len(sel), sel[-1])Ответ: 944 9993
Контейнеры по 250
В файле 26-3.txt в первой строке записаны два числа, из которых нужно только второе — количество грузов N, в каждой следующей — масса груза. Контейнеры вместимостью 250 заполняют так: грузы перебирают по убыванию массы и кладут в контейнер каждый, который ещё помещается; затем то же повторяют для оставшихся грузов со следующим контейнером. Определи количество контейнеров и загрузку предпоследнего контейнера. (Подтема 6.)
Введите два числа через пробел в том порядке, в каком их спрашивают.
Подсказка
Процедура буквально: break при неудаче нельзя — следующие грузы легче.
Решение
1008 250: процедура выполняется буквально; break при неудаче нельзя — следующие грузы легче.
Решение программой
with open('26-3.txt') as f: f.readline() a = [int(line) for line in f] rest = sorted(a, reverse=True)loads = []while rest: left, load = [], 0 for w in rest: if load + w <= 250: load += w else: left.append(w) loads.append(load) rest = leftprint(len(loads), loads[-2])Ответ: 1008 250