Задача
Подсчитайте количество способов, которыми можно получить сумму $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 |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
import java.util.*; import java.lang.*; import java.io.*; import java.util.Scanner; public class Ideone { public static void main (String[] args) throws java.lang.Exception { int n; int ans = 0; Scanner myObj = new Scanner(System.in); n = myObj.nextInt(); //считываем сумму, для которой будем считать количество перестановок int a[] = new int[n+1]; //создаем массив Arrays.fill(a, 0); if (n == 1) ans = 1; if (n == 2) ans = 2; if (n == 3) ans = 4; if (n == 4) ans = 8; if (n == 5) ans = 16; if (n == 6) ans = 32; // частные случаи if (n > 6) { a[1] = 1; a[2] = 2; a[3] = 4; a[4] = 8; a[5] = 16; a[6] = 32; for (int i = 7; i < n + 1; i++) { a[i]=0; for (int j = 1; j < 7; j++) // вычисление количества для i-ой суммы a[i] = ( a[i] + a[i-j] ) % 1000000007; } ans = a[n]; } System.out.println(ans); } } |
Решение
Создадим массив на $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