Đây là bài interactive đầu tiên mình từng viết nên mình xin trình bày cách làm bài này theo cách tối ưu và chính xác nhất (C++):

Solution 1: Brute-force (WA)

Do các số cần được đoán chỉ nằm gọn trong giới hạn \([1,100]\) nên các bạn có thể dùng lệnh:

for(int i = 1; i <= 100; ++i){
    if (query(i)) {
        cout << "! " << i << "\n";
        cout.flush();
        return 0;
    }
}

Và sau đó nhận các tham số như sau:

bool query(int i){
    cout << "? " << type << "\n";
    cout.flush();
    int type; cin >> type;
    return (type == 1);
}

Độ phức tạp:

• Time complexity: \(O(N)\)
• Memory complexity: \(O(1)\)

Code của bạn có thể AC với các số cần đoán từ \([1,8]\) nhưng nếu số cần đoán \(>8\) thì bạn WA.

Solution 2: AC - solution

Do số lượng các câu hỏi tối đa là \(8\) (mà: \(2^8=256>100\)) nên các bạn có thể chặt nhị phân để:

• Tối ưu số lượng câu hỏi
• Tận dụng tối đa các phản hổi của máy chấm

Vậy ta có cài đặt như sau:

int l = 1, r = 100;
while (l <= r) {
    int mid = l + (r - l) / 2;
    cout << "? " << mid << endl;
    cout.flush();
    int t; cin >> t;
    if (t == 1) {
        cout << "! "<<mid<<endl;
        cout.flush();
        return 0;
    }else if (t == 2) {
        l = mid + 1;
    }else {
        r = mid - 1;
    }
}