Информатика

Робот Сильвер движется по платному шоссе на планете Шелезяка. На каждом километре шоссе расположен пункт оплаты. Всего на шоссе n пунктов оплаты. Первый пункт оплаты находится в самом начале шоссе, n-й пункт оплаты находится в начале последнего километра шоссе. Заплатив нужную сумму в i-м пункте оплаты, робот может двигаться дальше либо до следующего пункта оплаты, либо же до того, который находится через 2 километра (то есть, если робот находится в пункте i, то он может двигаться либо до пункта i+1, либо до пункта i+2). Первую оплату можно сделать либо в первом пункте, либо во втором (на выбор). Если оплаты была произведена в предпоследнем (n-1) пункте, то можно просто доехать до конца  шоссе, не оплачивая проезд в последнем пункте.
Зная стоимость проезда через определенный пункт оплаты, помогите роботу Сильверу найти наименьшую стоимость проезда через все шоссе, которую должен будет заплатить Сильвер, а также пункты оплаты, на которых ему необходимо будет остановиться. 

Входные данные
В первой строке записано количество пунктов оплаты n (2 <= n <= 1000). Во второй строке записыны n целых чисел (costi) - стоимость проезда через i-й пункт оплаты (1 <= i <= n, 0 <= costi <= 999).

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

Примеры

№	Входные данные	Выходные данные
1	3 10 15 20	15 2
2	10 1 100 1 1 1 100 1 1 100 1	6 1 3 5 7 8 10

Робот Сильвер едет по шоссе. Вдоль дороги стоят n пунктов оплаты — по одному на каждый километр. На пункте i написана плата cost[i]: столько робот отдаёт, если останавливается у этого пункта. Пункт, мимо которого он проехал не останавливаясь, не оплачивается.
Перед шоссе есть бесплатный въезд, а после — бесплатный съезд. Робот стартует со въезда, едет только вперёд, и от каждой остановки до следующей проезжает 1 или 2 пункта. Доехать ему надо до съезда.
Найдите наименьшую сумму, которую заплатит робот.

Формат входных дынных
В первой строке записано количество пунктов оплаты n (2 <= n <= 1000). Во второй строке записыны n целых чисел (costi) - стоимость проезда через i-й пункт оплаты (1 <= i <= n, 0 <= costi <= 999).

Формат выходных дынных
Выведите одно число - ответ на задачу.

Последовательность чисел Трибоначчи (Tn) определяется следующим образом: 

T0 = 0,
T1 = 1,
T2 = 1, и Tn+3 = Tn + Tn+1 + Tn+2 при n >= 0.

Для заданного числа n, определите значение T_n.

Входные данные
Программа получает на вход натуральное число n (0 <= n <= 37). Ответ гарантированно укладывается в рамки 32-разрядного целого числа, т.е. ответ <= 2³¹ - 1.

Выходные данные
Выведите значение T_n.
 
Попробуйте решить эту задачу без использования массивов и других структур данных! Другими словами, ваша программа должна использовать фиксированный объем памяти, не зависящий от входных данных (О(1)).

 

Примеры

№	Входные данные	Выходные данные
1	4	4
2	25	1389537

Робот Сильвер занимается терроформированием на планете Шелезяка. Сейчас робот находится перед лестницу, ведущей на вершину горы. Лестница состоит из n ступенек. Робот, поднимаясь вверх, может пойти на одну или сразу две ступеньки.
Пока робот поднимается на вершину, вы хотите определить, сколько существует различных способов, которыми он может добраться до последней ступеньки этой лестницы и тем самым оказаться на вершине горы.

Входные данные
Программа получает на вход одно целое число  n - количество ступенек в лестнице (1 <= n <= 45).

Выходные данные
Выведите одно число - количество способов добраться до вершины горы.
 
 

Примеры

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

Числа Фибоначчи, обозначаемые обычно F(n) образуют последовательность, называемую последовательностью Фибоначчи, такую, что каждое число является суммой двух предыдущих, начиная с 0 и 1. То есть,

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), для n > 1.

По заданному n, вычислите F(n) (0 <= n <= 80).

Попробуйте решить эту задачу без использования массивов и других структур данных! Другими словами, ваша программа должна использовать фиксированный объем памяти, не зависящий от входных данных (О(1)).
 

Примеры

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

Робот Сильвер занимается терроформированием на планете Шелезяка. Сейчас робот находится перед лестницей, ведущей на вершину горы. Лестница состоит из n ступенек. Робот, поднимаясь вверх, может пойти на одну или сразу две ступеньки.
Пока робот поднимается на вершину, вы хотите определить, сколько существует различных способов, которыми он может добраться до последней ступеньки этой лестницы и тем самым оказаться на вершине горы.

Входные данные
Программа получает на вход одно целое число  n - количество ступенек в лестнице (1 <= n <= 45).

Выходные данные
Выведите одно число - количество способов добраться до вершины горы.
 
Попробуйте решить эту задачу без использования массивов и других структур данных! Другими словами, ваша программа должна использовать фиксированный объем памяти, не зависящий от входных данных (О(1)).
 

Примеры

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

Последовательность чисел Трибоначчи (Tn) определяется следующим образом: 

T0 = 0,
T1 = 1,
T2 = 1, и Tn+3 = Tn + Tn+1 + Tn+2 при n >= 0.

Для заданного числа n, определите значение T_n.

Входные данные
Программа получает на вход натуральное число n (0 <= n <= 37). Ответ гарантированно укладывается в рамки 32-разрядного целого числа, т.е. ответ <= 2³¹ - 1.

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

Примеры

№	Входные данные	Выходные данные
1	4	4
2	25	1389537

Числа Фибоначчи, обозначаемые обычно F(n) образуют последовательность, называемую последовательностью Фибоначчи, такую, что каждое число является суммой двух предыдущих, начиная с 0 и 1. То есть,

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), для n > 1.

По заданному n, вычислите F(n) (0 <= n <= 80).

(в коде программы длина одного отступа равна 4 пробелам!)

Примеры

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

 

Пример

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

Напишите программу, которая в строке заменяет все точки на нули и все заглавные английские буквы "X" на единицы. 
 

Примеры

№	Входные данные	Выходные данные
1	..X..XX	0010011

Даны две строки. Определите строку с наибольшей длиной и выведите на экран длину этой строки. Если обе строки имеют одинаковую длину, то выведите -1.


Входные данные
В первой строке вводится первая строка.
Во второй строке вводится вторая строка.

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

 

Примеры

№	Входные данные	Выходные данные
1	Hello, world! Good day!	12
2	Hi! And	-1

Входные данные
В первой строке задается имя пользователя.

Выходные данные
Выведите на экран:
1) в первой строке - приветствие пользователю в виде "Hello, имя!" (без кавычек)
2) во второй строке - выведите имя пользователя 10 раз через пробел.

Примеры

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

Дано натуральное число N (\(N<=10^9\)). Определить две самые большие цифры числа. 

Входные данные 
На вход подается одно число (число содержит как минимум 2 различные цифры).

Выходные данные 
Выведите две цифры через пробел, сначала наибольшую цифру числа, затем вторую по величине (не равную первой наибольшей цифре).
 

 

Примеры

№	Входные данные	Выходные данные
1	45545	5 4
2	1113	3 1

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

Входные данные 
На вход поступают числа последовательности, по одному числу в строке. Ноль - признак окончания ввода.

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

 

Примеры

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

Дано натуральное число N (\(N<=10^9\)). Определить его максимальную четную и минимальную четную цифры.

Входные данные 
На вход подается одно число.

Выходные данные 
Выведите через пробел два числа: сначала минимальную четную цифру, затем максимальную. Если четных цифр в числе нет, выведите NO.

Гарантируется, что если в  числе есть четные цифры, то их не менее двух.

 

Примеры

№	Входные данные	Выходные данные
1	45545	4 4
2	111	NO

Дано натуральное число N. Определить количество его цифр, кратных z. 

Входные данные 
Вводятся два числа через пробел, сначала натуральное число N, затем - z (\(0< z <=9\)).

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

 

Примеры

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

Дана последовательность целых ненулевых чисел, оканчивающаяся нулем (ноль в последовательность не входит). Необходимо найти расстояние (по модулю) между первым минимальным и первым максимальным числом последовательности. 

Входные данные 
На вход подаются целые числа (по одному числу в строке).

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

 

Примеры

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

На вход программы поступает неизвестное количество целых чисел, ввод заканчивается нулём (ноль не входит в последовательность). Найти максимальное чётное число среди всех введённых чисел. Гарантируется, что в последовательности есть хотя бы одно четное число

Входные данные
На вход программе подаются числа, по одному числу в строке.

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

 

Примеры

№	Входные данные	Выходные данные
1	1 2 6 0	6

 

На вход программы поступает неизвестное количество целых чисел, ввод заканчивается нулём (ноль не входит в последовательность). Определить, сколько получено чисел, которые делятся на 3.

Входные данные
На вход программе подаются числа, по одному числу в строке.

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

 

Примеры

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