POJ 1930

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <iostream>
 5 
 6 using namespace std;
 7 
 8 typedef long long ll;
 9 
10 char s[20];
11 ll ten_pow[20];
12 
13 ll gcd(ll x,ll y) {
14         return y > 0 ? gcd(y,x % y) : x;
15 }
16 
17 void init() {
18         ten_pow[0] = 1;
19         for(int i = 1; i <= 9; i++) {
20                 ten_pow[i] = ten_pow[i - 1] * 10;
21         }
22 
23         /*for(int i = 0; i <= 9; i++){
24                 printf("%lld\n",ten_pow[i]);
25 
26         }*/
27 }
28 void solve() {
29 
30         ll a,b,aa,bb;
31         ll ans1,ans2 = -1;
32         for(int i = 0; i < strlen(s) - 2; i++) {
33                     b = 0; bb = 0;
34                     for(int j = 2; j < 2 + i; j++) {
35                             b += (s[j] - ‘0‘) * ten_pow[1 + i - j];
36                     }
37                     for(int j = 2 + i; j < strlen(s); j++){
38                             bb += (s[j] - ‘0‘) * ten_pow[strlen(s) - 1 - j];
39                     }
40 
41 
42                     a = ten_pow[i];
43                     aa = ten_pow[strlen(s) - 2] - ten_pow[i];
44                    // printf("b =%lld bb=%lld a = %lld aa = %lld\n",b,bb,a,aa);
45 
46                     b = b * aa + bb * a;
47                     a *= aa;
48 
49                     ll t = gcd(a,b);
50                     b /= t;
51                     a /= t;
52 
53                     //printf("a = %lld b = %lld\n",a,b);
54                     if(ans2 == -1 || ans2 > a) {
55                             ans2 = a;
56                             ans1 = b;
57                     }
58 
59 
60         }
61 
62         printf("%I64d/%I64d\n",ans1,ans2);
63 
64 
65 
66 }
67 
68 int main() {
69         init();
70        // freopen("sw.in","r",stdin);
71 
72         while(~scanf("%s",s) && strlen(s) != 1) {
73 
74 
75                 int pos = strlen(s) - 1;
76                 while(s[pos] == ‘.‘) {
77                         s[pos--] = ‘\0‘;
78                 }
79 
80                 bool flag = 0;
81                 for(int i = 2; i < strlen(s); i++) {
82                         if(s[i] != ‘0‘ ) flag = 1;
83 
84                 }
85 
86                 //puts(s);
87 
88                 if(!flag) {
89                         printf("0/1\n");
90                         continue;
91                 }
92 
93                 solve();
94 
95         }
96 
97         return 0;
98 }