Обмен и назначение на Python: как решать + 11 задач с проверкой

Тема «обмен и назначение» — про задачи, где одну и ту же цель можно закрыть разными способами: купить «по одному» или «пакетами», обменять ресурсы по фиксированным правилам, распределить объекты по местам/парам. В олимпиадных условиях это часто выглядит как «есть несколько тарифов/наборов, можно брать сколько угодно, иногда допускается взять с запасом, лишнее пропадает». Пример — удержать пост популярным c часов, покупая по 1 часу или блоками по 7 часов.

Как распознать приём:

• в условии 2–3 варианта действия с разной «ценой» и «размером шага» (1 час vs 7 часов; пачки 1, 7, 49…);
• числа большие (до сотен миллионов), значит нельзя делать динамику по c;
• разрешён «перерасход» (перекупить часы/жетоны) или есть округление вниз/вверх;
• нужно минимум/максимум, а решение похоже на сравнение нескольких кандидатов.

Суть приёма: мы не перебираем все количества покупок. Вместо этого нормализуем варианты (иногда полезно поменять местами два способа, чтобы «базовый» шаг был 1 или самый выгодный), считаем деление с остатком и проверяем несколько разумных кандидатов около границы (например, сколько 7-часовых пакетов взять и чем добить). Это ускоряет решение до O(1) или O(количество разрядов), потому что кандидатов мало.

С чего начать учиться:

• потренируйте целочисленное деление и остаток: c // 7, c % 7, «округление вверх» через (c + 6) // 7;
• научитесь быстро отбрасывать невыгодный пакет: если b >= 7 * a, пакет не нужен;
• держите ответ через присваивание: ans = min(ans, candidate);
• при степенях 7 — думайте «по разрядам» (как запись числа в системе счисления) и проверяйте переносы;
• следите за переполнением: используйте 64-битные целые.

Ниже — задачи с автопроверкой и разбором подхода: от простых сравнений тарифов до распределения по парам и пачек по степеням 7.