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......
解题思路: 暴力了把 a,b的 [0,9]的所有情况都枚举输出了一遍,发现除了(a=0,b=0)之外的特殊情况,只有两种循环方式 {1,4,5,9} 和 {1,1,2,3,5,8,1,3,4,7}
但是开始循环的地方不一样,不过长度都在10以内. 写了个暴力程序:
View Code
#include<stdio.h> #include<string.h> #include<stdlib.h> #include<algorithm> #include<iostream> #include<map> using namespace std; const int N = 101010; map< pair<int,int>, bool > Mp; int key[2][10] = { {1,1,2,3,5,8,1,3,4,7},{1,4,5,9} }; int val[N],str[10][10][100]; int len[10][10] = {0}, mod[2] = {10,4}; bool vis[10][10]; void init() { Mp.clear(); for(int i = 0; i < 3; i++) Mp[ make_pair(key[1][i],key[1][i+1]) ] = true; for(int i = 0; i < 9; i++) Mp[ make_pair(key[0][i],key[0][i+1]) ] = true; memset( vis, false, sizeof(vis)); vis[0][7] = true; vis[1][4] = true; vis[2][6] = true; vis[3][1] = true; vis[4][2] = true; vis[4][5] = true; vis[5][9] = true; vis[6][8] = true; vis[7][0] = true; vis[7][7] = true; vis[8][6] = true; vis[9][5] = true; } void func(int a, int b) { int i; for(i = 1; i < 100; i++) { if( Mp.count( make_pair(str[a][b][i-1],str[a][b][i]) ) ) { len[a][b] = i-1;break; } } // if( i == N ) printf("a = %d, b = %d\n", a, b ); } void GetString() { for(int a = 0; a <= 9; a++) for(int b = 0; b <= 9; b++) { if( !a && !b ) continue; str[a][b][0] = a; str[a][b][1] = b; for(int i = 2; i < 100; i++) { int tmp = str[a][b][i-1]+str[a][b][i-2]; if(tmp > 9) { str[a][b][i++] = tmp/10; str[a][b][i] = tmp%10; } else str[a][b][i] = tmp; } func( a, b ); // printf("(%d,%d) : %d\n", a, b, len[a][b] ); } } void solve(int a, int b, int n) { // printf("len[a][b] = %d\n", len[a][b] ); // for(int i = 0; i < 50; i++) // printf("%d", str[a][b][i] ); puts(""); if( n < len[a][b] ) printf("%d\n", str[a][b][n] ); else { int x = (n-len[a][b])%( mod[ vis[a][b] ] ); int res = str[a][b][ x+len[a][b] ]; printf("%d\n", res ); } } int main() { init(); GetString(); int a, b, n, T; scanf("%d", &T); for(int Case = 1; Case <= T; Case++ ) { scanf("%d%d%d", &a,&b,&n); printf("Case #%d: ", Case ); if( !a && !b ) puts("0"); else solve( a, b, n-1 ); } return 0; }