test/yukicoder/1501.test.cpp

• View this file on GitHub
• Last update: 2024-09-01 13:40:30+09:00
• Problem: https://yukicoder.me/problems/no/1501

Depends on

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

Code

// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/1501
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include "src/Math/Rational.hpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 using Q= Rational<long long>;
 int N, K;
 cin >> N >> K;
 int A[N];
 for (int i= 0; i < N; ++i) cin >> A[i];
 if (N == 1) return cout << "1/1" << '\n', 0;
 Q d= 0, n= 0;
 for (int i= 0; i < N - 1; ++i) {
  d+= Q(1, A[i] * A[i + 1]);
  if (i == K - 2) n= d;
 }
 Q ans= n / d;
 if (ans == 0) cout << 0 << '\n';
 else cout << ans.num << "/" << ans.den << '\n';
 return 0;
}

#line 1 "test/yukicoder/1501.test.cpp"
// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/1501
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#line 2 "src/Math/Rational.hpp"
#include <string>
#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 6 "test/yukicoder/1501.test.cpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 using Q= Rational<long long>;
 int N, K;
 cin >> N >> K;
 int A[N];
 for (int i= 0; i < N; ++i) cin >> A[i];
 if (N == 1) return cout << "1/1" << '\n', 0;
 Q d= 0, n= 0;
 for (int i= 0; i < N - 1; ++i) {
  d+= Q(1, A[i] * A[i + 1]);
  if (i == K - 2) n= d;
 }
 Q ans= n / d;
 if (ans == 0) cout << 0 << '\n';
 else cout << ans.num << "/" << ans.den << '\n';
 return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-13	sample01.txt	AC	7 ms	4 MB
g++-13	sample02.txt	AC	6 ms	4 MB
g++-13	sample03.txt	AC	6 ms	4 MB
g++-13	test01.txt	AC	6 ms	4 MB
g++-13	test02.txt	AC	6 ms	4 MB
g++-13	test03.txt	AC	13 ms	4 MB
g++-13	test04.txt	AC	11 ms	4 MB
g++-13	test05.txt	AC	12 ms	4 MB
g++-13	test06.txt	AC	7 ms	4 MB
g++-13	test07.txt	AC	11 ms	4 MB
g++-13	test08.txt	AC	8 ms	4 MB
g++-13	test09.txt	AC	11 ms	4 MB
g++-13	test10.txt	AC	9 ms	4 MB
g++-13	test11.txt	AC	6 ms	4 MB
g++-13	test12.txt	AC	5 ms	4 MB
g++-13	test13.txt	AC	5 ms	4 MB
g++-13	test14.txt	AC	6 ms	4 MB
g++-13	test15.txt	AC	6 ms	4 MB
g++-13	test16.txt	AC	6 ms	4 MB
g++-13	test17.txt	AC	6 ms	4 MB
g++-13	test18.txt	AC	6 ms	4 MB
g++-13	test19.txt	AC	6 ms	4 MB
g++-13	test20.txt	AC	15 ms	4 MB
g++-13	test21.txt	AC	15 ms	4 MB
g++-13	test22.txt	AC	15 ms	4 MB
g++-13	test23.txt	AC	15 ms	4 MB
g++-13	test24.txt	AC	15 ms	4 MB
g++-13	test25.txt	AC	15 ms	4 MB
g++-13	test26.txt	AC	15 ms	4 MB
g++-13	test27.txt	AC	14 ms	4 MB
g++-13	test28.txt	AC	14 ms	4 MB
g++-13	test29.txt	AC	15 ms	4 MB
g++-13	test30.txt	AC	15 ms	4 MB
g++-13	test31.txt	AC	15 ms	4 MB
g++-13	test32.txt	AC	15 ms	4 MB
g++-13	test33.txt	AC	15 ms	4 MB
g++-13	test34.txt	AC	15 ms	4 MB
g++-13	test35.txt	AC	15 ms	4 MB
g++-13	test36.txt	AC	15 ms	4 MB
g++-13	test37.txt	AC	15 ms	4 MB
g++-13	test38.txt	AC	15 ms	4 MB
g++-13	test39.txt	AC	15 ms	4 MB
g++-13	test40.txt	AC	14 ms	4 MB
g++-13	test41.txt	AC	6 ms	4 MB
g++-13	test42.txt	AC	6 ms	4 MB
g++-13	test43.txt	AC	12 ms	4 MB
g++-13	test44.txt	AC	12 ms	4 MB
g++-13	test45.txt	AC	12 ms	4 MB
g++-13	test46.txt	AC	14 ms	4 MB
g++-13	test47.txt	AC	14 ms	4 MB
g++-13	test48.txt	AC	14 ms	4 MB
g++-13	test49.txt	AC	14 ms	4 MB
g++-13	test50.txt	AC	14 ms	4 MB
g++-13	test51.txt	AC	6 ms	4 MB
g++-13	test52.txt	AC	6 ms	4 MB
g++-13	test53.txt	AC	5 ms	4 MB
clang++-18	sample01.txt	AC	6 ms	4 MB
clang++-18	sample02.txt	AC	5 ms	4 MB
clang++-18	sample03.txt	AC	5 ms	4 MB
clang++-18	test01.txt	AC	5 ms	4 MB
clang++-18	test02.txt	AC	5 ms	4 MB
clang++-18	test03.txt	AC	12 ms	4 MB
clang++-18	test04.txt	AC	11 ms	4 MB
clang++-18	test05.txt	AC	12 ms	4 MB
clang++-18	test06.txt	AC	7 ms	4 MB
clang++-18	test07.txt	AC	11 ms	4 MB
clang++-18	test08.txt	AC	8 ms	4 MB
clang++-18	test09.txt	AC	10 ms	4 MB
clang++-18	test10.txt	AC	9 ms	4 MB
clang++-18	test11.txt	AC	5 ms	4 MB
clang++-18	test12.txt	AC	5 ms	4 MB
clang++-18	test13.txt	AC	5 ms	4 MB
clang++-18	test14.txt	AC	5 ms	4 MB
clang++-18	test15.txt	AC	5 ms	4 MB
clang++-18	test16.txt	AC	5 ms	4 MB
clang++-18	test17.txt	AC	5 ms	4 MB
clang++-18	test18.txt	AC	5 ms	4 MB
clang++-18	test19.txt	AC	5 ms	4 MB
clang++-18	test20.txt	AC	14 ms	4 MB
clang++-18	test21.txt	AC	15 ms	4 MB
clang++-18	test22.txt	AC	15 ms	4 MB
clang++-18	test23.txt	AC	15 ms	4 MB
clang++-18	test24.txt	AC	15 ms	4 MB
clang++-18	test25.txt	AC	15 ms	4 MB
clang++-18	test26.txt	AC	15 ms	4 MB
clang++-18	test27.txt	AC	15 ms	4 MB
clang++-18	test28.txt	AC	15 ms	4 MB
clang++-18	test29.txt	AC	15 ms	4 MB
clang++-18	test30.txt	AC	15 ms	4 MB
clang++-18	test31.txt	AC	14 ms	4 MB
clang++-18	test32.txt	AC	15 ms	4 MB
clang++-18	test33.txt	AC	15 ms	4 MB
clang++-18	test34.txt	AC	15 ms	4 MB
clang++-18	test35.txt	AC	15 ms	4 MB
clang++-18	test36.txt	AC	15 ms	4 MB
clang++-18	test37.txt	AC	15 ms	4 MB
clang++-18	test38.txt	AC	15 ms	4 MB
clang++-18	test39.txt	AC	15 ms	4 MB
clang++-18	test40.txt	AC	13 ms	4 MB
clang++-18	test41.txt	AC	6 ms	4 MB
clang++-18	test42.txt	AC	5 ms	4 MB
clang++-18	test43.txt	AC	11 ms	4 MB
clang++-18	test44.txt	AC	12 ms	4 MB
clang++-18	test45.txt	AC	12 ms	4 MB
clang++-18	test46.txt	AC	14 ms	4 MB
clang++-18	test47.txt	AC	13 ms	4 MB
clang++-18	test48.txt	AC	13 ms	4 MB
clang++-18	test49.txt	AC	14 ms	4 MB
clang++-18	test50.txt	AC	13 ms	4 MB
clang++-18	test51.txt	AC	5 ms	4 MB
clang++-18	test52.txt	AC	5 ms	4 MB
clang++-18	test53.txt	AC	5 ms	4 MB

Back to top page