test/aoj/0350.test.cpp

• View this file on GitHub
• Last update: 2024-09-01 10:56:39+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Final/0350

Depends on

• Binary GCD (src/Math/binary_gcd.hpp)
• 有理数 $\mathbb{Q}$ (src/Math/Rational.hpp)

Code

// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Final/0350
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include <string>
#include "src/Math/Rational.hpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 using Q= Rational<long long>;
 string str;
 cin >> str;
 if (str.back() != ')') str+= "(0)";
 int pw[12]= {1};
 for (int i= 0; i < 11; ++i) pw[i + 1]= pw[i] * 10;
 int p= str.find('.'), q= str.find('(');
 string a= str.substr(0, p);
 string b= str.substr(p + 1, q - p - 1);
 string c= str.substr(q + 1, str.size() - q - 2);
 int n= b.length();
 Q ans= stoi(a);
 if (n) ans+= Q(stoi(b), pw[n]);
 ans+= Q(stoi(c), pw[n] * (pw[c.length()] - 1));
 cout << ans.num << "/" << ans.den << '\n';
 return 0;
}

#line 1 "test/aoj/0350.test.cpp"
// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Final/0350
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include <string>
#line 3 "src/Math/Rational.hpp"
#include <limits>
#include <sstream>
#line 2 "src/Math/binary_gcd.hpp"
#include <type_traits>
#include <algorithm>
#include <cstdint>
template <class Int> constexpr int bsf(Int a) {
 if constexpr (sizeof(Int) == 16) {
  uint64_t lo= a & uint64_t(-1);
  return lo ? __builtin_ctzll(lo) : 64 + __builtin_ctzll(a >> 64);
 } else if constexpr (sizeof(Int) == 8) return __builtin_ctzll(a);
 else return __builtin_ctz(a);
}
template <class Int> constexpr Int binary_gcd(Int a, Int b) {
 if (a == 0 || b == 0) return a + b;
 int n= bsf(a), m= bsf(b), s= 0;
 for (a>>= n, b>>= m; a != b;) {
  Int d= a - b;
  bool f= a > b;
  s= bsf(d), b= f ? b : a, a= (f ? d : -d) >> s;
 }
 return a << std::min(n, m);
}
#line 6 "src/Math/Rational.hpp"
template <class Int, bool reduction= true> struct Rational {
 Int num, den;
 constexpr Rational(): num(0), den(1) {}
 constexpr Rational(Int n, Int d= 1): num(n), den(d) {
  if (den < 0) num= -num, den= -den;
  if constexpr (reduction) reduce(num, den);
 }
 constexpr Rational(const std::string &str) {
  auto it= str.find("/");
  if (it == std::string::npos) num= std::stoi(str), den= 1;
  else num= std::stoi(str.substr(0, it)), den= std::stoi(str.substr(it + 1));
  if constexpr (reduction) reduce(num, den);
 }
 static constexpr void reduce(Int &a, Int &b) {
  const Int g= binary_gcd(a < 0 ? -a : a, b);
  a/= g, b/= g;
 }
 static constexpr Rational raw(Int n, Int d) {
  Rational ret;
  return ret.num= n, ret.den= d, ret;
 }
 constexpr Rational operator-() const { return raw(-num, den); }
 constexpr Rational operator+(const Rational &r) const { return Rational(num * r.den + den * r.num, den * r.den); }
 constexpr Rational operator-(const Rational &r) const { return Rational(num * r.den - den * r.num, den * r.den); }
 constexpr Rational operator*(const Rational &r) const {
  if constexpr (reduction) {
   Int ln= num, ld= den, rn= r.num, rd= r.den;
   return reduce(ln, rd), reduce(rn, ld), raw(ln * rn, ld * rd);
  } else return Rational(num * r.num, den * r.den);
 }
 constexpr Rational operator/(const Rational &r) const {
  if constexpr (reduction) {
   Int ln= num, ld= den, rn= r.num, rd= r.den;
   if (rn < 0) rd= -rd, rn= -rn;
   return reduce(ln, rn), reduce(rd, ld), raw(ln * rd, ld * rn);
  } else return Rational(num * r.den, den * r.num);
 }
 Rational &operator+=(const Rational &r) { return *this= *this + r; }
 Rational &operator-=(const Rational &r) { return *this= *this - r; }
 Rational &operator*=(const Rational &r) { return *this= *this * r; }
 Rational &operator/=(const Rational &r) { return *this= *this / r; }
 constexpr bool operator==(const Rational &r) const {
  if constexpr (reduction) return num == r.num && den == r.den;
  else return den == 0 && r.den == 0 ? num * r.num > 0 : num * r.den == den * r.num;
 }
 constexpr bool operator!=(const Rational &r) const { return !(*this == r); }
 constexpr bool operator<(const Rational &r) const {
  if (den == 0 && r.den == 0) return num < r.num;
  else if (den == 0) return num < 0;
  else if (r.den == 0) return r.num > 0;
  else return num * r.den < den * r.num;
 }
 constexpr bool operator>(const Rational &r) const { return r < *this; }
 constexpr bool operator<=(const Rational &r) const { return !(r < *this); }
 constexpr bool operator>=(const Rational &r) const { return !(*this < r); }
 constexpr explicit operator bool() const { return num != 0; }
 constexpr long double to_fp() const { return (long double)num / den; }
 constexpr explicit operator long double() const { return to_fp(); }
 constexpr explicit operator double() const { return to_fp(); }
 constexpr explicit operator float() const { return to_fp(); }
 constexpr Int floor() const { return num < 0 ? -((-num + den - 1) / den) : num / den; }
 constexpr Int ceil() const { return num < 0 ? -(-num / den) : (num + den - 1) / den; }
 constexpr Rational abs() const { return raw(num < 0 ? -num : num, den); }
 constexpr friend Int floor(const Rational &r) { return r.floor(); }
 constexpr friend Int ceil(const Rational &r) { return r.ceil(); }
 constexpr friend Rational abs(const Rational &r) { return r.abs(); }
 std::string to_string() const {
  if (!num) return "0";
  std::stringstream ss;
  if (den == 1) return ss << num, ss.str();
  return ss << num << "/" << den, ss.str();
 }
 friend std::istream &operator>>(std::istream &is, Rational &r) {
  std::string s;
  if (is >> s; s != "") r= Rational(s);
  return is;
 }
 friend std::ostream &operator<<(std::ostream &os, const Rational &r) { return os << r.to_string(); }
};
template <class Int, bool reduction> struct std::numeric_limits<Rational<Int, reduction>> {
 static constexpr Rational<Int, reduction> max() noexcept { return Rational<Int, reduction>(1, 0); }
 static constexpr Rational<Int, reduction> min() noexcept { return Rational<Int, reduction>(1, std::numeric_limits<Int>::max()); }
 static constexpr Rational<Int, reduction> lowest() noexcept { return Rational<Int, reduction>(-1, 0); }
};
#line 7 "test/aoj/0350.test.cpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 using Q= Rational<long long>;
 string str;
 cin >> str;
 if (str.back() != ')') str+= "(0)";
 int pw[12]= {1};
 for (int i= 0; i < 11; ++i) pw[i + 1]= pw[i] * 10;
 int p= str.find('.'), q= str.find('(');
 string a= str.substr(0, p);
 string b= str.substr(p + 1, q - p - 1);
 string c= str.substr(q + 1, str.size() - q - 2);
 int n= b.length();
 Q ans= stoi(a);
 if (n) ans+= Q(stoi(b), pw[n]);
 ans+= Q(stoi(c), pw[n] * (pw[c.length()] - 1));
 cout << ans.num << "/" << ans.den << '\n';
 return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-13	00_sample01.in	AC	5 ms	4 MB
g++-13	00_sample02.in	AC	4 ms	4 MB
g++-13	00_sample03.in	AC	4 ms	4 MB
g++-13	00_sample04.in	AC	4 ms	4 MB
g++-13	10_min01.in	AC	4 ms	4 MB
g++-13	10_min02.in	AC	4 ms	4 MB
g++-13	20_max01.in	AC	4 ms	4 MB
g++-13	20_max02.in	AC	4 ms	4 MB
g++-13	30_cycle01.in	AC	4 ms	4 MB
g++-13	30_cycle02.in	AC	4 ms	4 MB
g++-13	40_cancel01.in	AC	4 ms	4 MB
g++-13	40_cancel02.in	AC	4 ms	4 MB
g++-13	50_random01.in	AC	4 ms	4 MB
g++-13	50_random02.in	AC	4 ms	4 MB
g++-13	50_random03.in	AC	4 ms	4 MB
clang++-18	00_sample01.in	AC	5 ms	4 MB
clang++-18	00_sample02.in	AC	4 ms	4 MB
clang++-18	00_sample03.in	AC	4 ms	4 MB
clang++-18	00_sample04.in	AC	4 ms	4 MB
clang++-18	10_min01.in	AC	4 ms	4 MB
clang++-18	10_min02.in	AC	4 ms	4 MB
clang++-18	20_max01.in	AC	4 ms	4 MB
clang++-18	20_max02.in	AC	4 ms	4 MB
clang++-18	30_cycle01.in	AC	4 ms	4 MB
clang++-18	30_cycle02.in	AC	4 ms	4 MB
clang++-18	40_cancel01.in	AC	4 ms	4 MB
clang++-18	40_cancel02.in	AC	4 ms	4 MB
clang++-18	50_random01.in	AC	4 ms	4 MB
clang++-18	50_random02.in	AC	4 ms	4 MB
clang++-18	50_random03.in	AC	4 ms	4 MB

Back to top page