http://acm.cs.bupt.cn/onlinejudge/showproblem.php?problem_id=1379
給一個(gè)長(zhǎng)度10MB的大數(shù)n,要求計(jì)算ceil(n/2),內(nèi)存只有1000K,顯然不能開(kāi)數(shù)組,要邊讀邊除
通常的除法只要設(shè)個(gè)變量記錄每位是否整除(mod).此外題目要求不輸出前導(dǎo)0,再設(shè)個(gè)bool值記錄(zero)
特殊之處在于向上取整.舉個(gè)例子:1999/2=1000,顯然直接除一位輸出一位有問(wèn)題
關(guān)鍵之處在于增加一個(gè)變量記錄連續(xù)的9的個(gè)數(shù)(cnt9).如果處理到非9的位,或者輸入文件結(jié)束,就分情況輸出前面最近一位非9數(shù)除的結(jié)果,然后循環(huán)輸出9除的結(jié)果.因此,還要一個(gè)變量記錄上一位除得的商(co)
1 /*
2 記錄連續(xù)9的個(gè)數(shù),為了使輸入末尾有連續(xù)9時(shí)向上取整
3 co記錄上位除的商
4 mod記錄上位除的余數(shù)
5 cnt9記錄連續(xù)的9的個(gè)數(shù)
6 zero記錄前導(dǎo)是否為0
7 當(dāng)前位不是9時(shí),輸出之前的結(jié)果,并將當(dāng)前位+mod*5存入co
8 當(dāng)前位是9時(shí),cnt9++
9 輸入結(jié)束時(shí),處理末尾幾位
10 注意:
11 輸入為0時(shí)
12 以9開(kāi)頭時(shí)
13 以x9開(kāi)頭時(shí)
14
15 幾組數(shù)據(jù):
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 閱讀(280)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
acm_icpc