Bước 1:

Dùng ~2~ thao tác để có được ~cnt_a~, ~cnt_b~, ~cnt_c~. Sau đó rút ra ~2~ ký tự có ~cnt~ thấp nhất để tiến hành dựng xâu.

Bước 2:

Đặt ~2~ loại ký tự có số lượng nhỏ nhất là ~x, y~, có số lượng ký tự lần lượt là ~r_x~, ~r_y~. Đặt xâu đang dựng là xâu ~s_{xy}~.

Liên tục lặp lại truy vấn với xâu ~s_{xy}~ + (~1~ ký tự ~x~) + (~r_y~ ký tự ~y~).

Nếu kết quả là \|~s_{xy}~\| + ~1~ + ~r_y~ thì ta biết được ký tự tiếp theo là ~x~ còn không thì là ký tự ~y~. Thêm ký tự mới vào xâu ~s_{xy}~ đồng thời trừ đi ~r_x~ hoặc ~r_y~ tương ứng với ký tự vừa thêm. Lặp lại liên tục đến khi ~r_x~ hoặc ~r_y~ bằng ~0~.

Sau đó thêm số lượng ký tự ~r_x~ hoặc ~r_y~ còn thừa vào xâu.

Bước 3:

Ta có được thứ tự đúng của ~2~ loại ký tự ~x, y~. Gọi ký tự còn lại là ~z~, ta tìm cách thêm ký tự ~z~ này vào giữa các ký tự của ~x, y~.

Xét các khoảng trống, với các khoảng trống ta duyệt từng số lượng ký tự ~z~ tăng dần từ ~1~. Mỗi lần thêm, truy vấn xâu ~s_{xy}~ với số lượng ký tự ~z~ thêm vào khoảng trống được duyệt. Nếu kết quả tăng, thì tăng số lượng ký tự ~z~ được thêm lên. Không thì lưu lại số lượng ký tự rồi chuyển sang khoảng trống mới.

Lặp lại với các khoảng trống, có tổng cộng ~|s_{xy}| + 1~ khoảng trống nhưng chỉ cần duyệt ~|s_{xy}|~ vì khoảng trống cuối cùng chính là số lượng ký tự ~z~ còn lại.

Số truy vấn: Ta có bước ~1~ hết ~2~ truy vấn. Bước ~2~ trường hợp xấu nhất số truy vấn hỏi là ~r_x + r_y~. Do ~r_x~, ~r_y~ là ~2~ số lượng nhỏ nhất ~=>~ ~r_x + r_y \le \left\lfloor \frac{2}{3} n \right\rfloor~. Bước ~3~ số lượng truy vấn hỏi sẽ là ~s_{xy} - 1~ tương ứng với số lần chuyển chỗ trống tối đa (~-1~ là do ký tự ~z~ cuối cùng được hỏi xong thì không cần tốn ~1~ lần hỏi sau để chuyển chỗ trống nữa), thêm với ~r_z~ tương ứng số lần hỏi cho từng ký tự ~z~ đặt đúng chỗ. Số truy vấn cho bước ~3~ là ~s_{xy} - 1 + r_z = n - 1~. Tổng số truy vấn tối đa cho ~3~ bước là ~2~ ~+~ ~\left\lfloor \frac{2}{3} n \right\rfloor~ ~+~ ~n - 1 = \left\lfloor \frac{5}{3} n \right\rfloor + 1~.

#include <bits/stdc++.h>
using namespace std;
const int maxn = (1000) + 7;
int cnt[3], pos[maxn];
char a[3];
int main(){
    int n; cin >> n;
    cout << "? ";
    for (int i = 1; i <= n; ++i) cout << "a";
    cout << '\n';
    cin >> cnt[0];
    cout << "? ";
    for (int i = 1; i <= n; ++i) cout << "b";
    cout << '\n';
    cin >> cnt[1];
    cnt[2] = n - cnt[0] - cnt[1];
    a[0] = 'a'; a[1] = 'b'; a[2] = 'c';
    if (cnt[0] > cnt[1]){
        swap(cnt[0], cnt[1]); swap(a[0], a[1]);
    }
    if (cnt[1] > cnt[2]){
        swap(cnt[1], cnt[2]); swap(a[1], a[2]);
    }
    if (cnt[0] > cnt[1]){
        swap(cnt[0], cnt[1]); swap(a[0], a[1]);
    }
    string s; int rx = cnt[0]; int ry = cnt[1];
    while (rx > 0 && ry > 0){
        cout << "? " << s;
        cout << a[0];
        for (int i = 1; i <= ry; ++i) cout << a[1];
        cout << '\n';
        int x; cin >> x;
        if (x == s.size() + 1 + ry){
            s.push_back(a[0]); rx--;
        }
        else {s.push_back(a[1]); ry--;}
    }
    while (rx){ s.push_back(a[0]); rx--;}
    while (ry){ s.push_back(a[1]); ry--;}
    int rz = 0;
    for (int i = 0; i < s.size(); ++i){
        while (true){
            if (rz + pos[i] == cnt[2]) break;
            cout << "? ";
            for (int j = 0; j < i; ++j) cout << s[j];
            for (int j = 1; j <= pos[i] + 1; ++j) cout << a[2];
            for (int j = i; j < s.size(); ++j) cout << s[j];
            cout << '\n';
            int x; cin >> x;
            if (x == s.size() + pos[i] + 1) pos[i]++; else break;
        }
        rz += pos[i];
    }
    cout << "! ";
    pos[s.size()] = cnt[2] - rz;
    for (int i = 0; i <= s.size(); ++i){
        for (int j = 0; j < pos[i]; ++j) cout << a[2];
        if (i < s.size()) cout << s[i];
    }

}