codeforces 俄罗斯季度决赛标题sequence解答

codeforces 俄罗斯季度决赛题目sequence解答
原题大意如下：
用两种操作产生数字序列：加倍和数字排序。数字排序就是升序方式排列数字，如数值6532，排列后的结果是2356。
序列都是从1开始，序列前15个数值时1 2 4 8 16 23 46 29 58 116 223 446 289 578 1156。
请编程算出第n个序列中的数值是什么。
1<=n<=2147483647


分析：由于n的上界很大，如果逐一计算，一定不现实。因为它涉及大数据加法和超大数组存储。算法相当麻烦！因而这个思路可以排除。
同时，这种操作明显是无规律可循的，因此找规律的方法也排除了。
既然有这道题目，说明一定是可以解答的！
思考一下，容易想到，当数大到一定程度，序列中的数会出现0，也就是说数值可以降低一个数量级！于是猜想，是不是到达某值后，序列中的数就不在增长。即存在循环。
于是证明一下，果然！这样算法的时间和空间消耗都很小了。

附程序如下：

#include <stdio.h>


int main()
{
int i, j, k, n, c, tmp, flag, bits, count, nn;
int num[20] = {0, 1, 0};
int nums[35] = {0, 1, 0};

//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
 
scanf("%d", &n);
nn = n < 31? n : 30;
for(i = 2; i <= nn; i++){
for(flag = 0, c = 0, j = 1; num[j] != 0; j++){
tmp = num[j] * 2 + c;
c = tmp / 10;
num[j] = tmp % 10;
if(j > 1 && num[j] > num[j - 1]){
flag = 1;
}
}

if(c > 0)
num[j] = c;
else
j--;

bits = j;
if(flag){
for(j = 1; j < bits; j++){
for(k = 2; k <= bits; k++){
if(num[k] > num[k - 1]){
tmp = num[k];
num[k] = num[k - 1];
num[k - 1] = tmp;
}
}
}

for(count = 0, j = 1; j <= bits; j++){
if(num[j] == 0){
count++;
}else{
break;
}
}

for(j = 1; j < bits; j++){
num[j] = num[j + count];
}
bits -= count;
}

for(tmp = 0, k = bits; k > 0; k--){
tmp = tmp * 10 + num[k];
}
nums[i] = tmp;
}


if(n > 30)
n = (n - 25) % 6 + 25;
printf("%d\n", nums[n]);


return 0;
}