Problem A. Repeating digit (easy) ≡

Author:T. Chistyakov, A. Klenin   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

Statement

For given integers P and N you need to find all such values of x < 10N, that N last digits of xP are non-zero and equal.

Fortunately, there is not so many numbers showing this property. For example, for P = 2 and N = 2 there exist only 4 of them:

12, 38, 62, 88

Input file format

Input file contains P and N.

Output file format

Output the number of existing numbers X, then all these numbers in any order.

Constraints

2 ≤ P ≤ 100

2 ≤ N ≤ 9

Sample tests

No. Input file (input.txt) Output file (output.txt)
1 
3 2

8 
14 42 53 64 77 71 92 99

Problem B. Repeating digit (medium) ≡

Author:T. Chistyakov, A. Klenin   Time limit:5 sec
Input file:input.txt   Memory limit:1 Mb
Output file:output.txt  

Statement

For given integers P and N you need to find all such values of x < 10N, that N last digits of xP are non-zero and equal.

Fortunately, there is not so many numbers with this property. For example, for P = 2 and N = 2 there exist only 4 of them:

12, 38, 62, 88

Input file format

Input file contains P and N.

Output file format

Output the number of existing numbers X, then all these numbers in any order.

Constraints

2 ≤ P ≤ 100

2 ≤ N ≤ 17

Sample tests

No. Input file (input.txt) Output file (output.txt)
1 
3 2

8 
14 42 53 64 77 71 92 99

Задача C. Треугольник Паскаля ≡

Автор:XII Командный чемпионат школьников Санкт-Петербурга по программированию   Ограничение времени:2 сек
Входной файл:pascal.in   Ограничение памяти:8 Мб
Выходной файл:pascal.out  

Условие

Треугольник Паскаля — это бесконечный треугольник из чисел, который имеет следующий вид:

1
11
121
1331
14641
………………

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

Таким образом, i-ая строка содержит i + 1 число. Если обозначить j-ый элемент i-ой строки как ai, j, то выполняется равенство ai, j = ai−1, j−1 + ai−1, j. Заметим, что это равенство выполняется и для крайних элементов, если положить отсутствующие элементы предыдущей строки (элементы с номерами −1 и i) равными нулю.

Коля хочет узнать, сколько нечетных чисел в n-ой строке треугольника Паскаля. Он начал рисовать треугольник, но очень скоро тот перестал помещаться на листочек. Тогда Коля решил сделать это с помощью компьютера. Помогите ему.

Формат входного файла

Во входном файле содержится число n.

Формат выходного файла

Выходной файл должен содержать одно число — количество нечетных чисел в n-ой строке треугольника Паскаля.

Ограничения

0 ≤ n ≤ 2 ⋅ 109

Примеры тестов

№ Входной файл (pascal.in) Выходной файл (pascal.out)
1 
0
 
1
2 
5
 
4
3 
7
 
8

Задача D. Интересное число ≡

Автор:XII Командный чемпионат школьников Санкт-Петербурга по программированию   Ограничение времени:2 сек
Входной файл:number.in   Ограничение памяти:64 Мб
Выходной файл:number.out  

Условие

Для заданного числа n найдите наименьшее положительное целое число с суммой цифр n, которое делится на n.

Формат входного файла

Во входном файле содержатся целое число n.

Формат выходного файла

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

Ограничения

1 ≤ n ≤ 1000.

Примеры тестов

№ Входной файл (number.in) Выходной файл (number.out)
1 
1
 
1
2 
10
 
190

Задача E. Цветные нули ≡

Автор:XII Командный чемпионат школьников Санкт-Петербурга по программированию   Ограничение времени:2 сек
Входной файл:zeroes.in   Ограничение памяти:8 Мб
Выходной файл:zeroes.out  

Условие

Толик только что узнал, что на свете существует двоичная система счисления. Обрадованный этим, он записал в столбик двоичные формы чисел 1, 2,…, n. Получились числа 1, 10, 11, 100, 101, 110, 111, …

После этого он стер все написанные единицы и стал изучать расположение нулей. Он выбрал число k и в каждой строке, идя слева направо, выделил красным цветом каждый k-ый ноль, начиная с первого. Таким образом, оказались выделенными нули с номерами 1, k + 1, 2 k + 1, … Например если k = 2, n = 56, то получились бы такие строки:

1 1 0 0 0 1 1 1 1 1 0 1 1 0 1 1 1 0 1 1 0 0 1 0 0 1 0 1 0 1 1 1 1 0 0 1 0
1 0 1 0 0 1 1 0 0 0 0 1 0 1 1 1 1 1 1 1 0 1 0 0 1 0 1 1 0 1 1 0 0 1 1 0 0 1 1
1 1 1 0 1 0 1 0 0 0 1 1 1 0 0 0 1 1 1 1 1 1 0 0 1 1 0 1 0 1 1 0 1 1 1 0 1 0 0
1 0 0 1 0 1 1 1 0 0 1 0 1 1 0 0 1 1 0 0 0 0 0 1 0 0 1 1 1 1 0 1 1 1 0 1 1 0 1 0 1
1 0 1 1 1 0 0 1 0 0 1 1 1 1 0 1 0 1 0 0 0 0 1 1 0 1 0 0 0 1 0 1 1 1 1 1 1 0 1 1 0
1 1 0 1 1 0 1 1 0 1 0 0 1 1 0 1 1 1 0 0 0 1 0 1 0 1 0 0 1 1 1 0 0 0 0 1 1 0 1 1 1
1 1 1 1 1 1 0 1 0 1 0 1 1 1 1 0 0 1 0 0 0 1 1 1 0 1 0 1 0 1 1 0 0 0 1 1 1 1 0 0 0
(красные нули выделены жирным шрифтом и подчеркнуты)

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

Формат входного файла

Во входном файле содержатся числа n и k .

Формат выходного файла

Выходной файл должен содержать одно число — количество красных нулей.

Ограничения

1 ≤ n < 231, 1 ≤ k ≤ 30

Примеры тестов

№ Входной файл (zeroes.in) Выходной файл (zeroes.out)
1 
4 1
 
3
2 
56 2
 
74
0.071s 0.006s 15