2499:Binary Tree

keyword

二分木　C++

概要

根が(1,1)の二分木があり、(a,b)の左の子は(a+b,b)、右の子は(a,a+b)である。(x,y)が与えられたとき、根から左右にそれぞれ何回落ちたらその頂点にたどり着けるかを求める問題。
TopCoderのSRMだったかTCOだったかで似たような問題があった(TwoRegisters)。大小関係を見れば直前にどちらが足されたのか分かるので再帰で書く。ただし(10^8,1)みたいなのでTLEしないように気を付ける必要があるとか思ってたけど実はいらなかったかも。後leftとrightが変数名で使えなくて困った。lとrは使ってたからllとrrにしようと思ったけどllはlong longだったし。

static int lll, rr;

void solve(int l, int r){
    if(!l || !r || (r!=1 && l==r)){printf("error\n");return ;}
    if(r==1) lll += l-1;
    else if(l==1) rr += r-1;
    else if(l > r){lll += l/r; solve(l%r, r);}
    else if(r > l){rr += r/l; solve(l, r%l);}
    return ;
}

int main(){
    int rept, l, r;
    scanf("%d",&rept);
    LOOP(rept){
        scanf("%d%d",&l,&r);
        lll = 0; rr = 0;
        solve(l,r);
        printf("Scenario #%d:\n",loopCount);
        printf("%d %d\n",lll, rr);
        if(loopCount<rept) printf("\n");
    }
}