Во всех задачах этого листка ввод-вывод стандартный.

В системе счисления с основанием больше 10, цифры записываются так: 0, 1, 2, ..., 9, A, B, C, ...

В тексте программ на языке Python можно использовать целочисленные константы, записанные в двоичной (префикс 0b), восьмеричной (префикс 0o) и шестнадцатеричной (префикс 0x) системах счисления. После указанного префикса идут цифры, которые в двоичной системе счисления могут быть только 0 или 1, в восьмеричной — от 0 до 7, в шестнадцатеричной — от 0 до 9, а также буквы латинского алфавита от A до F (могут быть как строчными, так и заглавными). Например, десятичной число 179 можно задать несколькими способами.

A = 179
A = 0b10110011
A = 0o263
A = 0xB3

Если вы знаете стандартные функции языка Python для перевода представления чисел между различными системами счисления, то этими функциями пользоваться нельзя. Также нельзя использовать функции типа eval, exec и т.д.

Если программа выводит результат в системе счисления с основанием больше 10, то цифры записываются так: 0, 1, 2, ..., 9, A, B, C, ...

Упражнения

01: Шестнадцатеричная цифра - 1

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

Программа должна содержать функцию перевода hex2int(c). Аргумент функции имеет тип str, результат — int.

9

9

F

15

02: Шестнадцатеричная цифра - 2

Решите задачу, обратную предыдущей.

9

9

15

F

03: Из двоичной в десятичную

Дано число, записанное в двоичной системе счисления. Переведите его в тип int и выведите на экран в десятичном виде. Исходное число необходимо считать в переменную типа string, для перевода реализовать функцию bin2int(s). Аргумент функции имеет тип str, результат — int.

10110011

179

04: Из шестнадцатеричной в десятичную

Решите предыдущую задачу в случае, когда входное число задано в шестнадцатеричном виде. Соответствующая функция должна называться hex2int(s). Аргумент функции имеет тип str, результат — int.

B3

179

05: Из десятичной в двоичную

Переведите число из десятичной системы в двоичную. Соответствующая функция должна называться int2bin(n). Аргумент функции — число типа int, результат имеет тип str.

179

10110011

06: Из десятичной в шестнадцатеричную

Переведите число из десятичной системы в шестнадцатеричную. Соответствующая функция должна называться int2hex(n).

179

B3

07: Из любой в любую

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

На вход программа получает три величины: n, A, k, где n и k – натуральные числа от 2 до 36: основания системы счисления, A – число, записанное в в системе счисления с основанием n, A<2³¹.

Необходимо вывести значение A в системе счисления с основанием k без лидирующих нулей.

2
101111
16

2F

10
35
36

Z

Указание. Напишите две функции перевода — из числа в произвольной системе счисления, записанного в переменной типа str в переменную типа int и обратно.

08: Из шестнадцатеричной в двоичную

Переведите число из шестнадцатеричной системы счисления в двоичную. Исходное число может быть очень большим (до $2\times10^5$ символов). Необходимо вывести результат без лидирующих нулей.

2F

101111

09: Из двоичной в шестнадцатеричную

Переведите число из двоичной системы счисления в шестнадцатеричную. Исходное число может быть очень большим (до $1{,}2\times10^6$ символов).

101111

2F

10: Из уравновешенной троичной в десятичную

В уравновешенной троичной системе счисления используется основание 3 и три цифры: 0, 1 и -1. Цифру -1 будем обозначать знаком $. Достоинство уравновешенной троичной системы счисления: простота хранения отрицательных чисел и удобство нахождения числа, противоположному данному.

Вот как записываются небольшие числа в уравновешенной троичной системе счисления:

Подробней о уравновешенной троичной системе счисления можно прочитать в Википедии (статья Троичная система счисления, там используется термин "троичная симметричная система счисления") а также в этой статье.

Дана запись числа в уравновешенной троичной системе счисления. Переведите его в десятичную. Исходное число может быть очень большим (до $10^5$).

$01

-8

11: Из фибоначчиевой в десятичную

Рассмотрим последовательность Фибоначчи: F₁=1, F₂=2, F_n=F_n-1+F_n-2 при n>2. В частности, F₃=2, F₄=3, F₅=5, F₆=8 и т.д.

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

Будем говорить, что число A представимо в фибоначчиевой системе счисления в виде a_ka_k-1...a₁, где a_i∈{0;1}, если A=a_kF_k+...+a₁F₁ и в записи a_ka_k-1...a₁ нет двух единиц подряд.

Вот как записываются небольшие числа в фибоначчиевой системе счисления:

Подробней о фибоначчиевой системе счисления можно прочитать в Википедии (статья Фибоначчиева система счисления).

Дана запись числа в фибоначчиевой системе счисления. Запишите его в десятичной системе счисления.

Программа получает на вход строку из символов 0 и 1 и должна вывести одно целое число. Гарантируется, что результат может принимать значения от 0 до 2·10⁹.

10101

12

12: Из десятичной в уравновешенную троичную

Дано целое число oт -2·10⁹ до 2·10⁹. Выведите его представление в уравновешенной троичной системе счисления без лидирующих нулей.

-8

$01

13: Из десятичной в фибоначчиеву

Дано целое число oт 0 до 2·10⁹. Выведите его представление в фибоначчиевой системе счисления без лидирующих нулей.

12

10101

14: Инкремент

Первая строка входных данных содержит последовательность символов '0', ..., '9', 'A', ..., 'Z', являющейся записью некоторого неотрицательного числа в системе счисления с основанием base. Длина числа не превосходит 100000 символов. Вторая строка входных данных содержит основание системы счисления base, не превосходящее 36.

Увеличьте это число на 1 и выведите результат в той же системе счисления.

19A
11

1A0

15: Декремент

Первая строка входных данных содержит последовательность символов '0', ..., '9', 'A', ..., 'Z', являющейся записью некоторого положительного числа в системе счисления с основанием base. Длина числа не превосходит 100000 символов. Вторая строка входных данных содержит основание системы счисления base, не превосходящее 36.

Уменьшите это число на 1 и выведите результат в той же системе счисления.

1A0
11

19A

16: Инкремент в уравновешенной троичной системе счисления

Дана запись некоторого числа в уравновешенной троичной системе счисления, длина записи не превосходит 100000 символов.

Увеличьте это число на 1 и выведите его значение в той же системе.

$01

$1$

17: Декремент в уравновешенной троичной системе счисления

Уменьшите на 1 длинное число, записанное в уравновешенной троичной системе счисления.

$1$

$01

18: Фибоначчиев инкремент

Дано целое неотрицательное число n, записанное в фибоначчиевой системе счисления, длина числа не превосходят 100000 символов. Выведите значение числа n+1 в фибоначчиевой системе счисления.

100101

101000

19: Фибоначчиев декремент

Дано целое положительное число n, записанное в фибоначчиевой системе счисления, длина числа не превосходят 100000 символов. Выведите значение числа n-1 в фибоначчиевой системе счисления.

101000

100101

20: Шестнадцатеричная сумма

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

F1
F

100

21: Уравновешенное троичное сложение

Дано два числа, записанных в уравновешенной троичной системе счисления. Выведите их сумму без лидирующих нулей. Длины входных чисел не превосходят 100.000 символов.

1$$$
$0$

11

Пример соответствует выражению 14+(-10)=4.

22: Фибоначчиево сложение

Даны два числа, записанные в фибоначчиевой системе счисления, длины чисел не превосходят 100.000 символов. Выведите значение их суммы в фибоначчиевой системе счисления.

10010
10101

1000001

23: Марсианские факториалы

В 3141 году очередная экспедиция на Марс обнаружила в одной из пещер таинственные знаки. Они однозначно доказывали существование на Марсе разумных существ. Однако смысл этих таинственных знаков долгое время оставался неизвестным. Недавно один из ученых, профессор Очень-Умный, заметил один интересный факт: всего в надписях, составленных из этих знаков, встречается ровно $K$ различных символов. Более того, все надписи заканчиваются на длинную последовательность одних и тех же символов.

Вывод, который сделал из своих наблюдений профессор, потряс всех ученых Земли. Он предположил, что эти надписи являются записями факториалов различных натуральных чисел в системе счисления с основанием $K$. А символы в конце — это конечно же нули — ведь, как известно, факториалы больших чисел заканчиваются большим количеством нулей. Например, в нашей десятичной системе счисления факториалы заканчиваются на нули, начиная с $5!=1\times2\times3\times4\times5$. А у числа $100!$ в конце следует $24$ нуля в десятичной системе счисления и $48$ нулей в системе счисления с основанием 6 — так что у предположения профессора есть разумные основания!

Теперь ученым срочно нужна программа, которая по заданным числам $N$ и $K$ найдет количество нулей в конце записи в системе счисления с основанием $K$ числа $N!$, чтобы они могли проверить свою гипотезу. Вам придется написать им такую программу!

В первой строке входных данных содержатся числа $N$ и $K$, разделенные пробелом, ($1\le N \le 10^9$, $2 \le K \le 1000$). Выведите число $X$ — количество нулей в конце записи числа $N!$ в системе счисления с основанием $K$.

24: Счастливые цифры

Школьнику Васе нравятся числа, которые заканчиваются счастливыми для него цифрами $k$. Поэтому каждый раз, когда он видит какое-нибудь натуральное число n, он сразу пытается подобрать такое $d$ ($d \ge 2$), что число $n$ в системе счисления с основанием $d$ заканчивается как можно большим количеством цифр $k$.

Требуется написать программу, которая по заданным числам $n$ и $k$ найдет такое $d$, чтобы число $n$ в системе счисления с основанием $d$ заканчивалось как можно большим количеством цифр $k$.

Вводятся два целых десятичных числа $n$ и $k$ ($1 \le n \le 10^{11}$, $0 \le k \le 9$).

Выведите два числа: $d$ — искомое основание системы счисления и $l$ — количество цифр $k$, которым заканчивается запись числа $n$ в этой системе счисления. Если искомых $d$ несколько, выведите любое из них, не превосходящее $10^{12}$ (такое всегда существует).