← 返回题目列表

Codeforces · 457/A

A. 黄金系统

中文机器翻译题面 查看原题

Piegirl 厌倦了二进制、十进制和其他基于整数的计数系统。最近,她发现了关于数字 $$q = \frac{\sqrt{5}+1}{2}$$ 的一些有趣的属性,特别是 q2 = q + 1,她认为这将为她的新独特系统奠定良好的基础。她称之为“黄金系统”。在黄金系统中,数字是包含 0 和 1 作为数字的非空字符串。表达式 a0a1...an 的十进制值等于 $$\sum_{i=0}^{n} a_i \cdot q^{n-i}$$。

很快 Piegirl 发现这个系统不具有与整数基系统相同的属性,并且无法对其执行某些操作。她无法想出一种快速方法来比较两个数字。她正在寻求你的帮助。

给定两个用黄金系统表示法写成的数字,确定其中哪个具有更大的十进制值。

输入

输入由两行组成 - 每个数字一行。每行包含由“0”和“1”字符组成的非空字符串。每个字符串的长度不超过100000。

输出

如果第一个数字较大,则打印“">”;如果第一个数字较小,则打印“<”;如果它们相等,则打印“=”。

示例

输入 #1

1000
111

输出 #1

<

输入 #2

00100
11

输出 #2

=

输入 #3

110
101

输出 #3

>

注意

在第一个示例中,第一个数字等于 $$( { \frac { \sqrt { 5 } + 1 } { 2 } } ) ^ { 3 } \approx 1. 6 1 8 0 3 3 9 8 8 ^ { 3 } \approx 4. 2 3 6$$,而第二个数字约为1.6180339882 + 1.618033988 + 1 ≈ 5.236,这显然是一个更大的数字。

在第二个示例中,数字是相等的。它们中的每一个都约为 2.618。