| MemSQL Start[c]UP 2.0 - Round 2 |
|---|
| Закончено |
Piegirl надоела двоичная, десятичная и все остальные системы счисления с целочисленным основанием. Недавно она обнаружила весьма интересные свойства числа 
, одно из из них можно записать следующим образом: q2 = q + 1. Piegirl считает, что число q может быть неплохим основанием для новой системы счисления, которую она назовет «золотая система счисления». Число в золотой системе счисления — это непустая строка, состоящая из нулей и единиц. Десятичное значение числа a0a1...an равно 
.
Немного поизучав новую систему счисления, Piegirl поняла, что эта система не обладает некоторыми свойствами, которыми обладают системы счисления с целочисленным основанием. В частности, сравнение двух чисел в этой системе счисления — не такая тривиальная задача.
Вам заданы два числа в золотой системе счисления, сравните их.
Входные данные состоят из двух строк, в каждой из которых записана непустая строка из нулей и единиц. Длина каждой строки не превосходит 100000.
Выведите «>», если первое число больше второго; выведите «<», если первое число меньше второго; иначе, выведите «=».
1000
111
<
00100
11
=
110
101
>
В первом примере первое число равно 
, второе число приблизительно равно 1.6180339882 + 1.618033988 + 1 ≈ 5.236. Очевидно, что первое число меньше.
Во втором примере числа равны. Каждое из них приблизительно равно ≈ 2.618.
