Задача
Вычислить количество последовательностей длины $n,$ состоящих только из нулей и единиц, в которых не встречается три единицы подряд.
Входные данные
Длина последовательностей $n$ $\left ( 1 \leq n \leq 10^{5} \right ).$
Выходные данные
Вывести количество искомых последовательностей по модулю $12345.$
Тесты
| Входные данные | Выходные данные |
| $1$ | $2$ |
| $4$ | $0$ |
| $263$ | $10159$ |
| $10000$ | $8872$ |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
import java.util.*; import java.lang.*; import java.io.*; class Main { static int MAX = 100010; static int f[] = new int[MAX]; public static void main (String[] args) throws java.lang.Exception { Scanner in = new Scanner(System.in); int n = in.nextInt(); f[1] = 2; f[2] = 4; f[3] = 7; for(int i = 4; i <= n; i++) { f[i] = (f[i-1] + f[i-2] + f[i-3]) % 12345; } System.out.println(f[n]); } } |
Решение
Объявим массив $f,$ в котором будем сохранять значения $f(1), f(2),\dots, f(n).$ Далее читаем входные данные и заносим в соответствующие ячейки массива $f$ значения $f(1), f(2)$ и $f(3).$ Вычисляем значения $f(i)$ по рекуррентной формуле $f(n) = f(n – 1) + f(n – 2) + f(n – 3).$
Эту формулу получили так: сперва обозначили через $f(n)$ количество искомых последовательностей из $0$ и $1$ длины $n.$ Далее мы смотрим, если на первом месте последовательности будет находиться $0,$ то начиная со второго места можно построить $f(n – 1)$ последовательность. Если на первом месте стоит $1,$ то на втором месте возможны оба варианта. Если там стоит $0,$ то на следующих $n – 2 $свободных местах можно построить $f(n – 2)$ последовательности. Если $1,$ то на третьем месте обязательно должен находиться $0$ и начиная с четвертого места можно построить $f(n – 3)$ последовательности.
Вычисления значения $f(i)$ производим по модулю $12345.$ В результате выводим количество искомых последовательностей по модулю.
Ссылки
Условие задачи на e-olymp
Код решения задачи ideone