test/aoj/1208/main.test.cpp

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1208

Depends on

• Stern-Brocot tree (Mylib/Number/Rational/stern_brocot_tree.cpp)

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1208"

#include <iostream>
#include <utility>
#include "Mylib/Number/Rational/stern_brocot_tree.cpp"

namespace hl = haar_lib;

int main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);

  int p, n;
  while (std::cin >> p >> n, p) {
    std::pair<int, int> lower, upper;
    hl::stern_brocot_tree(
        [p](int64_t pm, int64_t qm) {
          auto a = pm * pm;
          auto b = p * qm * qm;
          if (a < b) return -1;
          if (a > b) return 1;
          return 0;
        },
        n, lower, upper);
    std::cout << upper.first << "/" << upper.second << " "
              << lower.first << "/" << lower.second << "\n";
  }

  return 0;
}

#line 1 "test/aoj/1208/main.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1208"

#include <iostream>
#include <utility>
#line 2 "Mylib/Number/Rational/stern_brocot_tree.cpp"
#include <cstdint>
#line 4 "Mylib/Number/Rational/stern_brocot_tree.cpp"

namespace haar_lib {
  template <typename Checker>
  void stern_brocot_tree(
      const Checker &check,
      int n,
      std::pair<int, int> &lower,
      std::pair<int, int> &upper,
      int64_t pl = 0, int64_t ql = 1, int64_t pr = 1, int64_t qr = 0) {
    int64_t pm = pl + pr;
    int64_t qm = ql + qr;

    if (pm > n or qm > n) return;

    auto t = check(pm, qm);

    if (t < 0) {
      lower = {pm, qm};
      stern_brocot_tree(check, n, lower, upper, pm, qm, pr, qr);
    } else if (t > 0) {
      upper = {pm, qm};
      stern_brocot_tree(check, n, lower, upper, pl, ql, pm, qm);
    } else {
      lower = {pm, qm};
      upper = {pm, qm};
    }
  }
}  // namespace haar_lib
#line 6 "test/aoj/1208/main.test.cpp"

namespace hl = haar_lib;

int main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);

  int p, n;
  while (std::cin >> p >> n, p) {
    std::pair<int, int> lower, upper;
    hl::stern_brocot_tree(
        [p](int64_t pm, int64_t qm) {
          auto a = pm * pm;
          auto b = p * qm * qm;
          if (a < b) return -1;
          if (a > b) return 1;
          return 0;
        },
        n, lower, upper);
    std::cout << upper.first << "/" << upper.second << " "
              << lower.first << "/" << lower.second << "\n";
  }

  return 0;
}

Back to top page