test/src/number/find_denominators/dummy.test.cpp

• View this file on GitHub
• Last update: 2022-10-20 19:29:51+09:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A

Depends on

• 分子と商から分母としてありうる範囲を計算 (library/number/find_denominators.hpp)

Code

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

#include <cassert>
#include <iostream>

#include "library/number/find_denominators.hpp"

using suisen::fld_denominators_positive;
using suisen::fld_denominators_negative;
using suisen::cld_denominators_positive;
using suisen::cld_denominators_negative;

template <typename T>
constexpr inline int pow_m1(T n) {
    return -(n & 1) | 1;
}
template <>
constexpr inline int pow_m1<bool>(bool n) {
    return -int(n) | 1;
}

template <typename T>
constexpr inline T fld(const T x, const T y) {
    return (x ^ y) >= 0 ? x / y : (x - (y + pow_m1(y >= 0))) / y;
}
template <typename T>
constexpr inline T cld(const T x, const T y) {
    return (x ^ y) <= 0 ? x / y : (x + (y + pow_m1(y >= 0))) / y;
}

bool in(const std::optional<std::pair<int, int>> &r, int x) {
    return r.has_value() and r->first <= x and x <= r->second;
}
bool out(const std::optional<std::pair<int, int>> &r, int x) {
    return not r.has_value() or x < r->first or x > r->second;
}

void cld_test(int n, int q) {
    auto res_pos = cld_denominators_positive(n, q, 100);
    if (res_pos.has_value()) {
        auto [l, r] = *res_pos;
        assert(1 <= l and r <= 100);
    }
    for (int x = 1; x <= 100; ++x) {
        if (not (cld(n, x) == q ? in : out)(res_pos, x)) {
            assert(false);
        }
    }

    auto res_neg = cld_denominators_negative(n, q, -100);
    if (res_neg.has_value()) {
        auto [l, r] = *res_neg;
        assert(-100 <= l and r <= -1);
    }
    for (int x = -100; x <= -1; ++x) {
        if (not (cld(n, x) == q ? in : out)(res_neg, x)) {
            assert(false);
        }
    }
}

void fld_test(int n, int q) {
    auto res_pos = fld_denominators_positive(n, q, 100);
    if (res_pos.has_value()) {
        auto [l, r] = *res_pos;
        assert(1 <= l and r <= 100);
    }
    for (int x = 1; x <= 100; ++x) {
        if (not (fld(n, x) == q ? in : out)(res_pos, x)) {
            assert(false);
        }
    }

    auto res_neg = fld_denominators_negative(n, q, -100);
    if (res_neg.has_value()) {
        auto [l, r] = *res_neg;
        assert(-100 <= l and r <= -1);
    }
    for (int x = -100; x <= -1; ++x) {
        if (not (fld(n, x) == q ? in : out)(res_neg, x)) {
            assert(false);
        }
    }
}

int main() {
    for (int n = -100; n <= 100; ++n) {
        for (int q = -101; q <= 101; ++q) {
            cld_test(n, q);
            fld_test(n, q);
        }
    }

    std::cout << "Hello World" << std::endl;
    return 0;
}

#line 1 "test/src/number/find_denominators/dummy.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"

#include <cassert>
#include <iostream>

#line 1 "library/number/find_denominators.hpp"



#include <limits>
#include <optional>
#include <type_traits>

namespace suisen {
    /**
     * @brief Calculates { min S, max S }, where S = { x>0 | floor(n/x)=q } in O(1) time.
     * @tparam T integer type
     * @param n numerator
     * @param q quotient (round down)
     * @param max_val upper bound (closed)
     * @return { min S, max S } if S is not empty, otherwise std::nullopt
     */
    template <typename T, std::enable_if_t<std::is_integral_v<T>, std::nullptr_t> = nullptr>
    std::optional<std::pair<T, T>> fld_denominators_positive(T n, T q, T max_val = std::numeric_limits<T>::max()) {
        T l, r;
        if (q >= 0) {
            if (n < 0) return std::nullopt;
            // cld(n + 1, q + 1) <= x <= fld(n, q)
            l = (n + 1 + q) / (q + 1), r = q == 0 ? max_val : std::min(max_val, n / q);
        } else {
            if (n >= 0) return std::nullopt;
            // cld(n, q) <= x <= fld(n + 1, q + 1)
            l = (n + q + 1) / q, r = q == -1 ? max_val : std::min(max_val, (n + 1) / (q + 1));
        }
        if (l <= r) return std::make_pair(l, r);
        else        return std::nullopt;
    }
    /**
     * @brief Calculates { min S, max S }, where S = { x<0 | floor(n/x)=q } in O(1) time.
     * @tparam T integer type
     * @param n numerator
     * @param q quotient (round down)
     * @param min_val lower bound (closed)
     * @return { min S, max S } if S is not empty, otherwise std::nullopt
     */
    template <typename T, std::enable_if_t<std::is_integral_v<T>, std::nullptr_t> = nullptr>
    std::optional<std::pair<T, T>> fld_denominators_negative(T n, T q, T min_val = std::numeric_limits<T>::min()) {
        T l, r;
        if (q >= 0) {
            if (n > 0) return std::nullopt;
            // cld(n, q) <= x <= fld(n - 1, q + 1)
            l = q == 0 ? min_val : std::max(min_val, n / q), r = (n - 1 - q) / (q + 1);
        } else {
            if (n <= 0) return std::nullopt;
            // cld(n - 1, q + 1) <= x <= fld(n, q)
            l = q == -1 ? min_val : std::max(min_val, (n - 1) / (q + 1)), r = (n - q - 1) / q;
        }
        if (l <= r) return std::make_pair(l, r);
        else        return std::nullopt;
    }
    /**
     * @brief Calculates { min S, max S }, where S = { x>0 | ceil(n/x)=q } in O(1) time.
     * @tparam T integer type
     * @param n numerator
     * @param q quotient (round down)
     * @param max_val upper bound (closed)
     * @return { min S, max S } if S is not empty, otherwise std::nullopt
     */
    template <typename T, std::enable_if_t<std::is_integral_v<T>, std::nullptr_t> = nullptr>
    std::optional<std::pair<T, T>> cld_denominators_positive(T n, T q, T max_val = std::numeric_limits<T>::max()) {
        T l, r;
        if (q > 0) {
            if (n <= 0) return std::nullopt;
            l = (n + q - 1) / q, r = q == 1 ? max_val : std::min(max_val, (n - 1) / (q - 1));
        } else {
            if (n > 0) return std::nullopt;
            l = (n - 1 + q) / (q - 1), r = q == 0 ? max_val : std::min(max_val, n / q);
        }
        if (l <= r) return std::make_pair(l, r);
        else        return std::nullopt;
    }
    /**
     * @brief Calculates { min S, max S }, where S = { x<0 | ceil(n/x)=q } in O(1) time.
     * @tparam T integer type
     * @param n numerator
     * @param q quotient (round down)
     * @param min_val lower bound (closed)
     * @return { min S, max S } if S is not empty, otherwise std::nullopt
     */
    template <typename T, std::enable_if_t<std::is_integral_v<T>, std::nullptr_t> = nullptr>
    std::optional<std::pair<T, T>> cld_denominators_negative(T n, T q, T min_val = std::numeric_limits<T>::min()) {
        T l, r;
        if (q > 0) {
            if (n >= 0) return std::nullopt;
            l = q == 1 ? min_val : std::max(min_val, (n + 1) / (q - 1)), r = (n - q + 1) / q;
        } else {
            if (n < 0) return std::nullopt;
            l = q == 0 ? min_val : std::max(min_val, n / q), r = (n + 1 - q) / (q - 1);
        }
        if (l <= r) return std::make_pair(l, r);
        else        return std::nullopt;
    }
} // namespace suisen


#line 7 "test/src/number/find_denominators/dummy.test.cpp"

using suisen::fld_denominators_positive;
using suisen::fld_denominators_negative;
using suisen::cld_denominators_positive;
using suisen::cld_denominators_negative;

template <typename T>
constexpr inline int pow_m1(T n) {
    return -(n & 1) | 1;
}
template <>
constexpr inline int pow_m1<bool>(bool n) {
    return -int(n) | 1;
}

template <typename T>
constexpr inline T fld(const T x, const T y) {
    return (x ^ y) >= 0 ? x / y : (x - (y + pow_m1(y >= 0))) / y;
}
template <typename T>
constexpr inline T cld(const T x, const T y) {
    return (x ^ y) <= 0 ? x / y : (x + (y + pow_m1(y >= 0))) / y;
}

bool in(const std::optional<std::pair<int, int>> &r, int x) {
    return r.has_value() and r->first <= x and x <= r->second;
}
bool out(const std::optional<std::pair<int, int>> &r, int x) {
    return not r.has_value() or x < r->first or x > r->second;
}

void cld_test(int n, int q) {
    auto res_pos = cld_denominators_positive(n, q, 100);
    if (res_pos.has_value()) {
        auto [l, r] = *res_pos;
        assert(1 <= l and r <= 100);
    }
    for (int x = 1; x <= 100; ++x) {
        if (not (cld(n, x) == q ? in : out)(res_pos, x)) {
            assert(false);
        }
    }

    auto res_neg = cld_denominators_negative(n, q, -100);
    if (res_neg.has_value()) {
        auto [l, r] = *res_neg;
        assert(-100 <= l and r <= -1);
    }
    for (int x = -100; x <= -1; ++x) {
        if (not (cld(n, x) == q ? in : out)(res_neg, x)) {
            assert(false);
        }
    }
}

void fld_test(int n, int q) {
    auto res_pos = fld_denominators_positive(n, q, 100);
    if (res_pos.has_value()) {
        auto [l, r] = *res_pos;
        assert(1 <= l and r <= 100);
    }
    for (int x = 1; x <= 100; ++x) {
        if (not (fld(n, x) == q ? in : out)(res_pos, x)) {
            assert(false);
        }
    }

    auto res_neg = fld_denominators_negative(n, q, -100);
    if (res_neg.has_value()) {
        auto [l, r] = *res_neg;
        assert(-100 <= l and r <= -1);
    }
    for (int x = -100; x <= -1; ++x) {
        if (not (fld(n, x) == q ? in : out)(res_neg, x)) {
            assert(false);
        }
    }
}

int main() {
    for (int n = -100; n <= 100; ++n) {
        for (int q = -101; q <= 101; ++q) {
            cld_test(n, q);
            fld_test(n, q);
        }
    }

    std::cout << "Hello World" << std::endl;
    return 0;
}

Back to top page