SHARE
TWEET

10077 The Stern-Brocot Number System

Kaidul Jun 17th, 2013 521 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /**
  2.  * Kaidul Islam
  3.  * Khulna University of Engr. & Tech.
  4.  * Rank: 696, Time: 0.015 sec
  5.  **/
  6. #include <iostream>
  7. #include <cstdio>
  8. #include <vector>
  9.  
  10. using namespace std;
  11. vector <int> v;
  12.  
  13. void solve(int nominator, int denominator) {
  14.     if(nominator == 1) return;
  15.     v.push_back(nominator / denominator);
  16.     solve(denominator, nominator % denominator);
  17.  
  18. }
  19.  
  20. int main() {
  21.     int m ,n;
  22.     while(scanf("%d %d", &m, &n)) {
  23.         if(m == 1 && n == 1) break;
  24.         v.clear();
  25.  
  26.         if(m < n) {
  27.             v.push_back(0);
  28.             solve(n, m);
  29.         } else
  30.             solve(m, n);
  31.  
  32.         size_t size = v.size();
  33.         v[size - 1] = v[size - 1] - 1;
  34.  
  35.         for(int i = 0; i < size; i++)
  36.             for(int j = 0; j < v[i]; j++)
  37.                 if(i % 2) printf("L");
  38.                 else printf("R");
  39.  
  40.         printf("\n");
  41.     }
  42.     return 0;
  43. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top