杰哥私房题──细菌繁殖

问题描述
一种细菌的繁殖速度是每天成倍增长。例如：第一天有10 个，第二天就变成20 个，
第三天变成40 个，第四天变成80 个，……。现在给出第一天的日期和细菌数目，要你
写程序求出到某一天的时候，细菌的数目。
输入数据
第一行有一个整数n，表示测试数据的数目。其后n 行每行有5 个整数，整数之间
用一个空格隔开。第一个数表示第一天的月份，第二个数表示第一天的日期，第三个数
表示第一天细菌的数目，第四个数表示要求的那一天的月份，第五个数表示要求的那一
天的日期。已知第一天和要求的一天在同一年并且该年不是闰年，要求的一天一定在第
一天之后。数据保证要求的一天的细菌数目在整数范围内。
输出要求
对于每一组测试数据，输出一行，该行包含一个整数，为要求的一天的细菌数。
输入样例
2
1 1 1 1 2
2 28 10 3 2
输出样例
2
40

#include <stdio.h>
int main(){
	int nCases;
	int monthDay[] = {31,30,31,30,31,30,31,31,30,31,30, 31};
	scanf("%d", &nCases);
	while(nCases--){
		int aMonth, aDay, bMonth, bDay, bacteria;
		scanf("%d %d %d %d %d", &aMonth, &aDay, &bMonth, &bDay, &bacteria);
		int days = 0;
		int j;
		for(j = aMonth; j < bMonth; j++){
			days += monthDay[j - 1];
		}
		days -= aDay;
		days += bDay;
		unsigned int total = bacteria;
		for(j = 0; j < days; j++){
			total *= 2;
		}
		printf("%d\n", total);
	}
	return 0;
}

 

评论

9 楼 netalpha 2009-03-06  

leeldy 写道

netalpha 写道

leeldy 写道

如果是ACM题目，一、LZ的算法肯定超时二、LZ的算法肯定会出现ErrorAnswer考虑极端情况，起始日期是1.1，终止日期是12.31，没有闰年，天数就是364天2的364次方肯定不能用int来保存我的算法：日期相差天数n开始有细菌数s那么到了那天一共有细菌数目是s*(2<<n)数据巨大，需要使用BigDecimal来保存和输出

谢谢你的分析。
对于你所说的问题，首先，你说认为会超时的原因是细菌繁殖的计算吧？我认为即使计算365次也不会超时，这里我用无符号int的范围确实小了点，我不清楚有没有unsigned long，如果有的话到可以用，但是BigDecimal是java的东西，C里面好像没有吧。

用C的话就考虑用数组吧，这样需要不少时间
Long也只有64位二进制，要保存364位的二进制数，你还是采用数组吧
正规的ACM题目的测试数据肯定不会只有1组。。。
一般测试数据都是用txt文件保存，测试的时候读取
我见过的txt测试数据一般都有几M，至于有多少组我就不知道了

呵呵  恩  在过3天我就会就大数问题出几个题目讨论讨论。

8 楼 leeldy 2009-03-06  

netalpha 写道

leeldy 写道

如果是ACM题目，一、LZ的算法肯定超时二、LZ的算法肯定会出现ErrorAnswer考虑极端情况，起始日期是1.1，终止日期是12.31，没有闰年，天数就是364天2的364次方肯定不能用int来保存我的算法：日期相差天数n开始有细菌数s那么到了那天一共有细菌数目是s*(2<<n)数据巨大，需要使用BigDecimal来保存和输出

谢谢你的分析。
对于你所说的问题，首先，你说认为会超时的原因是细菌繁殖的计算吧？我认为即使计算365次也不会超时，这里我用无符号int的范围确实小了点，我不清楚有没有unsigned long，如果有的话到可以用，但是BigDecimal是java的东西，C里面好像没有吧。

用C的话就考虑用数组吧，这样需要不少时间
Long也只有64位二进制，要保存364位的二进制数，你还是采用数组吧
正规的ACM题目的测试数据肯定不会只有1组。。。
一般测试数据都是用txt文件保存，测试的时候读取
我见过的txt测试数据一般都有几M，至于有多少组我就不知道了

7 楼 netalpha 2009-03-05  

ray_linn 写道

这个不用看都知道。。没有两把刷子你能存下天文数字？投一个隐藏

以后我会有个章节处理大数问题的，到时候讨论啦。呵呵

6 楼 ray_linn 2009-03-04  

这个不用看都知道。。没有两把刷子你能存下天文数字？投一个隐藏

5 楼 agapple 2009-03-04  

晕，如果ACM这么简单循环算，那还搞个P

4 楼 netalpha 2009-03-04  

leeldy 写道

如果是ACM题目，一、LZ的算法肯定超时二、LZ的算法肯定会出现ErrorAnswer考虑极端情况，起始日期是1.1，终止日期是12.31，没有闰年，天数就是364天2的364次方肯定不能用int来保存我的算法：日期相差天数n开始有细菌数s那么到了那天一共有细菌数目是s*(2<<n)数据巨大，需要使用BigDecimal来保存和输出

谢谢你的分析。
对于你所说的问题，首先，你说认为会超时的原因是细菌繁殖的计算吧？我认为即使计算365次也不会超时，这里我用无符号int的范围确实小了点，我不清楚有没有unsigned long，如果有的话到可以用，但是BigDecimal是java的东西，C里面好像没有吧。

3 楼 leeldy 2009-03-04  

如果是ACM题目，
一、LZ的算法肯定超时
二、LZ的算法肯定会出现ErrorAnswer

考虑极端情况，起始日期是1.1，终止日期是12.31，没有闰年，天数就是364天
2的364次方肯定不能用int来保存

我的算法：
日期相差天数n
开始有细菌数s
那么到了那天一共有细菌数目是s*(2<<n)
数据巨大，需要使用BigDecimal来保存和输出

2 楼 netalpha 2009-03-04  

xiaoyuerbaby 写道

发错地方了吧 这是java板块啊

语言的东西是不分java和c的，他在于的是你的逻辑性~~

1 楼 xiaoyuerbaby 2009-03-04  

发错地方了吧 这是java板块啊