#111587

Фибоначчи

Темы: [Системы счисления]

Числа Фибоначчи - элементы числовой последовательности, в которой каждое последующее число равно сумме двух предыдущих чисел. Более формально, последовательность чисел Фибоначчи {F_n} задается линейным рекуррентным соотношением:

F₁ = 1, F₂ = 2, F_n = F_n - 1 + F_n - 2, n ≥ 2

Рассмотрим систему счисления с двумя цифрами 0 и 1, в которой, в отличие от двоичной системы весами являются не степени двойки 1,2,4,8,16,..., а числа Фибоначчи 1,2,3,5,8,13,.... В этой системе счисления каждое положительное целое число единственным образом представляется в виде строки нулей и единиц, которая начинается с 1 и в которой нет двух единиц, стоящих рядом.

Даны две строки, представляющие натуральные числа A и B. Найти строку, представляющую число A+B.

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

Даны две строки, представляющие A и B, состоящие из нулей и единиц. Длина каждой из строк не превышает 10⁴.

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

Выведите строку, представляющую число A + B. Обратите внимание, что она должна начинаться с единицы.

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

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

10101
100

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

Примечание

Исходные строки '10101' и '100' представляют числа 8 + 3 + 1 = 12 и 3. Ответом является строка '100010', представляющая строку 13 + 2 = 15 = 12 + 3.

#111588

Количество единиц

Темы: [Битовые операции]

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

Дано целое число x (0 ≤ x ≤ 4·10¹⁸).

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

Вывести количество единиц в двоичной записи числа x.

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

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

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

#111589

Последовательность

Темы: [Рекурсия]

Последовательность 011212201220200112... строится так: сначала пишется 0, затем повторяется следующее действие: уже написанную часть приписывают справа с заменой 0 на 1, 1 на 2, 2 на 0, т.е.:

0 → 01 → 0112 → 01121220 → ... Составить алгоритм, который по введенному k определяет, какое число стоит на k-ом месте в последовательности.

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

Дано натуральное число k (1 ≤ k ≤ 10¹⁸).

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

Выведите число, которое стоит на k-ом месте в последовательности.

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

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

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

#111590

Два массива

Темы: [Одномерные массивы]

Даны два массива X и Y одинаковой длины. Записать алгоритм, меняющий последовательно местами значения элементов X[k] и Y[k] для этих таблиц, для k = 1, 2, ..., n, не используя промежуточных переменных.

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

В первой строке содержится одно число n — количество элементов в каждом из массивов. (1 ≤ n ≤ 100{, }000) Во второй строке через пробел записаны натуральные числа первого массива. В третьей строке через пробел записаны натуральные числа второго массива (Гарантируется, что числа не превышают 10⁶)

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

В первой строке выведите через пробел все элементы второго массива, а во второй строке — первого.

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

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

3
1 2 3
4 5 6

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

4 5 6 
1 2 3

#111591

Точки на плоскости

Темы: [Битовые операции]

Точки с целочисленными координатами из 1-го квадранта помечаются числами 0,1,2,... слева направо и снизу вверх таким образом, что очередной точке приписывается минимальное число, отсутствующее в вертикали и горизонтали, проходящей через точку. Первой помечается точка (0,0).

То есть допустим мы хотим пометить точку (i, j). Это значит, что все точки, находящиеся ниже и левее относительно нее уже помечены. Тогда рассмотрим набор из чисел в i-ом столбце и j-ом столбце (вместе). Отметкой точки (i, j) будет минимальное неотрицательное число, которое не содержится в этом наборе.

Написать программу, которая

По заданным координатам x и y, x ≥ 0, y ≥ 0, x, y — целые, определяет пометку точки.
По заданной координате x и пометке точки c, x ≥ 0, y ≥ 0, x, y — целые, определяет вторую координату точки.

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

В первой строке даются два числа x и y для первой части задачи (0 ≤ x, y ≤ 10⁹). Во второй строке даются два числа x и c для второй части задачи (0 ≤ x ≤ 10⁹, 0 ≤ c ≤ 2·10⁹)

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

Выведите два числа. В первой строке выведите ответ на первую часть задачи, а во второй — на вторую.

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

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

3 4
5 23

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

7
18