编程介的小学生 2017-08-29 15:42 采纳率: 20.5%
浏览 682
已采纳

Death to Binary?

The group of Absurd Calculation Maniacs has discovered a great new way how to count. Instead of using the ordinary decadic numbers, they use Fibonacci base numbers. Numbers in this base are expressed as sequences of zeros and ones similarly to the binary numbers, but the weights of bits (fits?) in the representation are not powers of two, but the elements of the Fibonacci progression (1, 2, 3, 5, 8,... - the progression is defined by F0 = 1, F1 = 2 and the recursive relation Fn = Fn-1 + Fn-2 for n >= 2).

For example 1101001Fib = F0 + F3 + F5 + F6 = 1 + 5 + 13 + 21 = 40.

You may observe that every integer can be expressed in this base, but not necessarily in a unique way - for example 40 can be also expressed as 10001001Fib. However, for any integer there is a unique representation that does not contain two adjacent digits 1 - we call this representation canonical. For example 10001001Fib is a canonical Fibonacci representation of 40.

To prove that this representation of numbers is superior to the others, ACM have decided to create a computer that will compute in Fibonacci base. Your task is to create a program that takes two numbers in Fibonacci base (not necessarily in the canonical representation) and adds them together.

Input

The input consists of several instances, each of them consisting of a single line. Each line of the input contains two numbers X and Y in Fibonacci base separated by a single space. Each of the numbers has at most 40 digits. The end of input is not marked in any special way.

Output

The output for each instance should be formated as follows:

The first line contains the number X in the canonical representation, possibly padded from left by spaces. The second line starts with a plus sign followed by the number Y in the canonical representation, possibly padded from left by spaces. The third line starts by two spaces followed by a string of minus signs of the same length as the result of the addition. The fourth line starts by two spaces immediately followed by the canonical representation of X + Y. Both X and Y are padded from left by spaces so that the least significant digits of X, Y and X + Y are in the same column of the output. The output for each instance is followed by an empty line.

Sample Input

11101 1101
1 1
Sample Output

100101

  • 10001

    1001000

    1

  • 1

    10

  • 写回答

1条回答 默认 最新

  • threenewbee 2017-09-13 15:52
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 MATLAB动图的问题
  • ¥15 求差集那个函数有问题,有无佬可以解决
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名