ismaeil

A Rational Sequence

May 12th, 2021
653
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. using namespace std;
  4.  
  5. typedef pair<ll , ll> pll;
  6. #define S second
  7. #define F first
  8.  
  9. inline pll getLeft(pll a)
  10. {
  11.     return pll(a.F ,a.F + a.S);
  12. }
  13.  
  14. inline pll getRight(pll a)
  15. {
  16.     return pll(a.F + a.S ,a.S);
  17. }
  18.  
  19. inline pll getFather(pll a)
  20. {
  21.     return a.S > a.F ? pll(a.F ,a.S - a.F) : pll(a.F - a.S ,a.S);
  22. }
  23.  
  24. pll getNext(pll cur)
  25. {
  26.     pll last = cur;
  27.     cur = getFather(cur);
  28.    
  29.     int cnt = 0;
  30.     while( last == getRight(cur) )
  31.     {
  32.         cnt += 1;
  33.         last = cur;
  34.         cur = getFather(cur);
  35.     }
  36.    
  37.     cur = getRight(cur);
  38.     while( cnt )
  39.     {
  40.         cnt -= 1;
  41.         cur = getLeft(cur);
  42.     }
  43.    
  44.     return cur;
  45. }
  46.  
  47. void Solve()
  48. {
  49.     ll k;
  50.     cin >> k;
  51.     cout << k << ' ';
  52.    
  53.     string buffer;
  54.     cin >> buffer;
  55.     for(char &i : buffer)
  56.     {
  57.         if( i == '/' )
  58.         {
  59.             i = ' ';
  60.             break;
  61.         }
  62.     }
  63.    
  64.     pll cur;
  65.     stringstream st(buffer);
  66.     st >> cur.F >> cur.S;
  67.    
  68.     if( !cur.F || !cur.S )
  69.     {
  70.         cout << 1 << '/' << 1 << endl;
  71.         return;
  72.     }
  73.    
  74.     if( cur.S == 1 )
  75.     {
  76.         cout << 1 << '/' << cur.F + cur.S << endl;
  77.         return;
  78.     }
  79.    
  80.     pll nxt = getNext(cur);
  81.     cout << nxt.F << '/' << nxt.S << endl;
  82. }
  83.  
  84. int main()
  85. {
  86.     int Tc;
  87.     cin >> Tc;
  88.    
  89.     while( Tc-- ) Solve();
  90.     return 0;
  91. }
  92.  
RAW Paste Data