Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

У исполнителя Счетовод две команды, которым присвоены номера:

1. прибавь 1

2. увеличь каждый разряд числа на 1

Первая команда увеличивает число на 1, вторая - увеличивает каждый разряд числа на 1, если он не равен 9.
Например, число 45 с помощью команды 2 превратится в 56, а 49 в 59 (так как младший разряд равен 9 и он остается без изменений).
Программа для Счетовода – это последовательность команд.
Сколько существует программ, которые число S преобразуют в число F?

Входные данные
Программа получает на вход два числа (каждое число записано в отдельной строке): S и F ( 1 <= S <= 100, 10 <= F <= 1000, S < F).

Выходные данные
Выведите ответ на задачу. Гарантируется, что ответ не превышает 2⁶³.

Примеры

№	Входные данные	Выходные данные
1	26 49	22

Рекуррентные последовательности

✓ 24✗ 55800средняяВойти и решать

Счетовод - 4#46792

У исполнителя Счетовод две команды, которым присвоены номера:

1. прибавь A

2. умножь на B

3. возведи в квадрат

Программа для Счетовода – это последовательность команд. Сколько есть программ, которые число S преобразуют в число F?
Гарантируется, что имеется хотя бы одна программа, которая получает из числа S число F.

Входные данные
Программа получает на вход четыре числа: A, B, S, F (1 <= A, B <= 10, 1 <= S <= 100, 1 <= F <= 10³)

Выходные данные
Выведите ответ на задачу. Гарантируется, что ответ не превышает 2⁶³.

Примеры

№	Входные данные	Выходные данные
1	1 2 2 38	266

Рекуррентные последовательности

✓ 47✗ 51500лёгкаяВойти и решать

Счетовод - 3#46791

У исполнителя Счетовод три команды, которым присвоены номера:

1. прибавь A

2. прибавь B

3. умножь на С

Программа для Счетовода – это последовательность команд. Сколько есть программ, которые число S преобразуют в число F?
Гарантируется, что имеется хотя бы одна программа, которая получает из числа S число F.

Входные данные
Программа получает на вход четыре числа: A, B, С, S, F (1 <= A, B, C <= 10, 1 <= S <= 10, 1 <= F <= 100, A и B - различные числа)

Выходные данные
Выведите ответ на задачу. Гарантируется, что ответ не превышает 2⁶³.

Примеры

№	Входные данные	Выходные данные
1	1 2 3 1 12	225

Рекуррентные последовательности

✓ 118✗ 127500лёгкаяВойти и решать

Счетовод - 2#46790

У исполнителя Счетовод три команды, которым присвоены номера:

1. прибавь A

2. умножь на B

3. умножь на С

Программа для Счетовода – это последовательность команд. Сколько есть программ, которые число S преобразуют в число F?
Гарантируется, что имеется хотя бы одна программа, которая получает из числа S число F.

Входные данные
Программа получает на вход пять чисел: A, B, С, S, F (1 <= A, B, C <= 10, 1 <= S <= 100, 1 <= F <= 10³, B и C - различные числа)

Выходные данные
Выведите ответ на задачу. Гарантируется, что ответ не превышает 2⁶³.

Примеры

№	Входные данные	Выходные данные
1	1 2 3 1 18	96

Рекуррентные последовательности

✓ 81✗ 90500лёгкаяВойти и решать

Счетовод - 1#46789

У исполнителя Счетовод две команды, которым присвоены номера:

1. прибавь A

2. умножь на B

Примеры

№	Входные данные	Выходные данные
1	1 2 1 10	14

Рекуррентные последовательности

✓ 61✗ 105500лёгкаяВойти и решать

Номер числа Фибоначчи#42242

Дано натуральное число A > 1. Определите, каким по счету числом Фибоначчи оно является, то есть выведите такое число n, что f_n=A. Если A не является числом Фибоначчи, выведите число -1.

Входные данные
Программа получает на вход натуральное число.

Выходные данные
Выведите ответ на задачу.

Примеры

№	Входные данные	Выходные данные
1	8	6
2	10	-1

Рекуррентные последовательности Цикл while

✓ 4✗ 1900средняяВойти и решать

N-е число Фибоначчи#42241

Последовательность Фибоначчи определяется так: \(f_0 = 0, f_1 = 1, ..., f_n = f_{n-1}+f_{n-2}\).

По данному числу n определите n-е число Фибоначчи f_n.

Входные данные
Программа получает на вход натуральное число n.

Выходные данные
Выведите ответ на задачу.

Примеры

№	Входные данные	Выходные данные
1	6	8

Рекуррентные последовательности

✓ 3✗ 0800средняяВойти и решать

Мячик на лесенке#38639

На вершине лесенки, содержащей N ступенек, находится мячик, который начинает прыгать по ним вниз, к основанию. Мячик может прыгнуть на следующую ступеньку, на ступеньку через одну или через 2. (То есть, если мячик лежит на 8-ой ступеньке, то он может переместиться на 5-ую, 6-ую или 7-ую.) Определить число всевозможных "маршрутов" мячика с вершины на землю.

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

Вводится одно число 0 < N < 31.

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

Выведите одно число — количество маршрутов.

Примеры

№	Входные данные	Выходные данные
1	4	7

Динамическое программирование: один параметр Рекуррентные последовательности

✓ 211✗ 205400лёгкаяВойти и решать

Перестановка#38131

У Беси есть N (3≤N≤40)любимых точек на 2D-решётке, никакие три из которых не коллинеарны. Для каждого 1≤i≤N, i-ая точка задаётся двумя целочисленными координатами x_i и y_i (0≤x_i,y_i≤10⁴).
Беси рисует некоторые отрезки между точками следующим образом:

Она выбирает некоторую перестановку p₁,p₂,…,p_N из N точек
Она рисует отрезки между p₁ и p₂, p₂ и p₃, p₃ и p₁.
Затем для каждого целого i от 4 до N по порядку, она рисует отрезки прямых от p_i до p_j для всех j<i так, этот отрезок не пересекает никакой из ранее нарисованных отрезков (вне конечных точек)
Беси заметила, что для каждого i она нарисовала ровно три новых отрезка. Вычислите количество перестановок, которые Беси могла выбрать на шаге 1, которые удовлетворяют этому свойству по модулю 10⁹+7.

Входные данные:
Первая строка содержит N.
Каждая из последующих N строк содержит два разделённых пробелом целых числа x_i и y_i.

Выходные данные:
Количество перестановок по модулю 10⁹+7.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	4 0 0 0 4 1 1 1 2	0	Никакая перестановка не сработает.
2	4 0 0 0 4 4 0 1 1	24	Все перестановки работают.
3	5 0 0 0 4 4 0 1 1 1 2	96	Одна из перестановок, удовлетворяющих свойству - (0,0),(0,4),(4,0),(1,2),(1,1). Для этой перстановки Сначала она рисует отрезки между каждой парой (0,0),(0,4), и (4,0). Затем она рисует отрезки от (0,0), (0,4), и (4,0) до (1,2). Наконец, она рисует отрезки от (1,2), (4,0), и (0,0) до (1,1). Рисунок: Перестановка не удовлетворяет свойству, если её первые четыре точки (0,0)(0,0), (1,1)(1,1), (1,2)(1,2), и (0,4)(0,4) в некотором порядке.

Рекуррентные последовательности

✓ 2✗ 1—Войти и решать

Небоскреб#31785

В небоскребе n этажей. Известно, что если уронить стеклянный шарик с этажа номер p, и шарик разобьется, то если уронить шарик с этажа номер p+1, то он тоже разобьется. Также известно, что при броске с последнего этажа шарик всегда разбивается.

Вы хотите определить минимальный номер этажа, при падении с которого шарик разбивается. Для проведения экспериментов у вас есть два шарика. Вы можете разбить их все, но в результате вы должны абсолютно точно определить этот номер.

Определите, какого числа бросков достаточно, чтобы заведомо решить эту задачу.

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

Программа получает на вход количество этажей в небоскребе n.

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

Требуется вывести наименьшее число бросков, при котором можно всегда решить задачу.

Примечание

Комментарий к первому примеру. Нужно бросить шарик со 2-го этажа. Если он разобьется, то бросим второй шарик с 1-го этажа, а если не разобьется - то бросим шарик с 3-го этажа.

Подсказки

1. Как следует действовать, если шарик был бы только один?

2. Пусть шариков два и мы бросили один шарик с этажа номер k. Как мы будем действовать в зависимости от того, разобьется ли шарик или нет?

3. Пусть f(n) - это минимальное число бросков, за которое можно определить искомый этаж, если бы в небоскребе было n этажей. Выразите f(n) через значения f(a) для меньших значений a.

Примеры

№	Входные данные	Выходные данные
1	4	2
2	7	3

Динамическое программирование: один параметр Рекуррентные последовательности

✓ 61✗ 110700средняяВойти и решать

Опасные отходы#27085

При переработке радиоактивных материалов образуются отходы двух типов: А (неопасные) и B (особо опасные). Отходы каждого типа упаковываются в контейнеры, а затем контейнеры складываются в стопки. Стопка считается взрывоопасной, если в ней есть три или больше контейнеров с особо опасными отходами (типа B) расположены рядом. Для заданного количества контейнеров N определите, сколько есть способов составить безопасную стопку.

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

Входная строка содержит натуральное число – количество контейнеров N в стопке (1 <= N <= 35).

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

Программа должна вывести одно число – количество способов составить безопасную стопку из N контейнеров.

Примеры

№	Входные данные	Выходные данные
1	3	7

Динамическое программирование: один параметр Рекуррентные последовательности

✓ 88✗ 156700средняяВойти и решать

Числа Фибоначчи#25962

Числа Фибоначчи определяются рекуррентной формулой:

\(F_0 = F_1 = 1, \\ F_n = F_{n-1} + F_{n-2}, \text{ при}\ n \ge 2\)

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

В единственной строке входных данных записано натуральное число n (\(1<=n<=45\)).

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

Вывести одно n-е число Фибоначчи - F_n.

Примеры

№	Входные данные	Выходные данные
1	1	1
2	7	21

Динамическое программирование Рекуррентные последовательности

✓ 104✗ 217400лёгкаяВойти и решать

MTN DEW#21780

Чтобы подготовиться к предстоящей битве Bonkisilver должен прокачать свой скил, а, как известно, лучшим способом это сделать, является употребление mtn dew при прослушивании дабстепа в 4:20 по МСК. Полученный скилл вычисляется по формуле:

f(n) = f(n - 1) + f(n - 2) + f(n / 2),
где n - количество литров mtn dew, выражаемое целым числом. Операция n/2 означает целочисленное деление числа n на 2.

Также, известно, что

f(1) = 1 microCoinZ
f(x) = 0 microCoinZ, при x < 1.

Помогите Bonkisilver сосчитать полученное количество microCoinZ.

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

На вход подается число n (0 <= n <= 70).

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

Выведите одно число - полученный скилл.

Примеры

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

PS: Mountain Dew, также MTN DEW — безалкогольный сильногазированный прохладительный напиток, торговая марка американской компании PepsiCo.

Динамическое программирование Динамическое программирование: один параметр Рекуррентные последовательности

✓ 296✗ 741500лёгкаяВойти и решать