Advertisement
mickypinata

USACO-T039: Fractions to Decimals

Dec 17th, 2021
650
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2. ID: mickyta1
  3. TASK: fracdec
  4. LANG: C++
  5. */
  6.  
  7. #include <bits/stdc++.h>
  8. using namespace std;
  9.  
  10. #define f first
  11. #define s second
  12. typedef pair<int, int> pii;
  13.  
  14. const int N = 1e5 + 5;
  15.  
  16. deque<pii> cycle;
  17. vector<pii> noCycle;
  18. string str;
  19. bool visited[N];
  20.  
  21. void printStr(){
  22.     int upb = ((int)str.size() + 75) / 76;
  23.     for(int i = 0; i < upb; ++i){
  24.         for(int j = 0; j < 76 && 76 * i + j < str.size(); ++j){
  25.             cout << str[76 * i + j];
  26.         }
  27.         cout << '\n';
  28.     }
  29. }
  30.  
  31. int main(){
  32.     freopen("fracdec.in", "r", stdin);
  33.     freopen("fracdec.out", "w", stdout);
  34.  
  35.     int st, deno;
  36.     scanf("%d%d", &st, &deno);
  37.     if(st % deno == 0){
  38.         cout << st / deno << ".0\n";
  39.         fclose(stdin);
  40.         fclose(stdout);
  41.         return 0;
  42.     }
  43.     str += to_string(st / deno);
  44.     str.push_back('.');
  45.     st %= deno;
  46.     while(true){
  47.         if(st == 0){
  48.             goto hasNoCycle;
  49.         }
  50.         int u = 10 * st / deno;
  51.         if(visited[st]){
  52.             while(!cycle.empty() && cycle.front().s != st){
  53.                 noCycle.push_back(cycle.front());
  54.                 cycle.pop_front();
  55.             }
  56.             goto hasCycle;
  57.         }
  58.         visited[st] = true;
  59.         cycle.emplace_back(u, st);
  60.         st = 10 * st % deno;
  61.     }
  62. hasNoCycle:
  63.     for(int i = 0; i < cycle.size(); ++i){
  64.         str.push_back((char)(cycle[i].f + '0'));
  65.     }
  66.     printStr();
  67.     fclose(stdin);
  68.     fclose(stdout);
  69.     return 0;
  70. hasCycle:
  71.     for(int i = 0; i < noCycle.size(); ++i){
  72.         str.push_back((char)(noCycle[i].f + '0'));
  73.     }
  74.     str.push_back('(');
  75.     for(int i = 0; i < cycle.size(); ++i){
  76.         str.push_back((char)(cycle[i].f + '0'));
  77.     }
  78.     str.push_back(')');
  79.     printStr();
  80.     fclose(stdin);
  81.     fclose(stdout);
  82.     return 0;
  83. }
  84.  
Advertisement
RAW Paste Data Copied
Advertisement