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 閱讀(275)
評論(0) 編輯 收藏 引用 所屬分類:
acm_icpc