2014
11-05

# Continued Fraction

Dumbear loves numbers very much.
One day Dumbear found that each number can be expressed as a continued fraction. See below.

Formally, we say a number k can be expressed as a continued faction if

where a0, a1, …, an are positive integers except that a0 maybe be 0 and an cannot be 1.
Dumbear also found a sequence which looks like the Farey sequence. Initially the sequenceand if we insert an elementbetween all the two adjacent element,in Di, then we get a sequence Di+1. So you can seeandAssume initially you are on the elementin D0, and if now you are on the element k in Di, then if you go left(‘L’)(or right(‘R’)) you will be on the left(or right) element of k in Di+1. So a sequence composed of ‘L’ and ‘R’ denotes a number. Such as ‘RL’ denotes the number

Now give you a sequence composed of ‘L’ and ‘R’, you should print the continued fraction form of the number. You should use ‘-‘ to show the vinculum(the horizontal line), you should print one space both in front and back of ‘+’, and all parts up or down the vinculum should be right aligned. You should not print unnecessary space, ‘-‘ or other character. See details in sample.

There are several test cases in the input.
For each test case, there is a single line contains only a sequence composed of ‘L’ and ‘R’. The length of the sequence will not exceed 10000.
The input terminates by end of file marker.

There are several test cases in the input.
For each test case, there is a single line contains only a sequence composed of ‘L’ and ‘R’. The length of the sequence will not exceed 10000.
The input terminates by end of file marker.

LR
RL

        1
0 + -----
1
1 + -
2
1
1 + -
2

#include <cstdio>
#include <cstring>
#include <algorithm>

typedef long long ll;
const int MAX = 100000;
const int LEN = 100000;
char buffer[MAX];
ll a[MAX];
ll space[LEN],vin[LEN],bit[LEN];

static ll BIT[18] = {-1,9LL,99LL,999LL,9999LL,99999LL,999999LL,9999999LL,99999999LL,999999999LL,9999999999LL,99999999999LL,999999999999LL,
9999999999999LL,99999999999999LL,999999999999999LL};
inline int getBit(const ll& x) {
for (int i = 0; i < 18; ++i) {
if (x <= BIT[i]) return i;
}
return 18;
}

int main() {
//freopen("C.out", "w", stdout);
while (~scanf(" %s", buffer)) {
int len = strlen(buffer);
int deep = 0, cur;
if (buffer[0] == 'L') a[deep++] = 0;
cur = 1;
for (int i = 1; i < len; ++i) {
if (buffer[i] == buffer[i-1]) {
++cur;
} else {
a[deep++] = cur;
cur = 1;
}
}
a[deep] = ++cur;
if (deep == 0) {
printf("%I64d\n", a[0]);
continue;
}
for (int i = 0; i <= deep; ++i) {
bit[i] = getBit(a[i]);
}
vin[deep-1] = bit[deep];
for (int i = deep-2; i >= 0; --i) vin[i] = vin[i+1] + 3 + bit[i+1];
int LENGTH = vin[0] + 3 + bit[0];
space[0] = 0;
for (int i = 1; i <= deep; ++i) {
space[i] = space[i-1] + bit[i-1] + 3;
}

//printf("LENGTH = %d\n", LENGTH);
for (int i = 0; i < deep; ++i) {
for (int j = 1; j < LENGTH; ++j) putchar(' ');
putchar('1');
putchar('\n');
for (int j = 0; j < space[i]; ++j) putchar(' ');
printf("%I64d + ", a[i]);
for (int j = 0; j < vin[i]; ++j) putchar('-');
putchar('\n');
}
for (int j = 0; j < LENGTH-bit[deep]; ++j) putchar(' ');
printf("%I64d\n", a[deep]);
}
return 0;
}
/*
LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRLLLLLLLLLLLLLLLLLLLLLLLLLLLRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRLLLLLLLLLLLLLLLLLLLLLLLLLLLRLRLRLLRLRLRLRLRLRRRRRRRRRRR
*/

1. 我还有个问题想请教一下，就是感觉对于新手来说，递归理解起来有些困难，不知有没有什么好的方法或者什么好的建议？

2. int half(int *array,int len,int key)
{
int l=0,r=len;
while(l<r)
{
int m=(l+r)>>1;
if(key>array )l=m+1;
else if(key<array )r=m;
else return m;
}
return -1;
}
这种就能避免一些Bug
l,m,r
左边是l,m;右边就是m+1,r;