読者です 読者をやめる 読者になる 読者になる

UVa11350 Stern-Brocot Tree

問題
http://uva.onlinejudge.org/external/113/11350.html

概要
走査の方向 'L' または 'R' が書かれるので、Stern-Brocot Tree を親ノードから辿れ。

解法
左と右の数字の和を取って木を走査していく。二分探索木である。
図を見ながらコードで確認した方が分かりやすい。


Cite from Wikipedia

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

void TraverseSternBrocotTree(string &traverser, int depth, int limit,
                             ll pl = 0, ll ql = 1,
                             ll pr = 1, ll qr = 0) {
  ll pm = pl + pr, qm = ql + qr;
  
  if(depth == limit) {
    cout << pm << "/" << qm << endl;
    return ;
  }
  
  if(traverser[depth] == 'L')
    TraverseSternBrocotTree(traverser, depth+1, limit, pl, ql, pm, qm);
  else
    TraverseSternBrocotTree(traverser, depth+1, limit, pm, qm, pr, qr);
}

int main() {
  
  int Tc;
  cin >> Tc;
  while(Tc--) {
    string s; cin >> s;
    TraverseSternBrocotTree(s, 0, s.size());
  }
  
  return 0;
}