Nhận xét: Do đề bài chỉ cần tối ưu số lần hỏi miếng ngon nhất, ta sẽ tận dụng điều này bằng cách hỏi miếng ngon nhì nhiều nhất có thể.

Ta có thuật toán sau:

• Đầu tiên hỏi ~1~ lần xác định trong ~0~ và ~1~ miếng nào ngon hơn, duy trì hai biến ~best, second~ tương ứng vị trí của miếng ngon nhất và ngon nhì.

• Với ~i \geq 2~, ta xét trường hợp như sau:

  • Nếu miếng thứ ~i~ không ngon hơn miếng ~second~ thì bỏ qua

  • Nếu miếng thứ ~i~ ngon hơn miếng ~second~ thì ta sẽ hỏi tiếp miếng thứ ~i~ với miếng ~best~ rồi cập nhật lại ~best~, ~second~

Để tránh bị giám khảo đưa vô những test khó, ta sẽ hoán vị lại thứ tự duyệt.

Nhận xét: Giá trị kỳ vọng số lần ta thử miếng ngon nhất là khoảng ~3~ với ~n~ đủ lớn.

Chứng minh:

Số lần thử ~best~ khi gặp lần đầu (Gọi là ~E[A]~)

Lần đầu nó xuất hiện trong thứ tự duyệt:

1. Nếu ~best~ xuất hiện trong vị trí ~0~ hoặc ~1~ có xác suất là ~\frac{2}{n}~

2. Nếu ~best~ xuất hiện trong các vị trí từ ~2~ trở lên có xác suất là ~1 - \frac{2}{n}~

$$E[A] = \frac{2}{n} + 2 \cdot (1 - \frac{2}{n}) = 2 - \frac{2}{n}$$

Những lần nó bị chạm khi đã đã tìm thấy ~best~ (Gọi là ~E[B]~)

Điều kiện là ~second~ phải ngon nhất trong các miếng khác ~best~.

Xét tập tập giá trị còn lại: $$S = \{x, x + 1, ..., n - 1\}$$ Khi đó ~n - 1~ phải xuất hiện trước ~x~, và ~x + 1, x + 2, ..., n - 2~ chưa từng xuất hiện. Như vậy xác suất sẽ là: $$\frac{1}{(n - x) \cdot (n - x + 1)}$$

Như vậy giá trị kỳ vọng ở bước này là: $$E[B] = \sum_{m = 1}^{n - 1} \frac{1}{(m \cdot (m + 1))} = \sum_{m = 1}^{n - 1} (\frac{1}{m} - \frac{1}{m + 1}) = 1 - \frac{1}{n}$$ Tổng kết lại: $$E[M] = E[A] + E[B] = 3 - \frac{3}{n}$$ Như vậy với ~n~ đủ lớn thì số lần ta hỏi chỉ xấp xỉ ~3~ lần.

#include <bits/stdc++.h>

using namespace std;
bool BEGIN_ALLOC;

#define FOR(i, l, r) for(int i = (l); i < (r); ++i)
#define F0R(i, r) FOR(i, 0, r)
#define FORD(i, l, r) for(int i = (r) - 1; i >= (l); --i)
#define F0RD(i, r) FORD(i, 0, r) 

#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define sz(v) (int)v.size()
#define pb push_back
#define eb emplace_back
#define uniquify(v) v.erase(unique(all(v)), end(v))

#define F first
#define S second
#define mp make_pair
#define mt make_tuple

#define tcT template<class T
#define tcTU tcT, class U

tcT> bool minimize(T& a, const T& b){ return (a > b ? a = b, 1 : 0); }
tcT> bool maximize(T& a, const T& b){ return (a < b ? a = b, 1 : 0); }
tcT> using vc = vector<T>;
tcT> using vvc = vector<T>;
tcT> int lwb(vector<T>& a, const T& b){ return lower_bound(all(a), b) - a.begin(); }
tcT> int upb(vector<T>& a, const T& b){ return upper_bound(all(a), b) - a.begin(); }
tcT> using minHeap = priority_queue<T, vector<T>, greater<T>>;
tcT> using maxHeap = priority_queue<T>;
tcT> constexpr T infty = numeric_limits<T>::max() / 2; 

using ll = long long;
using ull = unsigned long long;
using str = string;

using pi = pair<int, int>;
using pl = pair<ll, ll>;

using vi = vector<int>;
using vl = vector<ll>;

using vpi = vector<pi>;
using vpl = vector<pl>;

using vvi = vector<vi>;
using vvl = vector<vl>;

mt19937 rng(12312123);
void testcase(){
    int N;
    cin >> N;
    vi p(N);
    iota(all(p), 0);
    shuffle(all(p), rng);

    int best, secBest;

    auto query = [&](int i, int j){
        cout << "? " << i << ' ' << j << endl;
        int mx; cin >> mx;
        return mx;
    };

    auto answer = [&](int x){
        cout << "answer " << x << endl;
    };

    if(query(p[0], p[1]) == p[0]){
        best = p[0];
        secBest = p[1];
    } else{
        best = p[1];
        secBest = p[0];
    }

    for(int i = 2; i < N; ++i){
        int u = p[i];
        int m = query(secBest, u);
        if(m == u){
            if(query(best, u) == best){
                secBest = u;
            } else{
                secBest = best;
                best = u;
            }
        } 
    }
    answer(best);
}

bool END_ALLOC;
int main(){
    int tests = 1;
    // cin >> tests;
    F0R(t, tests){
        testcase();
    }

    cerr << '\n';
    cerr << "[Static memory : " << abs((&END_ALLOC) - (&BEGIN_ALLOC)) / (1024.0 * 1024.0) << "]\n";
    return 0;
}