Binary Tree
| Time Limit: 1000MS |
|
Memory Limit: 65536K |
| Total Submissions: 6268 |
|
Accepted: 2887 |
Description
Background
Binary trees are a common data structure in computer science. In this problem we will look at an infinite binary tree where the nodes contain a pair of integers. The tree is constructed like this:
- The root contains the pair (1, 1).
- If a node contains (a, b) then its left child contains (a + b, b) and its right child (a, a + b)
Problem
Given the contents (a, b) of some node of the binary tree described above, suppose you are walking from the root of the tree to the given node along the shortest possible path. Can you find out how often you have to go to a left child and how often to a right
child?
Input
The first line contains the number of scenarios.
Every scenario consists of a single line containing two integers i and j (1 <= i, j <= 2*109) that represent
a node (i, j). You can assume that this is a valid node in the binary tree described above.
Output
The output for every scenario begins with a line containing "Scenario #i:", where i is the number of the scenario starting at 1. Then print a single line containing two numbers l and r separated by a single space, where l is how often you have to go left and
r is how often you have to go right when traversing the tree from the root to the node given in the input. Print an empty line after every scenario.
Sample Input
3
42 1
3 4
17 73
Sample Output
Scenario #1:
41 0
Scenario #2:
2 1
Scenario #3:
4 6
很简单，可以退着走，如果此时a>b说明上一层往左走才到该节点的，则left要增加1，a=a-b退到上一层，同样b>a的话是上一层往右走，right增加1，b=b-a。
算法就这么简单，但是会超时，因为假如在节点（1,100000）处，那么就要执行99999次b=b-a，能不超时吗？
只需要修改一下就好了，即我们一步就要推到不能再往这个方向退了为止，即如果a>b，我们要一次性退到b>a，可以这样：
left+=a/b; a=a-(a/b)*b;(即a=a%b);
最后注意输入格式，多一个空行。
#include <stdio.h>
#include <string.h>
typedef __int64 ll;
int main()
{
ll a,b,left,right;
int T,kcase=1;
scanf("%d",&T);
while(T--){
scanf("%I64d%I64d",&a,&b);
left=right=0;
while(a!=1 && b!=1){
if(a>b){
left+=a/b;
a%=b;
}
else{
right+=b/a;
b%=a;
}
}
if(a==1) right+=b-1;
if(b==1) left+=a-1;
printf("Scenario #%d:\n%I64d %I64d\n",kcase++,left,right);
if(T)
printf("\n");
}
return 0;
}
POJ 2499 Binary Tree
原文：http://blog.csdn.net/u013068502/article/details/45269295
