Последовательность чисел Фибоначчи определяется следующим образом: \(F_1 = F_2 = 1\), \(F_n = F_{n-1} + F_{n-2}\) при \(n \gt 2\)
В единственной строке входных данных записано натуральное число \(n (1 \le n \le 2 * 10^6).\)
Вывести одно число \(F_n\) по модулю \(2^{64}\)
| Ввод | Вывод |
|---|---|
2 |
1 |
5 |
5 |
Последовательность чисел Фибоначчи определяется следующим образом: \(F_1 = F_2 = 1\), \(F_n = F_{n-1} + F_{n-2}\) при \(n \gt 2\)
В единственной строке входных данных записано натуральное число \(n (1 \le n \le 10^9).\)
Вывести одно число \(F_n\) по модулю \(2^{64}\)
| Ввод | Вывод |
|---|---|
2 |
1 |
5 |
5 |
Последовательность чисел Фибоначчи определяется следующим образом: \(F_0 = F_1 = 1\), \(F_{n+1} = F_n+F_{n-1}\). Напишите программу для вычисления последней цифры \(n\)-го члена последовательности.
В единственной строке входных данных записано натуральное число \(n (1 \le n \le 1000)\)
Выведите последнюю цифру числа \(F_n\)
| Ввод | Вывод |
|---|---|
4 |
5 |
На вершине лесенки, содержащей \(N\) ступенек, находится мячик, который начинает прыгать по ним вниз, к основанию. Мячик может прыгнуть на следующую ступеньку, на ступеньку через одну или через 2. (То есть, если мячик лежит на 8-ой ступеньке, то он может переместиться на 5-ую, 6-ую или 7-ую.) Определить число всевозможных "маршрутов" мячика с вершины на землю по модулю \(10^9+7\).
Вводится одно число \(0 \lt N \le 10^5\)
Выведите одно число - количество маршрутов по заданному модулю.
| Ввод | Вывод |
|---|---|
4 |
7 |
Имеется калькулятор, который выполняет три операции:
Определите, какое наименьшее число операций необходимо для того, чтобы получить из числа 1 заданное число \(N\).
Программа получает на вход одно число, не превосходящее \(10^6\).
Требуется вывести одно число: наименьшее количество искомых операций.
| Ввод | Вывод |
|---|---|
1 |
0 |
5 |
3 |
32718 |
17 |
Имеется калькулятор, который выполняет три операции:
Определите кратчайшую последовательность операций, необходимую для получения из числа \(1\) заданное число \(N\).
Программа получает на вход одно число \(N\), не превосходящее \(10^6\).
Выведите строку, состоящую из цифр "1", "2" или "3", обозначающих одну из трех указанных операций, которая получает из числа \(1\) число \(N\) за минимальное число операций. Если возможных минимальных решений несколько, выведите любое из них.
| Ввод | Вывод |
|---|---|
1 |
|
5 |
121 |
562340 |
3333312222122213312 |
В дощечке в один ряд вбиты гвоздики. Любые два гвоздика можно соединить ниточкой. Требуется соединить некоторые пары гвоздиков ниточками так, чтобы к каждому гвоздику была привязана хотя бы одна ниточка, а суммарная длина всех ниточек была минимальна.
В первой строке входных данных записано число \(N\) - количество гвоздиков \((2 \le N \le 100)\). В следующей строке заданы \(N\) чисел - координаты всех гвоздиков (неотрицательные целые числа, не превосходящие 10000).
Выведите единственное число - минимальную суммарную длину всех ниточек.
| Ввод | Вывод |
|---|---|
5 4 10 0 12 2 |
6 |
Васин дедушка построил забор на даче из того, что попалось под руку. Забор представляет собой ряд из \(N\) досок ширины 10 см, но, возможно, различной высоты.
Теперь Вася хочет покрасить забор таким способом. Он выбирает 5 произвольных подряд идущих досок и красит их в один цвет. Затем он выбирает 5 любых еще не покрашенных идущих подряд досок и красит их в другой цвет. И так продолжает до тех пор, пока может выбрать 5 подряд идущих не покрашенных досок.
Требуется определить, какую наибольшую площадь забора он сможет покрасить таким способом.
В первой строке входного файла вводится одно число \(N\) - количество досок.
Во второй строке входного файла вводятся \(N\) чисел - высоты 1-й, 2-й, ..., \(N\)-й досок забора в сантиметрах.
Все числа натуральные и не превосходят 100.
Выведите одно число: наибольшую покрашенную площадь в квадратных сантиметрах.
| Ввод | Вывод |
|---|---|
6 1 2 3 4 5 6 |
200 |
12 2 4 3 7 8 100 92 1 4 2 34 1 |
2550 |