interactor.cpp

#include <algorithm>
#include <map>
#include <cassert>
#include <iostream>
#include <set>
#include <unordered_set>
#include <string>
#include <vector>
using namespace std;
typedef pair<int, int> pii;

class interactor {
public:
    virtual char ask(int bunch, int number) = 0;
    virtual void answer(const string &ans) = 0;
};

class real_interactor : public interactor {
public:
    char ask(int bunch, int number) {
        char c;
        cout << bunch * 5 + number + 1 << endl;
        cin >> c;
        return c;
    }

    void answer(const string &ans) {
        cout << ans << endl;
        string tmp;
        cin >> tmp;
    }
};

class joker_interactor : public interactor {
private:
    int cnt;
    string real_ans;
    string shelf;

    void gen_again() {
        cnt = 0;

        real_ans = "ABCDE";
        random_shuffle(real_ans.begin(), real_ans.end());

        vector<string> st;
        string tmp = "ABCDE";
        do {
            if (tmp != real_ans) {
                st.push_back(tmp);
            }
        } while (next_permutation(tmp.begin(), tmp.end()));

        random_shuffle(st.begin(), st.end());
        shelf = "";
        for (auto &it : st) {
            shelf += it;
        }
    }

public:
    joker_interactor() {
        srand(228);
        gen_again();
    }

    char ask(int bunch, int number) {
        cnt++;
        return shelf[bunch * 5 + number];
    }

    void answer(const string &ans) {
        cerr << "Our answer " << ans << " Real answer " << real_ans << endl;
        assert(ans == real_ans);
        cerr << "It takes " << cnt << " questions" << endl;

        gen_again();
    }
};

char find_value(map<char, int> &counts) {
    int minimal = INT_MAX;
    char res = 'N';
    for (auto &it : counts) {
        if (it.second != 0) {
            if (minimal > it.second) {
                minimal = it.second;
                res = it.first;
            }
        }
    }
    return res;
}

void solve(interactor* h) {
    int bunches = 119;

    set<int> possibles;
    for (int i = 0; i < bunches; i++) {
        possibles.insert(i);
    }

    string templ = "ABCDE";
    string res = "";

    int letter = 0;
    while (res.size() < 5) {
        // guess the letter
        map<char, int> counts;
        for (auto it : templ) {
            if (res.find(it) == string::npos) {
                counts[it] = 0;
            }
        }
        map<int, char> results;
        for (auto it : possibles) {
            char c = h->ask(it, letter);
            results[it] = c;
            counts[c]++;
        }

        char let = find_value(counts);
        res.push_back(let);

        for (auto it : results) {
            if (it.second != let) {
                possibles.erase(it.first);
            }
        }

        letter++;
    }

    // smart hack
    char a = res.back();
    res.pop_back();
    char b = res.back();
    res.pop_back();
    res.push_back(a);
    res.push_back(b);

    h->answer(res);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    interactor* h = new real_interactor();
    // interactor* h = new joker_interactor();

    int t, f;
    cin >> t >> f;
    for (int i = 1; i <= t; i++) {
        solve(h);
    }
}