Разбор задач

A.    Бригада грузчиков

Для переноски тяжестей собирается бригада из n грузчиков-огров. Бригада может состоять из одного, трёх или пяти огров. Шрек, огр уровня Y, собирает бригаду огров разного уровня, уровень которых отличается не более чем на x от его уровня. Вам даны уровни всех грузчиков в бригаде. Определите уровень Шрека. 

Разбор. Это задача с Codeforces, контест VK Cup 2017 - Квалификация 1, задача A. Год поступления в университет. Данную задачу можно решать разными способами. Самый простой из них — положить все заданные числа в массив, отсортировать его и вывести медиану получившегося массива (то есть элемент, находящийся в его середине).

      B. Сеть порталов

Университету Магии выделили грант на создание лаборатории телепортаций. Провели тендер и закупили генератор магии, n порталов разной мощности и k распределителей. Для каждого распределителя известно число Ai слотов в нем и максимальная суммарная мощность Bi порталов, которые могут быть в него подключены, а для каждого портала известна потребляемая им мощность Ci.
Теперь необходимо составить схему подключения порталов к генератору с использованием распределителей с учетом следующих соображений. Для каждого i-го распределителя суммарная мощность порталов, включенных в него как напрямую, так и через другие распределители, не превосходит соответствующего значения Bi. Число порталов и распределителей, напрямую включенных в i-й распределитель, не превосходит Ai. При этом, в соответствии с правилами безопасности, в каждый распределитель можно подключать не более одного другого распределителя.
Гарантируется, что мощность генератора магии достаточна, чтобы выдержать подключение всех имеющихся устройств. Отметим также, что при необходимости к генератору можно подключить портал напрямую.
Напишите программу, которая найдет требуемую схему подключения устройств.

 Разбор. Эта задача, как и следующие, за исключением последней, с X Всероссийской командной олимпиады школьников по программированию 13-14 ноября 2009 года. Задача D. Электричество. Не влезай, убьет.
По условию задачи в наличии имеется:
              k распределителей
              n порталов
              1 генератор магии
Требуется подсоединить все порталы так, чтобы потребляемая ими мощность не превышала допустимую для распределителя. К распределителю можно подсоединить не более одного распределителя.
Основные идеи:
Не имеет смысла подключать фильтр к фильтру с меньшей максимальной нагрузкой.
Наиболее мощные приборы имеет смысл ставить ближе к розетке.

Решение.

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

С.    Разбиение Гноллов

Комбинаторика - она и в Холмах Гноллов комбинаторика. Каждый гнолл знает, что разбиения числа n на слагаемые - это набор целых положительных чисел, сумма которых равна n. При этом разбиения, отличающиеся лишь порядком слагаемых, считаются одинаковыми, поэтому можно считать, что слагаемые в разбиении упорядочены по неубыванию.

Например, существует 7 разбиений числа 5 на слагаемые:

5=1+1+1+1+1

5=1+1+1+2

5=1+1+3

5=1+2+2

5=1+4

5=2+3

5=5

В приведенном примере разбиения упорядочены лексикографически ‑ сначала по первому слагаемому в разбиении, затем по второму, и так далее. В этой задаче гноллу Гоше требуется по заданному разбиению на слагаемые найти следующее в лексикографическом порядке разбиение. Помогите ему.

Разбор. Это задача H. Следующее разбиение на слагаемые с X Всероссийской командной олимпиады школьников по программированию 13-14 ноября 2009 года. 

Решением задачи является генерация следующего комбинаторного объекта:

Дано разбиение

   5=1+1+3

1. Идём с конца, пока нельзя увеличить слагаемое
2. Увеличим слагаемое на минимальную величину
3. Допишем минимальный «хвост»

Когда можно увеличить слагаемое?

Первое слагаемое с конца нельзя увеличить

Второе слагаемое с конца можно увеличить

Например можно прибавить к нему последнее слагаемое

5=1+1+3   →   5=1+4

На сколько можно увеличить слагаемое?

Слагаемое можно увеличить на 1, если оно было меньше последнего хотя бы на 2

5=1+1+3   →   5=1+2+2

Иначе его надо увеличить на величину последнего слагаемого

5=1+2+2   →   5=1+4

Как дописать минимальный «хвост»?

Надо вывести хвост с суммой S, при этом последнее слагаемое которое было выведено перед ним равно K

Выведем несколько(возможно ноль) слагаемых K, а затем остаток

Остаток должен быть не меньше чем K

D.    Эльфы – такие эльфы

Эльфов, населяющих леса в окрестностях Одинокой горы, очень беспокоит активное строительство путей между городами людей. Недавно эльфийский резидент в Дейле выкрала секретный документ. Сотрудники первого отдела разведки подозревают, что это список пар городов, между которыми проложены пути. Попытавшись сопоставить номера городов с городами людей, сотрудники убедились, что это можно сделать.

Однако сотрудники второго отдела высказали другое предположение. Они предположили, что этот список --- это в точности список пар городов, между которыми нет путей. Попытавшись сопоставить номера городов с городами людей, они также убедились, что это можно сделать.

Трандуил в затруднении. Решив проверить, возможно ли такое, он попросил сотрудников третьего отдела выяснить, может ли так быть, что между некоторыми городами людей проложены пути, а между некоторыми --- нет, и существует самодвойственный список пар.

Список пар целых чисел от 1 до n называется самодвойственным, если можно занумеровать города так, чтобы он задавал все пары городов, между которыми есть путь, а можно перенумеровать города таким образом, чтобы тот же самый список задавал все пары городов, между которыми путей нет.

Помогите сотрудникам третьего отдела решить поставленную задачу.

Разбор. Это задача I. Самодвойственный документ с X Всероссийской командной олимпиады школьников по программированию 13-14 ноября 2009 года. Соответственно, разбор сделан в технике копи-паст. 

По условию задачи надо построить граф из n вершин

Первый отдел: пары чисел – это ребра графа

Второй отдел: пары чисел – это вершины между которыми ребра нет

Граф изоморфен своему дополнению

Когда ответ существует?

В полном графе из n вершин  n(n - 1)/2 ребер

Если n = 4k + 2 или n = 4k + 3, то ребер нечетное число – ответ «No»

Если n = 4k или n = 4k + 1, то ответ «Yes» 

E.    Красота эльфийского леса

Несколько отрядов эльфов были посланы на восстановление Пущи Драколесья после опустошительного пожара, вызванного извержением Одинокой горы.

Отрядам выделены одинаковые участки, на которых они высаживают деревья. На участке деревья одного вида занимают ровно один ряд. Прошел назначенный срок, и распорядитель работ затребовал и получил отчеты о результатах посадочных работ. В сборном отчете данные о количестве заполненных рядов каждым отрядом были приведены в порядке невозрастания. Знакомясь с отчетом, Трандуил обратил внимание на тот факт, что количество рядов, посаженных каждым отрядом, является делителем числа видов деревьев (или нулем).

Красивый математический факт восхитил Трандуила. Его заинтересовало, сколько еще рядов смогут суммарно посадить отряды так, чтобы после каждого посаженного ряда сохранялось указанное свойство: количество рядов, посаженное отрядом, является делителем числа видов деревьев (или нулем).

Разбор. Это задача K. Красивая таблица результатов с X Всероссийской командной олимпиады школьников по программированию 13-14 ноября 2009 года. 

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

У количества рядов не может быть более 24 подряд идущих делителей, так как минимальное число, которое делится на все числа от 1 до 24 это ― 5354228880.

F.    Трудный выбор

Достигнув необходимого возраста, наш герой отправляется в центральный мир АВ, дабы выучить всё что должен знать дворянин, и заодно отдать свой долг империи и отслужить на звёздном флоте. Путь тяжел и долог и почти на каждом шагу надо делать выбор. Результат каждого выбора ‑ некоторое целое неотрицательное число (штраф). Чем меньше будет суммарный штраф после прохождения пути, тем лучше. Но горе герою, если штраф будет выражаться четным числом! 

Задача. Набрать в сумме по всем строкам минимальный штраф, который должен быть нечетным числом. 

Во входных данных имеется последовательность строк (не более 10000). Каждая строка состоит из двух непустых слов, разделенных пробелом. Слово - последовательность латинских букв и цифр. Длина каждого слова не превосходит 100 символов. Штраф - сумма цифр в слове.

Разбор.  Задача навеяна демоверсией ЕГЭ по информатике 2017 года. Последнее время в задачах #27 ЕГЭ часто используются однопроходные алгоритмы. В данной задаче имеется дополнительная техническая трудность, связанная с необходимостью прочитать неизвестно сколько строк. В Паскале эта проблема решается конструкцией вида

while not seekEOF do begin read(...); ...  end;

Для каждой строки извлекаем цифры, суммируем, получаем пару чисел. Чтобы получить минимально возможную сумму по всем строкам, будем брать из каждой пары самое маленькое число. Если полученная при этом сумма будет четной, её необходимо увеличить. Для этого достаточно в одной из пар, где числа имеют разные остатки при делении на 2, заменить ранее выбранное 

число на другое число из той же пары. При этом разница между числами в паре должна быть минимально возможной. Если во всех парах оба числа имеют одинаковый остаток при делении на 2, получить нужную сумму невозможно.