4
|
Задача 209. Разноцветные полоски-2постоянный адрес задачи: http://www.diofant.ru/problem/590/показать код для вставки на свой сайт >> |
Задачу решили:
10
всего попыток:
12
поделиться задачей:
|
|
|
Задача опубликована:
19.10.09 15:11
Прислал:
mikev
Источник:
Проект "Эйлер" (http://projecteuler.net)
Вес:
1
сложность:
1
класс:
8-10
баллы: 100
Темы:
арифметика
,
алгоритмы
|
|
|
Замечание: Это более сложный вариант задачи 114.
Как и в задаче 114, будем рассматривать прямоугольные полоски, состоящие из n выстроенных в ряд клеток. Идущие подряд клетки одного цвета образуют блоки. При этом красные блоки содержат не менее mr клеток, а черные – не менее mb.
Обозначим через F(mr, mb,n) число способов, которым такая полоска может быть построена, например F(3, 2, 8)=14 (см. рисунок).
|
|
|
||||||||||||||||||||||||
|
|
|
||||||||||||||||||||||||
|
|
|
||||||||||||||||||||||||
|
|
|
||||||||||||||||||||||||
|
|
Кроме того, F(3, 2, 34)= 856506 и F(3, 2, 35)= 1309554.
Это означает, что n=35 – минимальное значение, при котором функция F(3, 2,n) превосходит миллион.
Аналогично, F(5, 3, 46) = 849735 и F(5, 3, 47)= 1172897, и 47 – первое значение n, при котором F(5, 3, n) больше миллиона.
Найдите минимальное значение n, при котором F(111, 100, n) > 1 000 000.
Если Вы не можете ее решить, значит Вы не можете ее решить :-)
Обсуждение
Правила >>