Здравствуйте codeforces-чане ) Нуждаюсь в помощи решением одной задачи . Ссылка вот
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3993 |
2 | jiangly | 3743 |
3 | orzdevinwang | 3707 |
4 | Radewoosh | 3627 |
5 | jqdai0815 | 3620 |
6 | Benq | 3564 |
7 | Kevin114514 | 3443 |
8 | ksun48 | 3434 |
9 | Rewinding | 3397 |
10 | Um_nik | 3396 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 156 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
9 | nor | 153 |
Здравствуйте codeforces-чане ) Нуждаюсь в помощи решением одной задачи . Ссылка вот
Название |
---|
It is guaranteed that the number of ways will be less than 2,000,000,000 (and thus will fit into a 32-bit integer).
Можно обычную динамику за O(6 * n). Если n был бы хотя бы 10^5 то количество превысит 2*10^9.
Можно подробней)
А можно узнать про вашу обычную динамику ? Как оно делается ?
d[x][k] — сколькими способами можно представить x, используя монеты типа не более k. Переход — либо увеличиваем количество типов, либо берём монетку самого большого типа, который можем.
Почему так — попробуем написать перебор и прикрутить к нему запоминание (получим динамику). Пусть как-то набрали. Для определённости (порядок монет неважен) отсортируем их по возрастанию номинала. Заметим, что на очередном шаге перебора нам важно знать лишь остаток суммы и монеты какого минимального номинала мы можем брать.
я понял но оценка памяти и времени какая? памяти надо int[2*A], A=10^9 ? времени соотв-но O(A)
я так понял nurs предлагает проанализировав "It is guaranteed that the number of ways will be less than 2,000,000,000" прийти к тому что A на самом деле на много меньше заявленного
я правильно понял?
Да
некрасиво такие условия давать) или это так сложность процесса решения повышают)
как оценить максимум A?
Просто пишем, запускаем и смотрим, при каком A число способов станет больше, чем надо.
тоже метод) я думал аналитически верхнюю границу для A кто-то оценит хорошо)