e-olymp 9036. Комбинация игральных костей

Задача

Подсчитайте количество способов, которыми можно получить сумму $n$ бросая игральный кубик один или несколько раз. Каждый бросок дает результат между 1 и 6.

Например, если $n = 3$, то имеется 4 способа:
1 + 1 + 1
1 + 2
2 + 1
3

Входные данные

Одно целое число $n$ $(1 \leqslant n \leqslant 10^6)$.

Выходные данные

Выведите количество способов по модулю $10^9+7$.

Тесты

Входные данные  Выходные данные
1 1 1
2 3 4
3 5 16
4 6 32
5 8 123

Код программы

Первый способ (выполняется быстрее, но использует больше памяти)

Второй способ (использует меньше памяти, но выполняется дольше)

 

Решение

Создадим массив на $n+1$ элемент. В который мы сразу запишем количество перестановок для сумм 1,2..,6. Для остальных случаев, когда $n>7$ воспользуемся следующей идеей. Будем вычислять количество перестановок для сумм, начиная с 7 до тех пор, пока не дойдем до заданного нам $n$. Будем делать это по такой формуле $a_{i}=a_{i-1}+a_{i-2}+a_{i-3}+a_{i-4}+a_{i-5}+a_{i-6}$  . Для первых шести сумм вычисляем по этой же формуле, с учетом, что $0 < i-k \; (1 \leqslant k \leqslant 6)$ и добавляя еще 1 перестановку, так как мы можем получить сумму ( $i$ ), подбросив кубик 1 раз. Рассмотрим для $n=7$. Чтобы получить 7 достаточно подбросить кубик ещё один раз, так как мы знаем количество для $n$ от 1 до 6. Если выпадет 1, то остается $a_{6}$ возможных перестановок, если выпадет 2, то остается  $a_{5}$  и так далее. Затем нам требуется просуммировать, так как кубик может выпасть 6 способами, как было сказано ранее. Соответственно для $n=8$ количество комбинаций увеличится на  $a_{7}$ и уменьшится на  $a_{1}$, так как кубик имеет только 6 граней.

Ссылки

Условие задачи на e-olymp

Код программы на ideone

4 thoughts on “e-olymp 9036. Комбинация игральных костей

    • Спасибо за ваш комментарий. Исправила

    • Ограничение в условии нужно сделать одной формулой и поставить правильные знаки неравенства.
    • Если в массив сразу прописать ответы для первых шести значений, то можно будет выбросить все семь условных операторов и оставить только печать a[n]. Получится как-то так:
      Но вообще-то для решения задачи достаточно 6 переменных или массив на 6 элементов.
    • Остаток от деления лучше брать при каждом сложении. И риска переполнения меньше и на одну строку короче.
    • «данной задачи» зачем этот канцелярский стиль? У вас одна задача и всем понятно, что Вы её и решаете.
    • Вы не описали как нашли первые шесть ответов. Если с этого начать, то будет понятнее.
    • Поработайте, пожалуйста, над ключевыми словами еще. Не очень они удачные, не отражают решения.
  1. Хорошо.
    Кстати, Вы заметили, что во втором коде вы фактически использовали очередь на 6 элементов? Сдвиг Вам понадобился для того, чтобы эти 6 элементов не уползали от начала массива. Но это в точности та же задача, которую мы сегодня решали при реализации очереди на основе массива. Мы можем воспользоваться тем, что в данной очереди всегда добавляется и удаляется ровно один элемент. Т.е. наша очередь ползет по массиву по кругу. Значит достаточно запомнить позицию ( last) где она заканчивается и сдвигать ее циклически вправо. Это позволит сохранить скорость работы первого алгоритма (нет пересылок) и малый объем требуемой памяти (нет огромного массива):

    Кстати, в этом коде я использовал long q, чтобы не вычислять остаток от деления в цикле. Да, я помню, что сам сказал вставить его в цикл. Виноват, был не прав. Здесь и так все помещается.

Добавить комментарий