Блог пользователя abd.yerzhan

Автор abd.yerzhan, 12 лет назад, По-русски

Здравствуйте codeforces-чане ) Нуждаюсь в помощи решением одной задачи . Ссылка вот

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Можно подробней)

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    А можно узнать про вашу обычную динамику ? Как оно делается ?

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      d[x][k] — сколькими способами можно представить x, используя монеты типа не более k. Переход — либо увеличиваем количество типов, либо берём монетку самого большого типа, который можем.

      Почему так — попробуем написать перебор и прикрутить к нему запоминание (получим динамику). Пусть как-то набрали. Для определённости (порядок монет неважен) отсортируем их по возрастанию номинала. Заметим, что на очередном шаге перебора нам важно знать лишь остаток суммы и монеты какого минимального номинала мы можем брать.

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        я понял но оценка памяти и времени какая? памяти надо 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 на самом деле на много меньше заявленного

        я правильно понял?

        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Да

          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится +3 Проголосовать: не нравится

            некрасиво такие условия давать) или это так сложность процесса решения повышают)

            как оценить максимум A?

            • »
              »
              »
              »
              »
              »
              »
              12 лет назад, # ^ |
                Проголосовать: нравится +3 Проголосовать: не нравится

              Просто пишем, запускаем и смотрим, при каком A число способов станет больше, чем надо.

              • »
                »
                »
                »
                »
                »
                »
                »
                12 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

                тоже метод) я думал аналитически верхнюю границу для A кто-то оценит хорошо)