A. Давид и мешки с конфетами

Сгодится наивное решение, поскольку всего имеется 4 мешка. И по сути нужно сделать неупорядоченные выборки из 4-х, вначале по 1-му, затем по 2 и затем по 3 мешка. Если для какой-то выборки получается, что сумма конфет равна половине сумме всех конфет, то решение найдено, пишем YES. Иначе, если ни одна выборка не подошла, пишем NO.

Мое решение

B. Аня и минимизация

Если k==0, выводим само число.

Если у нас число состоит из 1-го символа.

В этом случае, если k == 1 (а теперь оно точно равно 1), то мы можем заменить это число на 0 (пишем "0"), а иначе — не можем (но в эту ветвь мы никогда не попадем).

Если число многозначное (n>1).

1. Если первая цифра не 1, то меняем ее на '1' и делаем --k.
2. Идем от второй цифры и до тех пор пока не закончится либо k, либо сами цифры. Если мы встречаем цифру отличную от 0, заменяем ее на 0, и делаем --k.
3. Выводим измененную строку.

Мое решение

C. Анади и домино

Ну во-первых. Что такое сам по себе набор домино? Это полный граф из 6 вершин, у которого вдобавок на каждой вершине есть петля. Ребрами такого графа и будут костяшки домино. Т.е. если бы можно было класть костяшки домино на такой граф, то можно было бы на каждое ребро положить по штуке, и это с учетом всех оговоренных в задаче ограничений.

Нам же дается граф в котором количество вершин не более 7-ми.

Если число вершин данного графа 6 и меньше.

То это подграф графа домино. В этом случае на все его ребра также можно положить по костяшке. Поэтому мы просто возвращаем число m (количество данных ребер).

Если число вершин данного графа равно 7.

Надо свести задачу к первому типу. Помните анекдот про программиста и чайник?

Поэтому надо объединить какие-то две вершины в одну. При объединении у пары вершин A и B, с количеством ребер E(A) и E(B) найдутся общие ребра, обозначим их количество C. В этом случае после объединения мы получим граф из 6 вершин с количеством ребер равным m2(A, B) = m — C. В общем надо выполнить полный перебор всех пар вершин и найти такую пару, для которой m2 будем максимальным, и в качестве результата нужно вывести это значение m2 = max(by(A, B), m2(A, B)).

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

Мое решение

D. Марчин и сборы

Вначале давайте рассмотрим пару человек. Они смогут поехать вместе только если маски их знаний полностью совпадают.

Теперь можно расширить это понятие до группы человек. Группа человек с одинаковой маской знаний может спокойно ехать на сборы. С группой мы также можем связать эту маску G. После разбиения на группы останутся одиночки, с оригинальным набором знаний.

Кого может еще взять с собой группа?

• Любого одиночку, чья маска B будет подмаской группы: G or B == G.
• Абсолютно любую группу.

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

UPD: Я нашел косяк в своем решении. Что неверно в предыдущем утверждении?

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

Алгоритм

1. Выполняем сортировку на группы. С каждой группой связываем маску и суммарный опыт.
2. Проходимся по оставшимся одиночкам. Если для одиночки А, находится подходящая группа G, то включаем его в эту группу (увеличиваем опыт группы на опыт A).
3. Считаем суммарный опыт всех групп. Выводим его в качестве ответа.

Мое решение