Как мы в ВСК провели олимпиаду по программированию для сотрудников

[remova]

Молодцы! Олимпиадного программирования многие боятся, потому, полагаю, если бы все задачи были бы как первая, результаты были бы лучше, а людей пришло бы больше. Ну и, понятно, при условии, если бы успокоили всх заранее, что только такие, простые, задачи будут. Спасибо за ценный опыт!

[developerxyz]

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

[dvserg]

Странно, что один смог решить. Без рюшей там строк 50 кода на С++

[dvserg]

Добрый день, Игорь.

Вот идея уважаемого developerxyz . Я посмел удивиться ее несложности, и тому, что участники не все решили данную задачу. А 50 строк - это примерно столько потребовалось сделать задачу на-коленке.

[Alexandroppolus]

ДП - не слишком известная штука. Причем многие, кто об этом слышал, не имеют навыков. Без них очень маловероятно смекнуть это за ограниченное время.

Меня куда сильнее удивило, что целых 6(!) программистов не справились с первой. Это на 6 человек больше, чем должно быть.

[developerxyz]

Вторая задача — упрощенная версия задачи 505C — Мистер Китаюта, охотник за сокровищами

[Alexandroppolus]

В третьей задачи действительно одна формула.

Если у нас M мышей и K = Math.floor(totalMinutesToTest/poisonTime) раундов кормлений, то можем найти одну ядовитую среди (K+1)^M кормушек. Это обобщение известной задачи с одним раундом, и легко доказывается через бином Ньютона.

Решением этой задачи были математические выкладки, записанные в комментарии к коду? )