tests/iteration/combinations.test.cpp

View this file on GitHub
Last update: 2024-05-03 21:18:09+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/problems/ITP1_7_B

Depends on

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/ITP1_7_B"

#include <bits/stdc++.h>
#include "ugilib/base/constants.hpp"
#include "ugilib/base/definitions.hpp"
#include "ugilib/iteration/all_combinations.hpp"

using namespace std;

// debug settings
// #define DEBUG
#ifdef DEBUG
// debug input
string _INPUT = R"(
5
1 2 3 4 5
)";
auto _cin = stringstream(_INPUT.substr(1)); // remove '\n' at _INPUT[0]
#else
// standard input
auto& _cin = cin;
#endif

// speed up
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

// reader
struct rd {
    // T
    template<typename T> static T i() { T x; _cin >> x; return x; }  // T item
    // vector<T>
    template<typename T> static vector<T> v(int n) {vector<T> v(n); rep(i, n) _cin >> v[i]; return v;}  // vector<T>
    // vector<pair<T, T>>
    template<typename T> static vector<pair<T, T>> vp(int n) {vector<pair<T, T>> v(n); rep(i, n) _cin >> v[i].first >> v[i].second; return v;}  // vector<pair<T, T>>
    // tuple
    template<typename... Args> static tuple<Args...> t() {
        tuple<Args...> values;
        apply([](auto&... args) { ((_cin >> args), ...); }, values);
        return values;
    }
};

// debug print utility
namespace deb {
    #include <cxxabi.h>
    // demangle type name
    string demangle(const char* name) {
        int status = -4;
        unique_ptr<char, void(*)(void*)> res{
            abi::__cxa_demangle(name, NULL, NULL, &status),
            free
        };
        return (status == 0) ? string(res.get()) : name ;
    }
    // meta functions for type traits
    template<typename T>
    constexpr bool isArithmeticContainer() { return is_arithmetic<typename T::value_type>::value; }
    // for SFINAE
    template<typename T, typename = void> struct has_key_and_mapped_type : false_type {};
    template<typename T> struct has_key_and_mapped_type<T, void_t<typename T::key_type, typename T::mapped_type>> : true_type {};
    // for map or unordered_map
    template<typename T>
    constexpr bool isMapLike() { return has_key_and_mapped_type<T>::value; }

    // for values
    template<typename T, typename enable_if<is_arithmetic<T>::value, nullptr_t>::type = nullptr>
    void p(const T& x) { cout << x << " "; }
    // for pairs
    template <typename T, typename S>
    void p(const pair<T, S>& _p){ p(_p.first); p(_p.second); cout << endl; }
    // for containers
    template<typename T,  typename enable_if<!is_arithmetic<T>::value, nullptr_t>::type = nullptr>
    void p(const T& container) {
        // map and unordered_map
        if constexpr (isMapLike<T>()) {
            cout << demangle(typeid(T).name()) << ":" << endl;
            for (const auto& kv : container) {
                cout << "[" << kv.first << "] => ";
                p(kv.second);
                if constexpr (is_arithmetic_v<typename T::mapped_type>) cout << endl;
            }
        // vector or set or others
        } else {
            if constexpr (!isArithmeticContainer<T>()) cout << demangle(typeid(T).name()) << ":" << endl;
            for (auto it = begin(container); it != end(container); ++it) {
                p(*it);
            }
            if constexpr (isArithmeticContainer<T>()) cout << endl;
        }
    }
};  // namespace deb

int main() {
    auto& cin = _cin;
    // speed up io
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    // code
    while (true) {
        auto [n, x] = rd::t<int, int>();
        if (n == x && x == 0) break;

        int ans = 0;
        auto f = [&](const vector<size_t> &indices) {
            int y = 0;
            for (const auto i : indices) y += i+1;  // [0, n-1]のインデックスが渡されるので，それぞれ1を足して[1, n]にする
            if (y == x) ans += 1;
            return false;
        };
        ugilib::exec_all_combinations(n, 3, f);
        cout << ans << endl;
    }

    return 0;
}

#line 1 "tests/iteration/combinations.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/ITP1_7_B"

#include <bits/stdc++.h>
#line 2 "ugilib/base/definitions.hpp"

using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define rep(i, n) for(size_t i = 0; i < n; i++)  // rep macro
#define all(v) begin(v), end(v)  // all iterator
#line 3 "ugilib/base/constants.hpp"

namespace ugilib::constants {
    template<typename T>
    inline constexpr T INF = std::numeric_limits<T>::max() / 2;
} // namespace ugilib::constants

const ll INF = ugilib::constants::INF<ll>;
#line 2 "ugilib/iteration/all_combinations.hpp"

/**
 * @file all_combinations.hpp
 * @brief 全ての順列/組み合わせに対する処理を簡略化する関数
 *
 * ## 関数一覧
 * - `exec_all_combinations(num_items, num_pick, f)` : 全ての組み合わせに対して指定された関数を実行します.
 * - `exec_all_permutations(num_items, num_pick, f)` : 全ての順列に対して指定された関数を実行します.
 */

#line 4 "ugilib/iteration/next_combination.hpp"

using namespace std;

namespace ugilib {
    /**
     * @brief 次の組み合わせを生成する
     * @param indices 現在の組み合わせ
     * @param num_items 全体の要素数
     * @return bool 次の組み合わせが存在するかどうか
     * @details 例えば, indices = {0, 1, 2}, num_items = 5の場合, 次の組み合わせは{0, 1, 3}となる
     * @details これをラップしたものがexec_all_combination
    */
    bool next_combination(vector<size_t> &indices, const size_t &num_items) {
        const int num_pick = indices.size();
        for (signed i = num_pick - 1; i >= 0; i--) {
            if (indices[i] < num_items - num_pick + i) {
                indices[i]++;
                for (size_t j = i + 1; j < num_pick; j++) {
                    indices[j] = indices[j - 1] + 1;
                }
                return true;
            }
        }
        return false;
    }
} // namespace ugilib
#line 15 "ugilib/iteration/all_combinations.hpp"

using namespace std;

namespace ugilib {
    /**
     * @brief 全てのCombinationに対して関数を実行する
     * @tparam Func 実行操作のラムダ式
     * @param num_items 選択対象全体の要素数
     * @param num_pick 選択する要素数
     * @param f 実行する関数. trueを返すと探索を打ち切る
     * @return 途中で探索を打ち切った場合はtrue, それ以外はfalse
     * @details ラムダ式には選択した要素のインデックスが昇順で渡される
     * @details num_items個の中からnum_pick個選ぶ組み合わせを全探索し, それぞれに対して関数fを実行する
     * @example
     * auto f = [&](const vector<size_t> &indices) {
     *    for (const auto &i : indices) {
     *       cout << i << " ";
     *    }
     *    cout << endl;
     *    return false;
     * };
     * exec_all_combination(5, 3, f);
    */
    template <typename Func>
    bool exec_all_combinations(const size_t &num_items, const size_t &num_pick, Func f) {
        vector<size_t> indices(num_pick);
        iota(indices.begin(), indices.end(), 0);
        do {
            bool will_break = f(indices);
            if (will_break) return true;
        } while (next_combination(indices, num_items));
        return false;
    }

    /**
     * @brief 全てのPermutationに対して関数を実行する. 順列に存在しうる要素数より, 実際の要素数が小さくても実行可能
     * @tparam Func 実行操作のラムダ式
     * @param num_items 選択対象全体の要素数
     * @param num_pick 選択する要素数
     * @param f 実行する関数. trueを返すと探索を打ち切る
     * @return 途中で探索を打ち切った場合はtrue, それ以外はfalse
     * @details ラムダ式には選択した要素のインデックスの順列が渡される
     * @details num_items個の中からnum_pick個選ぶ順列を全探索し, それぞれに対して関数fを実行する
     * @details next_permutation との違いは, 選択対象全体の要素数よりも実際に選択する要素数が少ない場合でも実行可能な点
     * @details num_items choose num_pick の組み合わせを全探索する
     * @example
     * auto f = [&](const vector<size_t> &indices) {
     *   for (const auto &i : indices) {
     *      cout << i << " ";
     *   }
     *   cout << endl;
     *   return false;
     * };
     * exec_all_permutations(5, 3, f);
    */
    template <typename Func>
    bool exec_all_permutations(const size_t &num_items, const size_t &num_pick, Func f) {
        // 全要素からnum_pick個だけ選ばれる
        vector<bool> mask(num_items, false);
        fill(mask.begin(), mask.begin() + num_pick, true);  // 選ばれる要素のマスク

        // 途中終了フラグ
        bool will_break = false;
        do {
            // maskする
            vector<size_t> permutation;
            for (int i = 0; i < mask.size(); i++) {
                if (mask[i]) permutation.push_back(i);
            }

            // mask要素で順列全てに対して操作を行う
            do {
                will_break = f(permutation);
                if (will_break) return true;  // 途中終了
            } while (next_permutation(permutation.begin(), permutation.end()));
        } while (prev_permutation(mask.begin(), mask.end()));

        return false;  // 全探索終了
    }
}  // namespace ugilib
#line 7 "tests/iteration/combinations.test.cpp"

using namespace std;

// debug settings
// #define DEBUG
#ifdef DEBUG
// debug input
string _INPUT = R"(
5
1 2 3 4 5
)";
auto _cin = stringstream(_INPUT.substr(1)); // remove '\n' at _INPUT[0]
#else
// standard input
auto& _cin = cin;
#endif

// speed up
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

// reader
struct rd {
    // T
    template<typename T> static T i() { T x; _cin >> x; return x; }  // T item
    // vector<T>
    template<typename T> static vector<T> v(int n) {vector<T> v(n); rep(i, n) _cin >> v[i]; return v;}  // vector<T>
    // vector<pair<T, T>>
    template<typename T> static vector<pair<T, T>> vp(int n) {vector<pair<T, T>> v(n); rep(i, n) _cin >> v[i].first >> v[i].second; return v;}  // vector<pair<T, T>>
    // tuple
    template<typename... Args> static tuple<Args...> t() {
        tuple<Args...> values;
        apply([](auto&... args) { ((_cin >> args), ...); }, values);
        return values;
    }
};

// debug print utility
namespace deb {
    #include <cxxabi.h>
    // demangle type name
    string demangle(const char* name) {
        int status = -4;
        unique_ptr<char, void(*)(void*)> res{
            abi::__cxa_demangle(name, NULL, NULL, &status),
            free
        };
        return (status == 0) ? string(res.get()) : name ;
    }
    // meta functions for type traits
    template<typename T>
    constexpr bool isArithmeticContainer() { return is_arithmetic<typename T::value_type>::value; }
    // for SFINAE
    template<typename T, typename = void> struct has_key_and_mapped_type : false_type {};
    template<typename T> struct has_key_and_mapped_type<T, void_t<typename T::key_type, typename T::mapped_type>> : true_type {};
    // for map or unordered_map
    template<typename T>
    constexpr bool isMapLike() { return has_key_and_mapped_type<T>::value; }

    // for values
    template<typename T, typename enable_if<is_arithmetic<T>::value, nullptr_t>::type = nullptr>
    void p(const T& x) { cout << x << " "; }
    // for pairs
    template <typename T, typename S>
    void p(const pair<T, S>& _p){ p(_p.first); p(_p.second); cout << endl; }
    // for containers
    template<typename T,  typename enable_if<!is_arithmetic<T>::value, nullptr_t>::type = nullptr>
    void p(const T& container) {
        // map and unordered_map
        if constexpr (isMapLike<T>()) {
            cout << demangle(typeid(T).name()) << ":" << endl;
            for (const auto& kv : container) {
                cout << "[" << kv.first << "] => ";
                p(kv.second);
                if constexpr (is_arithmetic_v<typename T::mapped_type>) cout << endl;
            }
        // vector or set or others
        } else {
            if constexpr (!isArithmeticContainer<T>()) cout << demangle(typeid(T).name()) << ":" << endl;
            for (auto it = begin(container); it != end(container); ++it) {
                p(*it);
            }
            if constexpr (isArithmeticContainer<T>()) cout << endl;
        }
    }
};  // namespace deb

int main() {
    auto& cin = _cin;
    // speed up io
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    // code
    while (true) {
        auto [n, x] = rd::t<int, int>();
        if (n == x && x == 0) break;

        int ans = 0;
        auto f = [&](const vector<size_t> &indices) {
            int y = 0;
            for (const auto i : indices) y += i+1;  // [0, n-1]のインデックスが渡されるので，それぞれ1を足して[1, n]にする
            if (y == x) ans += 1;
            return false;
        };
        ugilib::exec_all_combinations(n, 3, f);
        cout << ans << endl;
    }

    return 0;
}