Question

Недавно палеонтологи обнаружили останки динозавра Linhenykus monodactylus, у которого на каждой передней конечности было только по одному пальцу. Распространение десятичной системы счисления связывают с количеством пальцев рук у человека. Значит, динозавры пользовались двоичной системой счисления. Точнее, супердвоичной системой, в которой для записи чисел использовались только «цифры» −1, 0 или 1. Супердвоичной записью числа n динозавры называли представление n в виде 2 kak + . . . + 22a2 + 2a1 + a0, где каждое из чисел ai равно −1, 0 или 1 и ai · ai+1 = 0 для всех 0 6 i 6 k − 1. Например, число 3 в этой системе записывалось в виде 1 0 −1, так как 3 = 22 · 1 + 2 · 0 + (−1). Ваша задача —– научиться записывать числа в супердвоичной системе динозавров. Формат входных данных В единственной строке записано целое число n (1 6 n 6 1018). Формат выходных данных Единственная строка содержит последовательность из разделенных пробелом целых чисел ak, . . . , a1, a0, образующих запись числа n в супердвоичной системе счисления. Число ak является первой (слева) цифрой в записи числа n, а a0 — его последней цифрой. Если таких представлений несколько, выведите любое из них.

Answer 1

На Питоне. Решение на скрине. Ввод - вывод стандартный.

Answer 2

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

Супердвоичная система счисления использует только цифры -1, 0 и 1. Чтобы записать число n в супердвоичной форме, мы должны разложить его на сумму степеней двойки, где каждое из чисел ai равно -1, 0 или 1, и при этом ai * ai+1 = 0 для всех 0 <= i <= k - 1.

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

Приведем алгоритм для этого:

1. Инициализируем список, в котором будем хранить коэффициенты ai.
2. Пока число n больше нуля, выполняем следующие шаги:
   • Находим наибольшую степень двойки, которая меньше или равна n, пусть это будет 2^k.
   • Вычисляем ai как n // 2^k (целочисленное деление) и добавляем ai в список.
   • Вычитаем из n значение ai * 2^k.

Теперь, когда у нас есть список коэффициентов ai, составим из них строку в обратном порядке и вернем ее.

Давайте реализуем этот алгоритм на Python:

pythonCopy code
def super_binary_representation(n):
    coefficients = []
    while n > 0:
        k = 0
        while 2 ** k <= n:
            k += 1
        k -= 1
        ai = n // (2 ** k)
        coefficients.append(ai)
        n -= ai * (2 ** k)
    
    super_binary_string = " ".join(str(ai) for ai in coefficients[::-1])
    return super_binary_string

# Пример использования:
n = int(input())
result = super_binary_representation(n)
print(result)

Теперь вы можете вводить различные значения n и программа вернет представление числа в супердвоичной системе счисления, как указано в условии задачи.