机器人繁殖

标题:机器人繁殖

X星系的机器人可以自动复制自己。它们用1年的时间可以复制出2个自己,然后就失去复制能力。
每年X星系都会选出1个新出生的机器人发往太空。也就是说,如果X星系原有机器人5个,
1年后总数是:5 + 9 = 14
2年后总数是:5 + 9 + 17 = 31

如果已经探测经过n年后的机器人总数s,你能算出最初有多少机器人吗?

数据格式:

输入一行两个数字n和s,用空格分开,含义如上。n不大于100,s位数不超过50位。

要求输出一行,一个整数,表示最初有机器人多少个。

例如:
用户输入:
2 31

则程序应该输出:
5

再例如:
用户输入:
97 2218388550399401452619230609499

则程序应该输出:
8

资源约定:
峰值内存消耗 < 512M
CPU消耗 < 1000ms
请严格按要求输出,不要画蛇添足地打印类似:“请您输入…” 的多余内容。

所有代码放在同一个源文件中,调试通过后,拷贝提交该源码。

注意: main函数需要返回0
注意: 只使用ANSI C/ANSI C++ 标准,不要调用依赖于编译环境或操作系统的特殊函数。
注意: 所有依赖的函数必须明确地在源文件中 #include <xxx>, 不能通过工程设置而省略常用头文件。

提交时,注意选择所期望的编译器类型。

 

思路:

关键是找规律推算出求和公式,不难得出,若第一年有i个机器人,则每一年的机器人数分别为:

i, 2*i-1 , 4*i-3 , 8*i-7 , 16*i-15…….

变一下形式即:

2^0(i-1)+1 , 2^1(i-1)+1 , 2^2(i-1)+1……

可以发现是一个等比数列,通项公式为:2^(n-1)*(i-1)+1

用求和公式可以得出,第n年的总数为(i-1)(2^n-1)+n

那么n年后的总数其实就是第n+1年的总数,所以最后的公式为:(i-1)(2^(n+1)-1)+n+1

有了公式后,剩下的问题就是数据貌似很大,最多可以有50位,这种情况下,直接比较n年后的总数和输入的是否相等必然很困难,用高精度计算肯定可以,但是也很麻烦。所以可以退而求其次,不比较两个数是否全部相等,只比较末尾的8位是否相等。这样写可以避免数据太大,同时也有着相当高的正确率:即使有那种只比较后8位仍不能确定唯一解的情况,那也是少数中的少数,最起码可以保证拿到题目80%的分数。

代码:

#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int main(){
	int n,total_end=0;
	char s[55];
	scanf("%d%s",&n,s);
	//将后8位转换为int 
	for(int i=strlen(s)-(strlen(s)>=8?8:strlen(s));i<strlen(s);i++)
		total_end=total_end+(s[i]-'0')*(int)(pow(10,strlen(s)-i-1)+0.5);
	//printf("%d\n",total_end);
	for(int i=2; ;i++){
		//求和公式:(i-1)(2^(n+1)-1)+n+1
		int s=0,i_pow2=1;
		for(int j=1;j<=n+1;j++)
			i_pow2=(i_pow2*2)%1000000000;//2^(n+1)
		i_pow2=i_pow2-1;//(pow(2,n+1)-1) 
		for(int j=1;j<i;j++)
		    s=(s+i_pow2)%1000000000;//(i-1)*(2^(n+1)-1)	
		s=(s+n+1)%100000000;//(i-1)(2^(n+1)-1)+n+1
		//printf("%d %d\n",i,s);
		if(s==total_end){
			printf("%d\n",i);
			break;
		}
	} 	
	return 0;
}
2016年5月10日 | 归档于 Uncategorized
标签:
本文的评论功能被关闭了.