没有通法,没有万金油.
记得partychen说过acm真的很有意思,每一道题都不一样.今天这道题观察出规律后,需要用大数,于是用java写了一遍,TLE,不知道原因,一直交,一直超时,一开始怀疑java的输出不能用Scanner, 改了BufferReader还是超时,最后用C++的大数模板还是超时,却是一直没想到它只要除2,只要减1
1 #include<stdio.h>
2 #include<string.h>
3
4 #define maxlen 2005
5 struct HP {int len,s[maxlen];};
6
7 void PrintHP(HP x){
8 for(int i=x.len;i>=1;i--) printf("%d",x.s[i]);
9 }
10
11 void Str2HP(const char* s ,HP &x)
12 {
13 x.len=strlen(s);
14 for(int i=1;i<=x.len;i++)
15 x.s[i]=s[x.len-i]-'0';
16 }
17
18 void dell(HP & a){
19 int i;
20 for(i = 1; i <= a.len; i++)
21 if(a.s[i]==0)a.s[i] = 9; else break;
22 a.s[i]--;
23 if(a.s[a.len]==0)a.len--;
24 }
25
26
27 bool div2(HP & a){
28 int i; a.s[0] = 0;
29 for(i = a.len; i >= 1; i--)
30 {
31 a.s[i-1] += 10*(a.s[i]%2);
32 a.s[i] /= 2;
33 }
34 if(a.s[a.len]==0)a.len--;
35 return a.s[0]==10;
36 }
37
38
39 char num[maxlen];
40
41 int main(){
42 HP a;
43 int T;
44 for( scanf("%d", &T), getchar(); T > 0; T--){
45 gets(num);
46 gets(num);
47 Str2HP(num,a);
48 if( div2(a) )
49 PrintHP(a);
50 else{
51 HP b = a;
52 if(div2(a) ){
53 dell(b); dell(b);
54 PrintHP(b);
55 }
56 else{
57 dell(b);
58 PrintHP(b);
59 }
60 }
61 printf("\n");
62 if( T > 1)printf("\n");
63 }
64 return 0;
65 }
66
67 /*
68 2
69
70 7
71
72 6
73
74 */
75
posted on 2009-09-10 20:02
wangzhihao 阅读(148)
评论(0) 编辑 收藏 引用 所属分类:
math