http://acm.cs.bupt.cn/onlinejudge/showproblem.php?problem_id=1379
给一个长度10MB的大数n,要求计算ceil(n/2),内存只有1000K,显然不能开数组,要边读边除
通常的除法只要设个变量记录每位是否整除(mod).此外题目要求不输出前导0,再设个bool值记录(zero)
特殊之处在于向上取整.举个例子:1999/2=1000,显然直接除一位输出一位有问题
关键之处在于增加一个变量记录连续的9的个数(cnt9).如果处理到非9的位,或者输入文件结束,就分情况输出前面最近一位非9数除的结果,然后循环输出9除的结果.因此,还要一个变量记录上一位除得的商(co)
1 /*
2 记录连续9的个数,为了使输入末尾有连续9时向上取整
3 co记录上位除的商
4 mod记录上位除的余数
5 cnt9记录连续的9的个数
6 zero记录前导是否为0
7 当前位不是9时,输出之前的结果,并将当前位+mod*5存入co
8 当前位是9时,cnt9++
9 输入结束时,处理末尾几位
10 注意:
11 输入为0时
12 以9开头时
13 以x9开头时
14
15 几组数据:
16 000319900099 159950050
17 199 100
18 0199 100
19 1998 999
20 99 50
21 0 0
22 */
23 #include <iostream>
24 using namespace std;
25 int main(){
26 bool zero;
27 int mod,cnt9;
28 char co,cn,ct;
29 zero=true; mod=0; co=0; cnt9=0;
30 while(isdigit(cn=getchar())){
31 cn-='0';
32 if(cn!=9){
33 if(!zero||co){
34 zero=false;
35 putchar(co+'0');
36 }
37 if(cnt9)zero=false;
38 while(cnt9--){
39 putchar(4+5*mod+'0');
40 mod=1;
41 }
42 cnt9=0;
43 co=(cn>>1)+5*mod;
44 mod=cn&1;
45 }
46 else{
47 cnt9++;
48 }
49 }
50 if(!zero||co||mod){
51 zero=false;
52 putchar(co+mod+'0');
53 }
54 mod=1-mod;
55 if(cnt9)zero=false;
56 while(cnt9--){
57 putchar(5*mod+'0');
58 mod=0;
59 }
60 //输入0的情况!
61 if(zero)putchar('0');
62 putchar('\n');
63 return 0;
64 }
65
posted on 2009-03-25 22:52
wolf5x 阅读(258)
评论(0) 编辑 收藏 引用 所属分类:
acm_icpc