GCJ 2019 Round 1A B - Golf Gophers

難読。。。でも一見複雑に見えて実はシンプルという問題みたい！！！

問題へのリンク

問題概要

B の題意、結局求めたい数を V として、

・x を 18 個吐いたら 18 個整数が返って来て、その和を x で割った余りを求めると、それが V % x になっている

・これを 7 回やっていいから V <= 10^6 を当ててね( *˙ω˙*)و

で合ってるかな？？

— けんちょん (@drken1215) April 13, 2019

制約

• 使っていい の回数 <= 7
• 当てるべき数 <= 10⁶

考えたこと

題意さえわかれば、中国剰余定理！！！！！

昔、兵士の集まりがあって何人いるかを素早く調べたいとき、

• 3 人組になってもらって何人あまるかを求める (人数を 3 で割ったあまりを求める)
• 5 人組になってもらって何人あまるかを求める (人数を 5 で割ったあまりを求める)
• 7 人組になってもらって何人あまるかを求める (人数を 7 で割ったあまりを求める)

をすることで、中国剰余定理によって、人数を 105 で割ったあまりが一意に求められることを利用した話が有名！

同じように 12, 13, 14, 15, 16, 17, 18 の最小公倍数を L とすると、L >= 10⁶ であり、中国剰余定理によると

• 12 で割ったあまりが a
• 13 で割ったあまりが b
• 14 で割ったあまりが c
• 15 で割ったあまりが d
• 16 で割ったあまりが e
• 17 で割ったあまりが f
• 18 で割ったあまりが g

となる数を L で割ったあまりは存在するならば一意に決まる！ただし、3, 5, 7 の例とは違って、12〜18 は互いに素ではないので、a〜g を決めても答えが存在するとは限らない。

でも今回の問題では、実在の x について、12〜18 で割ったあまりを答えてもらっているので、x を L で割ったあまりは存在して一意に決まる。

中国剰余定理ライブラリは不要

で、一瞬中国剰余定理ライブラリを持っていないと詰まりそうになるのだが、10⁶ 程度であればそんなことしなくてよくて、

中国剰余するまでもないのんな。。。
10^6 サイズのバケット用意して、12〜18 で割った余りの該当するところをカウントしてあげて、カウンタ値が 7 になってるものを答えるだけかな？？

— けんちょん (@drken1215) April 13, 2019

とすれば OK

#include <iostream>
#include <vector>
#include <cassert>
using namespace std;

const int MAX = 1010100;
vector<int> mods = {12, 13, 14, 15, 16, 17, 18};

void solve(int N, int M) { 
    vector<int> nums(MAX, 0);
    for (auto mod : mods) {
        for (int i = 0; i < 18; ++i) {
            cout << mod;
            if (i != 17) cout << " ";
        }
        cout << endl;
        
        int amari = 0;
        for (int i = 0; i < 18; ++i) {
            int a; cin >> a;
            amari = (amari + a) % mod;
        }
        for (int v = amari; v < MAX; v += mod) nums[v]++;
    }
    int res = -1;
    for (int n = 1; n < MAX; ++n) if (nums[n] == 7) res = n;
    cout << res << endl;
    int verify;
    cin >> verify;
    assert(verify == 1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int T, N, M;
    cin >> T >> N >> M;
    for (int _ = 0; _ < T; ++_) {
        solve(N, M);
    }
}