2018/08/02 19:34

# 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


# 题解

## 代码

#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