学步园

du熊学斐波那契I

Time Limit : 2000/1000ms (C/Other)   Memory Limit : 65535/32768K (C/Other)

本次组委会推荐使用C、C++

Problem Description

du熊对数学一直都非常感兴趣。最近在学习斐波那契数列的它，向你展示了一个数字串，它称之为“斐波那契”串：

 

11235813471123581347112358........

 

聪明的你当然一眼就看出了这个串是这么构造的：

1.先写下两位在0~9范围内的数字a, b，构成串ab；

2.取串最后的两位数字相加，将和写在串的最后面。

上面du熊向你展示的串就是取a = b = 1构造出来的串。

显然，步骤1之后不停地进行步骤2，数字串可以无限扩展。现在，du熊希望知道串的第n位是什么数字。

Input

输入数据的第一行为一个整数T（1 <= T <= 1000）, 表示有T组测试数据；

每组测试数据为三个正整数a, b, n（0 <= a, b < 10, 0 < n <= 10^9）。

Output

对于每组测试数据，输出一行“Case #c: ans”（不包含引号） 

c是测试数据的组数，从1开始。

Sample Input

3

1 1 2

1 1 8

1 4 8

Sample Output

Case #1: 1

Case #2: 3

Case #3: 9

Hint

对于第一、二组数据，串为112358134711235......

对于第三组数据，串为14591459145914......

 

这题就是找循环节了。

代码如下：

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

int loc[105];

int T, a, b, n, pos;

char s[200];

bool action() {
    int x = s[pos-2], y = s[pos-1];
    int z = x + y;
    if (z >= 10) {
        s[pos] = z / 10;
        s[pos+1] = z % 10;
        pos += 2; // 平移了两个单位 
    } else {
        s[pos] = z;
        pos += 1; // 平移了一个单位 
    }
    x = s[pos-2], y = s[pos-1];
    if (loc[x*10+y] != -1) {
        return false;
    }
    loc[x*10+y] = pos-2;
    return true;
}

int main() {
    int ca = 0;
    scanf("%d", &T);
    while (T--) {
        memset(loc, 0xff, sizeof (loc));
        pos = 3;
        scanf("%d %d %d", &a, &b, &n);
        s[1] = a, s[2] = b;
        while (1) {
            if (!action()) {
                break;    
            }
        } 
        printf("Case #%d: ", ++ca);
        if (n < pos) {
            printf("%d\n", s[n]);    
        } else {
            int x = s[pos-2], y = s[pos-1];
            n -= (loc[x*10+y]-1);
            n %= (pos - 2 - loc[x*10+y]);
            printf("%d\n", s[loc[x*10+y]+n-1]);
        }
    }
    return 0;    
}