A. Давид и мешки с конфетами
Сгодится наивное решение, поскольку всего имеется 4 мешка. И по сути нужно сделать неупорядоченные выборки из 4-х, вначале по 1-му, затем по 2 и затем по 3 мешка. Если для какой-то выборки получается, что сумма конфет равна половине сумме всех конфет, то решение найдено, пишем YES. Иначе, если ни одна выборка не подошла, пишем NO.
Мое решение
B. Аня и минимизация
Если k==0, выводим само число.
Если у нас число состоит из 1-го символа.
В этом случае, если k == 1 (а теперь оно точно равно 1), то мы можем заменить это число на 0 (пишем "0"), а иначе — не можем (но в эту ветвь мы никогда не попадем).
Если число многозначное (n>1).
- Если первая цифра не 1, то меняем ее на '1' и делаем --k.
- Идем от второй цифры и до тех пор пока не закончится либо k, либо сами цифры. Если мы встречаем цифру отличную от 0, заменяем ее на 0, и делаем --k.
- Выводим измененную строку.
Мое решение
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: Я нашел косяк в своем решении. Что неверно в предыдущем утверждении?
Если групп нет, то значит никто в этой компании не сможет поехать на сборы, поскольку с ним нет другого полностью совместимого студента.
Алгоритм
- Выполняем сортировку на группы. С каждой группой связываем маску и суммарный опыт.
- Проходимся по оставшимся одиночкам. Если для одиночки А, находится подходящая группа G, то включаем его в эту группу (увеличиваем опыт группы на опыт A).
- Считаем суммарный опыт всех групп. Выводим его в качестве ответа.
Мое решение
