Kolakoski

Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 878????Accepted Submission(s): 497


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? n th 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 ? ?題意： 給定值一個數n，求第n個 Kolakoski序列的值。如不了解請點擊這里
思路：我們不難發現，第二列序列的每位的數值，與其所在的位置的奇偶有關。可以圍繞這點解決問題。 源代碼： #include<cstdio> #include<cstring> const int M=1e7+7; using namespace std; int a[M]; int main() {a[1]=1;a[2]=2;int n=2;for(int i=2;i<M;){int num=a[n++];//記錄第二列第n位序列長度if(n&1){for(int j=1;j<=num;j++)a[i++]=2;}else{for(int j=1;j<=num;j++)a[i++]=1;}}int t;scanf("%d",&t);while(t--){int c;scanf("%d",&c);printf("%d\n",a[c]);}return 0; }

總結

以上是生活随笔為你收集整理的HDU 613 Kolakoski的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。