Часть 2 (решаются с использованием компьютера)

1. Единицы

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

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

Во входном файле INPUT.TXT записано целое число n (0 ≤ n ≤ 2*109).

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

В единственную строку выходного файла OUTPUT.TXT нужно вывести одно целое число — количество двоичных единиц в записи числа n.

Примеры

№      INPUT.TXT         OUTPUT.TXT

1        5                           2

2        7                          3

2. Несложное вычисление

Задано натуральное число n. Необходимо перевести его в k-ичную систему счисления и найти разность между произведением и суммой его цифр в этой системе счисления.

Например, пусть n = 239, k = 8. Тогда представление числа n в восьмеричной системе счисления — 357, а ответ на задачу равен 3 × 5 × 7 − (3 + 5 + 7) = 90.

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

Входной файл INPUT.TXT содержит два натуральных числа: n и k (1 ≤ n ≤ 109, 2 ≤ k ≤ 10). Оба этих числа заданы в десятичной системе счисления.

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

В выходной файл OUTPUT.TXT выведите ответ на задачу (в десятичной системе счисления).

Примеры

№      INPUT.TXT         OUTPUT.TXT

1        239 8                 90

2        1000000000 7       -34

3. Наименьшая система счисления

Известно, что основанием позиционной системы счисления называют количество различных символов, используемых для записи чисел в данной системе счисления. Также известно, что любое число x в b-ичной системе счисления имеет вид x=a₀∙b₀+a₁∙b₁+…+a_n∙b_n, где b ≥ 2 и 0 ≤ a_i < b.

Для записи чисел в b-ичной системе счисления, где b ≤ 36, могут быть использованы первые b символов из следующего списка 0,1,…, 9, A, B, …, Z. Например, для записи чисел в троичной системы используются символы 0, 1, 2, а в двенадцатеричной - 0,1,…, 9, A, B.

Требуется написать программу, которая по входной строке S определит, является ли данная строка записью числа в системе счисления, с основанием не большим 36, и, если является, определит минимальное основание этой системы счисления.

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

Входной файл INPUT.TXT содержит в единственной строке входную строку. Длина строки не превышает 255. Все символы строки имеют коды от 32 до 127.

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

Выходной файл OUTPUT.TXT должен содержать одно число. Если строка является записью числа в некоторой системе счисления, то нужно вывести минимальное основание такой системы счисления. Иначе вывести -1.

Примеры

№      INPUT.TXT         OUTPUT.TXT

1        123                    4

2        ABCDEF    16

3        AD%AF              -1

 

1. Бит-реверс

Целое положительное число m записывается в двоичной системе счисления, разряды (в этой записи) переставляются в обратном порядке и число переводится в десятичную систему счисления. Получившееся число принимается за значение функции B(m).

Требуется написать программу, которая для заданного m вычислит B(m).

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

Входной файл INPUT.TXT содержит натуральное число m (m <= 109).

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

В выходной файл OUTPUT.TXT выведите значение B(m).

Примеры

№      INPUT.TXT         OUTPUT.TXT

1        4                        1

2        6                        3

5. Делимость на 7

Требуется определить делимость на 7 ряда целых чисел, записанных в двоичной системе счисления.

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

В первой строке входного файла INPUT.TXT содержится N – количество чисел (N < 50). В следующих N строках содержатся двоичные числа (по одному в каждой строке). Каждое двоичное число состоит не более чем из 1000 цифр.

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

Выходной файл OUTPUT.TXT должен содержать N строк. Для каждого теста в отдельной строке надо выдать сообщение "Yes”, если соответствующее число кратно 7 или "No” в противном случае.

Примеры

№      INPUT.TXT         OUTPUT.TXT

1        3

            1110                            yes

          1010101                        no

           111111111111111111111111111      yes

2        1

              11                     No

6. Забавная игра

Легендарный учитель математики Юрий Петрович придумал забавную игру с числами. А именно, взяв произвольное целое число, он переводит его в двоичную систему счисления, получая некоторую последовательность из нулей и единиц, начинающуюся с единицы. (Например, десятичное число 1910 = 1*24+0*23+0*22+1*21+1*20 в двоичной системе запишется как 100112.) Затем учитель начинает сдвигать цифры полученного двоичного числа по циклу (так, что последняя цифра становится первой, а все остальные сдвигаются на одну позицию вправо), выписывая образующиеся при этом последовательности из нулей и единиц в столбик — он подметил, что независимо от выбора исходного числа получающиеся последовательности начинают с некоторого момента повторяться. И, наконец, Юрий Петрович отыскивает максимальное из выписанных чисел и переводит его обратно в десятичную систему счисления, считая это число результатом проделанных манипуляций. Так, для числа 19 список последовательностей будет таким:           10011

11001

11100

01110

00111

10011

…

и результатом игры, следовательно, окажется число 1*24+1*23+1*22+0*21+0*20 = 28.

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

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

Входной файл INPUT.TXT содержит одно целое число N (0 <= N <= 32767).

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

Ваша программа должна вывести в выходной файл OUTPUT.TXT одно целое число, равное результату игры.

Примеры

№      INPUT.TXT         OUTPUT.TXT

1        19      28

2        1212  1938

7. Число - палиндром

Напомним, что палиндромом называется строка, одинаково читающаяся с обеих сторон. Например, строка «ABBA» является палиндромом, а строка «ABC» - нет.

Необходимо определить, в каких системах счисления с основанием от 2 до 36 представление заданного числа N является палиндромом.

В системах счисления с основанием большим 10 в качестве цифр используются буквы латинского алфавита: A, B, ... , Z. Например, A11 = 1010, Z36 = 3510.

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

Входной файл INPUT.TXT содержит заданное число N в десятичной системе счисления (1 <= N <= 109).

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

Если соответствующее основание системы счисления определяется единственным образом, то выведите в первой строке выходного файла OUTPUT.TXT слово «unique», если оно не единственно — выведите в первой строке выходного файла слово «multiple». Если же такого основания системы счисления не существует — выведите в первой строке выходного файла слово «none».

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

Примеры

№      INPUT.TXT         OUTPUT.TXT

1        123                       unique

                                       6

2        111                      multiple

                                       6 10 36

3        102892748            none

 

8. Система счисления

Вчера на уроке математики Саша узнал о том, что иногда полезно использовать вместо десятичной системы счисления какую-нибудь другую.  Однако, учительница не объяснила, почему в системе счисления по основанию b в качестве цифр выбирают числа от 0 до b - 1.

Немного подумав, Саша понял, что можно выбирать и другие наборы цифр. Например, вместо троичной системы счисления можно рассмотреть систему счисления, где вместо обычных цифр 0, 1, 2 есть цифры 1, 2 и 3.

Саша заинтересовался вопросом, а как перевести число n в эту систему счисления? Например, число 7 в этой системе записывается как 21, так как 7 = 2∙3+1, а число 22 записывается как 211, так как 22 = 2 ∙ 9 + 1 ∙ 3 + 1.

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

Входной файл INPUT.TXT содержит натуральное число n, 1 ≤ n ≤ 2•109.

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

В выходной файл OUTPUT.TXT выведите число n записанное в указанной системе счисления.

Примеры

№      INPUT.TXT         OUTPUT.TXT

1        7                        21

2        22                     211