CF457A.Golden System

普及+/提高

通过率:0%

时间限制:1.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Piegirl got bored with binary, decimal and other integer based counting systems. Recently she discovered some interesting properties about number , in particular that _q_2 = q + 1, and she thinks it would make a good base for her new unique system. She called it "golden system". In golden system the number is a non-empty string containing 0's and 1's as digits. The decimal value of expression _a_0_a_1...a__n equals to .

Soon Piegirl found out that this system doesn't have same properties that integer base systems do and some operations can not be performed on it. She wasn't able to come up with a fast way of comparing two numbers. She is asking for your help.

Given two numbers written in golden system notation, determine which of them has larger decimal value.

Piegirl 对二进制、十进制以及其他基于整数的计数系统感到厌倦。最近,她发现了一个有趣的数 ,特别是它满足关系式 q2=q+1q^2 = q + 1,她认为该数非常适合作为一种全新独特进制系统的基底。她将这种系统称为“黄金进制”(golden system)。在黄金进制中,一个数是一个非空字符串,仅由数字 0 和 1 组成。表达式 a0a1…ana_0 a_1 \dots a_n 的十进制值等于 。

很快,Piegirl 发现该系统不具备整数进制系统所具有的某些性质,一些运算无法直接进行。她未能找到一种快速比较两个黄金进制数大小的方法。现在她向你求助。

给定两个以黄金进制表示的数,请判断哪一个对应的十进制值更大。

输入格式

Input consists of two lines — one for each number. Each line contains non-empty string consisting of '0' and '1' characters. The length of each string does not exceed 100000.

输入包含两行,每行一个数字。每行包含一个非空字符串,仅由字符 '0' 和 '1' 组成。每个字符串的长度不超过 100000100000。

输出格式

Print ">" if the first number is larger, "<" if it is smaller and "=" if they are equal.

如果第一个数更大,输出“>”;如果更小,输出“<”;如果相等,输出“=”。

输入输出样例

  • 输入#1

    1000
    111

    输出#1

    &lt;
  • 输入#2

    00100
    11

    输出#2

    =
  • 输入#3

    110
    101

    输出#3

    &gt;

说明/提示

In the first example first number equals to , while second number is approximately 1.6180339882 + 1.618033988 + 1 ≈ 5.236, which is clearly a bigger number.

In the second example numbers are equal. Each of them is  ≈ 2.618.

在第一个例子中,第一个数等于 ,而第二个数约为 1.6180339882 + 1.618033988 + 1 ≈ 5.2361.6180339882\,+\,1.618033988\,+\,1\,\approx\,5.236,显然更大。

在第二个例子中,两个数相等,均为 ≈ 2.618\approx\,2.618。

输入解题思路,AI测评打分。不知道怎么写?

首页