training_2006_04_22 - LCA на полном бинарном дереве

Задача A. LCA на полном бинарном дереве ≡

задачи
детали
видимые пробелы
простые формулы
широкий текст
редактор

Автор:	И. Туфанов	Ограничение времени:	2 сек
Входной файл:	input.txt	Ограничение памяти:	64 Мб
Выходной файл:	output.txt

Условие

Дано бесконечное полное бинарное дерево. Его вершины пронумерованы следующим образом: корень имеет номер 1, для каждой вершина с номером n ее левый ребенок имеет номер 2*n+1, а правый 2*n.

Две вершины заданы своими номерами. Найдите номер их наименьшего общего предка, то есть располженного дальше от корня.

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

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

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

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

Ограничения

1 ≤ N ≤ 2³¹−1

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

№	Входной файл (`input.txt`)	Выходной файл (`output.txt`)
1	`12 7`	`3`