Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 
[Вернуться к задаче]   1
  1  Севидов Артём Алексеевич, 19 июня 2020 г. 1:10:30
     Простой рюкзачок :)
  2  Дмитриев Дмитрий Андреевич, 26 февраля 2020 г. 8:04:02
     Наверно это будет слишком сильная подсказка, но: гораздо проще посчитать "плохие" разбиения, а не хорошие.
  3  Слуцкий Алексей, 03 февраля 2017 г. 7:07:32
     Не надо тут находить набор, который суммарно равен k. Это обычный рюкзак.
4 4
2 2 2 2
Ответ: 6
_
4 4
2 3 2 1
Ответ: 2
_
6 18
4 8 5 7 8 6
Ответ: 10
  4  Иван Михнович, 04 мая 2015 г. 12:32:59
     Жуткая задача! Я об неё чуть мозги не сломал. Не знаю почему. Разгадка же вроде лежит на поверхности.

От нас требуется найти количество способов из данного набора чисел выбрать несколько так чтобы набрать в сумме k, но при этом еще из оставшихся должно получиться суммарно не меньше k. Первая идея - давайте забудем на время про второе ограничение и решим первую часть задачи. Итак, сколько существует способов выбрать некоторые числа из данного набора чтобы получить в сумме k? Эта задачка легко решается динамикой по суммам, вариация на тему №378. Кстати, сложность у той задачи 62%, что аж на 12% больше чем у этой, а мы только начали. Более того, в номере 378 ограничения да числа от нуля до сотни, а тут аж до 10^9! Правда, ограничение это несколько фиктивное, но я не буду рассказывать как с ним справиться :o)
Итак, первая часть задачи решена, но что же делать со вторым условием-ограничением? Тут я завис надолго, хотя дел на копейку. Просто еще раз ВНИМАТЕЛЬНО вчитайтесь в то ЧТО нам нужно найти.

Удачи! :o
 1

Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!

Красноярский краевой Дворец пионеров, (c)2006 - 2020, E-mail: admin@acmp.ru