TIOJ 1101 D.分「樹」

#include <cstdio>
#include <cstdlib>
using namespace std;

struct node{
    int up, down;
};

node add(const node a, const node b){
    node c;
    c.up = a.up + b.up;
    c.down = a.down + b.down;
    return c;
}

int main(){
    int n, m;
    while(1){
        scanf("%d %d",&n, &m);
        if(n + m == 0){break;}
        if(n == 1){
            if (m == 1){ printf("0/1\n"); }
            if (m == 2){ printf("1/0\n"); }
            continue;
        }

        node l, r, mid;
        l.up = 0;  l.down = 1;
        r.up = 1;  r.down = 0;

        int l_num = 0, r_num = 1 << (n-2), mid_num;
        for(int i = 1; i < n-1; i++){
            mid = add(l, r);
            mid_num = (l_num + r_num)/2;
            if(m <= mid_num){
                r = mid;
                r_num = mid_num;
            }
            else{
                l = mid;
                l_num = mid_num;
            }
        }
        
        mid = add(l, r);

        printf("%d/%d\n", mid.up, mid.down);
    }
}