GCJ2019 B - Draupnir

• 問題へのリンク

問題概要

日リングは、日ごとに2倍になる。最初、日目に日リングを個（, ）持っている。ただし、の少なくとも一つは以上である。

あなたは回質問できる。一回の質問で、日（）のリングの所持数の合計を知ることができるので、を調べよ。ただし、所持数の合計はである。

• Small

• Large

解説

Small

6回質問できるので、1 ~ 6日目を聞いて、連立方程式を解けばよい。手で解くのは無理なので、WalfmanAlphaなどを使って掃き出し法で解いてもらう。

結果のリンク

• コード

#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

int t, w;
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> t >> w;
    while(t--){
        ll D[7] = {};
        //interact w times
        for(int i = 1; i <= w; i++){
            cout << i << endl;
            cin >> D[i];
        }
        int a[][8] = {
            {0,   0,   0,   0,  0,  0,  0,   0},
            {0,   4,  -4,  -2,  0,  0,  1,  40},
            {0, -24,  24,   2,  0,  0, -1,  20},
            {0,  -4,  -6,  12,  0,  0, -1,  10},
            {0,  16, -16,  -8, 10,  0, -1,  10},
            {0,  -8,   8,   4, -5,  5, -2,   5},
            {0,  12,  -2,  -6,  0, -5,  3,   5},
        };
        //calc
        ll ans[7] = {};
        for(int i = 1; i <= 6;i++){
            for(int j = 1; j <= 6;j++) ans[i] += a[i][j] * D[j];
            ans[i] /= a[i][7];
        }
        //output
        for(int i = 1; i <= 6; i++){
            cout << ans[i];
            if(i == 6)cout << endl;
            else cout << " ";
        }
        //last input
        int valid;
        cin >> valid;
        if(valid == -1)return 0;
    }
}

Large

2回しか質問を取れないので、どうにかうまい質問で情報を取りたい。

日の情報は、以下のように表される。

を乗算するということは、bit演算で考えると、個の左シフトである。 i 今回、なので、のbit表現はつの連続するbitで表現されている。よって、それぞれの値が個以上シフトが離れていれば独立に取り出せるということである。

また、質問で返ってくる値はなので、回以上シフトされるとその値の影響は無視することができる。

以上のような考察により、の場合のを最初に独立に取り出し、に関しては後から同様に取り出せばよいことがわかる。一度の質問で三つ全て取り出すためには、うまい数を見つけなければならないが、適当に実験を回して見つければよい。

#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)
#define rep1(i,N) for(int i=1;i<int(N);++i)
typedef long long ll;
int t, w;

ll R[7];
ll V;
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> t >> w;
    while(t--){
        //calc
        // V[1]を使う
        cout << 191 << endl;
        cin >> V;
        R[6] = (V >> (191 / 6)) % 128;
        R[5] = (V >> (191 / 5)) % 128;
        R[4] = (V >> (191 / 4)) % 128;
        // V[2]を使う
        cout << 48 << endl;
        cin >> V;
        V -= (R[4]<<(48/4));
        V -= (R[5]<<(48/5));
        V -= (R[6]<<(48/6));
        R[3] = (V >> (48 / 3)) % 128;
        R[2] = (V >> (48 / 2)) % 128;
        R[1] = (V >> (48 / 1)) % 128;
        //output
        for(int i = 1; i <= 6; i++){
            cout << R[i];
            if(i == 6)cout << endl;
            else cout << " ";
        }
        //last input
        int valid;
        cin >> valid;
        if(valid == -1)return 0;
    }
}