LightOJ - 1138 - Trailing Zeroes (III)

1. /****************#####    بِسْمِ اللَّهِ الرَّحْمَنِ الرَّحِيم   #####******************
2. __________________________________________________________________________
3. ######################  Ya-Seen Arafat(ACWizard) #########################
4. ######################        UAP-CSE-33B        #########################
5. *************************************************************************/
6. #include <bits/stdc++.h>
7. #define M 1000003
8. #define S 1000003
9. #define LL long long
10. using namespace std;
11.  
12. int n;
13.  
14. int BS(int h, int l){
15.     int p, q, m, f = 0;
16.     while(h >= l){
17.         p = h+l;
18.         if(p&1)p += 5;
19.         m = p/2;
20.         q = m;
21.         if(f == m)return -1;
22.         f = m;
23.         int ans = 0;
24.         while(q > 0){
25.             ans += q/5;
26.             q /= 5;
27.         }
28.         if(ans == n)return m;
29.         else if(ans > n)h = m;
30.         else l = m;
31.     }
32.     return -1;
33. }
34.  
35. int main(){
36.     int t, cs = 0;
37.     scanf("%d", &t);
38.     while(t--){
39.         scanf("%d", &n);
40.         int high = 5*n;
41.         int low = 5;
42.         int a = BS(high, low);
43.         printf("Case %d: ", ++cs);
44.         printf((a < 0)?"impossible\n":"%d\n", a);
45.     }
46.     return 0;
47. }

LightOJ - 1090 - Trailing Zeroes (II)

1. /****************#####    بِسْمِ اللَّهِ الرَّحْمَنِ الرَّحِيم   #####******************
2. __________________________________________________________________________
3. ######################  Ya-Seen Arafat(ACWizard) #########################
4. ######################        UAP-CSE-33B        #########################
5. *************************************************************************/
6. #include <bits/stdc++.h>
7. #define M 1000003
8. #define S 1000003
9. #define LL long long
10. using namespace std;
11.  
12. int find_p(int a, int b){
13.     int cn = 0;
14.     while(a > 0){
15.         cn += (a/b);
16.         a /= b;
17.     }
18.     return cn;
19. }
20.  
21. int find_pr(int a, int b){
22.     int cn = 0;
23.     while(!(a%b)){
24.         cn++;
25.         a /= b;
26.     }
27.     return cn;
28. }
29.  
30. int main(){
31.     int t, n, r, p, q, c, cs = 0;
32.     scanf("%d", &t);
33.     while(t--){
34.         scanf("%d %d %d %d", &n, &r, &p, &q);
35.         c = n-r;
36.         int five_up = 0, five_down = 0, two_up = 0, two_down = 0;
37.  
38.         five_up = find_p(n, 5);
39.         two_up = find_p(n, 2);
40.         five_down = find_p(c, 5);
41.         five_down += find_p(r, 5);
42.         two_down = find_p(c, 2);
43.         two_down += find_p(r, 2);
44.  
45.         five_up += (q*find_pr(p, 5));
46.         two_up += (q*find_pr(p, 2));
47.  
48.         int five, two;
49.         five = five_up-five_down;
50.         two = two_up-two_down;
51.         int ans = min(five, two);
52.         printf("Case %d: %d\n", ++cs, ans);
53.     }
54.     return 0;
55. }