Комментарии 9
Молодцы! Олимпиадного программирования многие боятся, потому, полагаю, если бы все задачи были бы как первая, результаты были бы лучше, а людей пришло бы больше. Ну и, понятно, при условии, если бы успокоили всх заранее, что только такие, простые, задачи будут. Спасибо за ценный опыт!
Оптимальный метод решения — динамическое программирование. Просто продублируем каждый элемент массива и проверим, существует ли подмножество с необходимой суммой.
Странно, что один смог решить. Без рюшей там строк 50 кода на С++
Добрый день, Игорь.
Вот идея уважаемого developerxyz . Я посмел удивиться ее несложности, и тому, что участники не все решили данную задачу. А 50 строк - это примерно столько потребовалось сделать задачу на-коленке.
Вторая задача — упрощенная версия задачи 505C — Мистер Китаюта, охотник за сокровищами
В третьей задачи действительно одна формула.
Если у нас M мышей и K = Math.floor(totalMinutesToTest/poisonTime) раундов кормлений, то можем найти одну ядовитую среди (K+1)^M кормушек. Это обобщение известной задачи с одним раундом, и легко доказывается через бином Ньютона.
Решением этой задачи были математические выкладки, записанные в комментарии к коду? )
Как мы в ВСК провели олимпиаду по программированию для сотрудников