K - Stern-Brocot Tree

Time Limit: 1 sec
Memory Limit: 16MB

In number theory, the Stern-Brocot tree is a method of listing all non-negative rational numbers as well as a point representing infinity (here represented formally as 1/0).

The tree may be created by an iterative process. It is easiest to describe as a list. Beginning with the list {0/1, 1/0} representing 0 and infinity respectively, one places between any two fractions the mediant of the fractions (the mediant of a/c and b/d is (a + b)/(c + d)). The first few steps of this process yield:
{0/1, 1/0}
{0/1, 1/1, 1/0}
{0/1, 1/2, 1/1, 2/1, 1/0}
{0/1, 1/3, 1/2, 2/3, 1/1, 3/2, 2/1, 3/1, 1/0}

This process can be represented as a tree where each row corresponds to the new numbers added at each step.

From Wikipedia

The position of a fraction in the tree can be specified as a path consisting of L(left) an R(right) moves along the tree starting from the top (fraction 1/1). Your have to find a fraction by a given path.

INPUT:

OUTPUT:

SAMPLE INPUT:

3
RL
RLR
RRL

SAMPLE OUTPUT:

3/2
5/3
5/2

#include <stdio.h>

int main() {
    int t;
    char str[100];
    scanf("%d ", &t);
    while(t--) {
        gets(str);
        unsigned long long la = 0, lb = 1, ma = 1, mb = 1, ra = 1, rb = 0;
        unsigned long long x = 1, y = 1, i;
        for(i = 0; str[i]; i++) {
            if(str[i] == 'L') {
                x = la+ma, y = lb+mb;
                ra = ma, rb = mb;
                ma = x, mb = y;
            } else {
                x = ra+ma, y = rb+mb;
                la = ma, lb = mb;
                ma = x, mb = y;
            }
        }
        printf("%llu/%llu\n", x, y);
    }
    return 0;
}

您可能對以下文章有興趣

[UVA][倒水問題] 571 - Jugs

[UVA] 11849 - CD

[UVA][離散化&掃描線&BIT] 10869 - Brownie Points II

[UVA][greedy] 11493 - The Club Ballroom