HDU 6130 Kolakoski

Problem Description

This is Kolakosiki sequence: 1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,2,1……. This sequence consists of 1 and 2, and its first term equals 1. Besides, if you see adjacent and equal terms as one group, you will get 1,22,11,2,1,22,1,22,11,2,11,22,1……. Count number of terms in every group, you will get the sequence itself. Now, the sequence can be uniquely determined. Please tell HazelFan its nth element.

Input

The first line contains a positive integer T(1≤T≤5), denoting the number of test cases. 
For each test case: 
A single line contains a positive integer n(1≤n≤107).

Output

For each test case: 
A single line contains a nonnegative integer, denoting the answer.

Sample Input

2 
1 
2

Sample Output

1 
2

题目大意：

给定Kolakoski序列a，求第n位是1还是2 
Kolakoski序列是仅仅由1和2组成的一个无限的序列，它的前几项为1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,2,1,2,1,1,2,1,2,2,1,1,……通过将相同的数字分为一组，原序列a的第i位表示第i组有几个元素，a是Kolakoski序列，b表示第i组的元素个数，根据下图来看 

b[2]=a[2]=2，所以第二组有两个元素，第二组只有一个2，所以a[3]=2，所以b[3]=a[3]=2，所以第三组是两个元素，因为上一组是2，所以第三组是1，所以a[4]，a[5]都是1，也可以发现第奇数组的元素是1，第偶数组的元素是2，所以根据这个规律直接打表

c++

#include
using namespace std;
int a[10000005];
int main()
{a[1]=1;a[2]=a[3]=2;int x=3;bool falg=true;for(int i=3;;i++){if(a[i]==2){if(falg){a[++x]=1;a[++x]=1;falg=!falg;}else{a[++x]=2;a[++x]=2;falg=!falg;}}else{if(falg){a[++x]=1;falg=!falg;}else{a[++x]=2;falg=!falg;}}if(x>10000004)break;}int T;scanf("%d",&T);while(T--){int b;scanf("%d",&b);printf("%d\n",a[b]);}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！