ZOJ1633 Big String(递推)

2018/08/02 19:34
阅读数 31

ZOJ1633 Big String


Time Limit: 2 Seconds Memory Limit: 65536 KB


Description

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.

Input

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

Output

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

Sample Input

1
2
4
8

Sample Output

T
.
^
T

题解

题意

对于给出的初始字符串A,B。组成C=BA。然后,使得A=B,B=C。问:第N个符号是什么?

思路

比较容易求得每次字符串的长度,通过每次减去字符串的长度直到长度小于7,最终可以得到当前值。

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 0x3f3f3f3f;

const int MAXN = 1e6+10;
ll strr[MAXN];
int main(){
	string C = "T.T^__^";
	strr[0] = 4 ;strr[1]=3;
	for(int i=2;i<MAXN;i++){
		strr[i]=strr[i-1]+strr[i-2];
	}
	ll N = 0;
	while(~scanf("%lld",&N)){
		while(N>7){
			int i = 0;
			while(strr[i]<N) i++;
			N -= strr[i-1];
		}
		printf("%c\n",C[N-1]);
	}
	return 0;
	
}

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部