Infinite Binary Tree

Interview

Time limit1sMemory limit128 MB

Summary
Given target pair (A,B) reachable in an infinite binary tree defined by additive child rules, count the left and right moves needed via a Euclidean-like reverse process.
Level

Medium4 of 10

Topics
Math, Number theory, Simulation
Solved
No attempts yet

Problem

Consider an infinite binary tree built by the following rules. Each node stores an ordered pair of two integers.

  1. The root stores (1, 1).
  2. If a node stores (a, b), its left child stores (a+b, b), and its right child stores (a, a+b).

Given a node, we want to find a shortest path from the root to that node. The path itself may be very long, so only the number of moves to a left child and the number of moves to a right child are required.

Given two integers A and B, write a program that computes how many times the shortest path from the root to the node storing (A, B) moves to a left child and to a right child.

Input

The first line contains two integers A and B. (1 ≤ A, B ≤ 2,000,000,000)

No invalid input is given.

Output

Print two integers L and R on the first line. L is the number of moves to a left child, and R is the number of moves to a right child.

Examples1

  1. Example 1

    Input
    3 4
    Expected output
    2 1