1276: Big String

1276: Big String

时间限制: 1 Sec   内存限制: 128 MB

题目描述

We will construct an infinitely long string from two short strings: A = "^__^" (four characters), and B = "T.T" (three characters). Repeat the following steps:

· Concatenate A after B to obtain a new string C. For example, if A = "^__^" and B = "T.T", then C = BA = "T.T^__^".

· Let A = B, B = C -- as the example above A = "T.T", B = "T.T^__^".

Your task is to find out the n-th character of this infinite string.

输入

The input contains multiple test cases, each contains only one integer N (1 <= N <= 2^63 - 1). Proceed to the end of file.

输出

For each test case, print one character on each line, which is the N-th (index begins with 1) character of this infinite string.

样例输入 Copy

1

2

4

8

样例输出 Copy

T

.

^

T

解析：

直接做的话N那么大肯定会出问题，因此我们研究一下这个题目：

C=B+A A=B B=C

这个式子让你想到了什么？

没错，斐波那契数列。因此这道题其实就是一个简单的斐波那契数列题目。

#include<bits/stdc++.h>

using namespace std;

int main(){

char ch[8]="T.T^__^";

int f[100];

f[0]=7;f[1]=10;

for(int i=2;i<88;i++) f[i]=f[i-1]+f[i-2];

int n;

while(scanf("%d",&n)!=EOF){

while(n>7){

int j=0;

for(;j<88&&f[j]<n;j++);

n-=f[j-1];

}

printf("%c\n",ch[n-1]);

}

return 0;

}