首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 服务器 > 云计算 >

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

2012-11-23 
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;
}

热点排行