|
|
|
|
|
|
|
| 1 Жасымбек Мади Ганиулы, 25 октября 2024 г. 19:57:14 |
| коробка может остаться ничей?
|
|
|
| 2 Матус Даниил Дмитриевич, 13 сентября 2020 г. 20:42:11 |
| а так изи дп
|
|
|
| 3 Матус Даниил Дмитриевич, 13 сентября 2020 г. 20:41:58 |
| у кого 11 тест в конце делайте проверку на отрицательный ответ мне помогло
|
|
|
| 4 Севидов Артём Алексеевич, 19 июня 2020 г. 1:10:30 |
| Простой рюкзачок :)
|
|
|
| 5 Дмитриев Дмитрий Андреевич, 26 февраля 2020 г. 8:04:02 |
| Наверно это будет слишком сильная подсказка, но: гораздо проще посчитать "плохие" разбиения, а не хорошие.
|
|
|
| 6 Слуцкий Алексей, 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
|
|
|
| 7 Иван Михнович, 04 мая 2015 г. 12:32:59 |
Жуткая задача! Я об неё чуть мозги не сломал. Не знаю почему. Разгадка же вроде лежит на поверхности.
От нас требуется найти количество способов из данного набора чисел выбрать несколько так чтобы набрать в сумме k, но при этом еще из оставшихся должно получиться суммарно не меньше k. Первая идея - давайте забудем на время про второе ограничение и решим первую часть задачи. Итак, сколько существует способов выбрать некоторые числа из данного набора чтобы получить в сумме k? Эта задачка легко решается динамикой по суммам, вариация на тему №378. Кстати, сложность у той задачи 62%, что аж на 12% больше чем у этой, а мы только начали. Более того, в номере 378 ограничения да числа от нуля до сотни, а тут аж до 10^9! Правда, ограничение это несколько фиктивное, но я не буду рассказывать как с ним справиться :o)
Итак, первая часть задачи решена, но что же делать со вторым условием-ограничением? Тут я завис надолго, хотя дел на копейку. Просто еще раз ВНИМАТЕЛЬНО вчитайтесь в то ЧТО нам нужно найти.
Удачи! :o
|
|
|
Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!
| | | |
