Псевдослучайная последовательность

ограничение времени на тест: 1 сек.
ограничение памяти на тест: 2048 KB.

ввод: input.txt
вывод: output.txt

 

Первое число псевдослучайной последовательности равно P. Каждое следующее получается путем возведения предыдущего значения в квадрат. Пусть получается значение Q. Если Q содержит менее, чем 4 цифры, то число дополняется до 4 цифр лидирующими нулями слева. После этого у Q отбрасываются первая и последняя цифры. Результат и есть очередное число в псевдослучайной последовательности.
Например, если P = 11, то начало последовательности имеет вид: 11, 12, 14, 19, 36, 29, 84, 5, 2, 0, 0,... Если P = 70, то последовательность имеет вид: 70, 90, 10, 10, 10,...
Несложно доказать, что последовательность рано или поздно зацикливается. Ваша задача найти количество элементов последовательности, которые не входят в цикл.

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

В первой строке входного файла содержится натуральное число P (0 <= P <= 99).

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

В выходной файл выведите искомую длину последовательности до начала цикла.

Пример

Ввод

Пример 1
70
Пример 2
10
Пример 3
11

Вывод

Пример 1
2
Пример 2
0
Пример 3
9

Танцоры

ограничение времени на тест: 1 сек.
ограничение памяти на тест: 2048 KB.

ввод: input.txt
вывод: output.txt

 

N танцоров собираются танцевать хоровод. Известен рост каждого из них. Они хотят встать в круг таким образом, чтобы минимизировать максимальную разницу ростов стоящих рядом людей. Например, если N = 4 и росты равны H = {180,183,178,185}, то надо организовать круг, изображенный на рисунке.

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

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

В первой строке входного файла содержится натуральное число N (3 <= N <= 20). Во второй содержится последовательность H1, H2,..., HN (150 <= Hi <= 210), где Hi - рост i-го танцора.

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

В выходной файл выведите искомое наименьшее значение.

Пример

Ввод

Пример 1
4
180 183 178 185
Пример 2
12
184 165 175 186 192 200 176 192 194 168 205 201

Вывод

Пример 1
5
Пример 2
10

Спички

ограничение времени на тест: 1 сек.
ограничение памяти на тест: 2048 KB.

ввод: input.txt
вывод: output.txt

 

Иногда для изучения простейшего счета маленькие дети складывают числа из спичек. Каждая цифра требует определенного количества спичек:
цифра 8 изображается 7 спичками;
цифры 0, 6, 9 используют 6 спичек;
2, 3, 5 - 5 спичек;
4, 7 - 4 спички;
цифра 1 использует 2 спички.
Задано N - количество спичек в коробке. Какое наименьшее положительное целое число нельзя сложить из этого количества спичек?

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

В первой строке входного файла записано целое число N (1 <= N <= 128).

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

В выходной файл выведите искомое число.

Пример

Ввод

Пример 1
2
Пример 2
9
Пример 3
11

Вывод

Пример 1
2
Пример 2
20
Пример 3
28

Домашнее задание

ограничение времени на тест: 1 сек.
ограничение памяти на тест: 2048 KB.

ввод: input.txt
вывод: output.txt

 

Петя очень не любит делать домашние задания. Поэтому он просит отличников из своего класса делать их за него. За это он дает им шоколадные конфеты - Петин папа работает на шоколадной фабрике, и у Пети всегда много конфет. Но отличники - капризные ребята. В разные дни они просят разное количество конфет за решение домашнего задания. Про каждого отличника в классе Петя знает, сколько конфет придется ему дать в j-й день учебы, чтобы тот сделал за него домашнее задание. Кроме того, каждый день делать задания за Петю не согласится ни один отличник. Про каждого отличника Петя знает, какое максимальное число заданий тот согласится сделать за него подряд.
Требуется по информации о количестве конфет, которое отличники просят за свои услуги, а также о максимальном количестве дней подряд, которое каждый отличник готов делать задания за Петю, определить, какое минимальное количество конфет требуется Пете, чтобы все домашние задания были за него сделаны.

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

Первая строка входного файла содержит два числа: N - количество учебных дней, в течение которых Петя хочет, чтобы за него делали домашние задания, и M - количество отличников в классе у Пети (1 <= N <= 100, 2 <= M <= 100). Вторая строка входного файла содержит M целых чисел - для каждого отличника задано число Ai - максимальное количество заданий подряд, которое он согласен выполнить за Петю. Следующие M строк содержат по N неотрицательных целых чисел - j-е число i-ой строке означает количество конфет, которое Пете придется отдать i-му отличнику, чтобы он сделал за Петю домашнее задание в j-й день. Все эти числа не превышают 10^6.

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

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

Пример

Ввод

5 2
2 2
1 3 6 4 1
5 2 3 1 1

Вывод

9
1 1 2 2 1