Здравствуйте codeforces-чане ) Нуждаюсь в помощи решением одной задачи . Ссылка вот
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
6 | adamant | 157 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 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 кто-то оценит хорошо)