Đoán số

Xem PDF
Tác giả:
cuom1999
Dạng bài
Điểm: 200 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Đây là bài toán giao tiếp với máy chấm (Interactive problem)

cuom1999 có một con số \(n\) bí mật. Điều duy nhất bạn biết về con số này là \(1 \leq n \leq 2 \times 10^9\). cuom1999 và bạn sẽ chơi một trò chơi như sau: Bạn sẽ được chọn một số bất kỳ và nói cho cuom1999 nghe số đó. cuom1999 sẽ cho bạn biết con số của bạn lớn hơn, nhỏ hơn, hay bằng \(n\). Hãy đoán xem \(n\) là số nào trong không quá \(31\) câu hỏi.

Cách Thức Giao Tiếp

Mỗi lượt, bạn sẽ in ra một số \(x\) trên một dòng (\(1\leq x \leq 2 \times 10^9\)). Máy tính sẽ đọc \(x\) và in ra màn hình một chuỗi tương ứng với các trường hợp sau:

  • "BIGGER" nếu \(n > x\)
  • "SMALLER" nếu \(n < x\)
  • "HOLA" nếu \(n = x\).

Lưu ý:

  • Chuỗi mà máy in ra màn hình không có dấu "
  • Nếu các bạn in ra một output không hợp lệ (không phải là một số, số ngoài đoạn \([1, 2 \times 10^9]\) thì nhiều khả năng bị TLE.
  • Sau khi in mỗi số, bạn phải xuống dòng (ví dụ in endl trong C++)
  • Khi in ra một dòng, các bạn phải flush output bằng cách cout.flush hoặc dùng endl thay vì \n

Example

Test 1

Con số bí mật trong test này là 5.

Input Output Giải thích
1 Bạn đoán số 1
SMALLER Số 1 nhỏ hơn đáp án
9 Bạn đoán số 9
BIGGER Số 9 lớn hơn đáp án
5 Bạn đoán số 5
HOLA Hola! Bạn đã đoán đúng mà chỉ dùng 3 câu hỏi!

Bình luận


  • 1
    jumptozero    3:57 p.m. 25 Tháng 6, 2020 ← chỉnh sửa 2
    • Mình xin chia sẻ lời giải bài toán này như sau:
    • Ý tưởng bài này quen thuộc: Chặt nhị phân thông thường. (\(2^{31}=2.(2^{10})^3=2.1024^3\sim 2e9\) vừa đẹp).
    • Điểm đặc biệt của các bài toán interactive là ta "vừa xuất vừa nhập". Tức là ta in ra một đáp án bất kì, và sau đó hệ thống sẽ trả lại ta một kết quả, và nhiệm vụ của ta là nhập kết quả này để đưa ra những hoạt động tiếp theo ... (đoạn này có vẻ khó hiểu, nên bạn có thể bỏ qua, xem trực tiếp phần code luôn cũng được).
    • Dưới đây là lời giải của mình, các bạn có thể tham khảo.
    C++
    #include<bits/stdc++.h>

using namespace std;
#define ll long long 
int main() {
    ll l = 1, r = (ll)(2e9),mid;
    while (1) {
         mid = (l + r ) / 2;
        cout<<mid<<'\n';
        string s;
        cin>>s;
        if(s=="SMALLER")
            r = mid - 1;
        else if (s=="BIGGER")
            l = mid+1;
        else break;
    }

    return 0;
}
    • P/s: Ở trên cái đề là "HOLA" nhé, không phải "BINGO" (vì mình đã test rồi).
    • Nếu có gì khó hiểu hoặc sai , mọi người cứ comment nhé.

    • 0
      SPyofgame    5:17 p.m. 25 Tháng 6, 2020

      Em tưởng mình nên sài endl thay cho '\n' trong trường hợp này để tránh Idleness Limit Exceed :v


      • 0
        vinhntndu    5:19 p.m. 25 Tháng 6, 2020

        endl mới hay TLE hơn '\n' 😃


        • 0
          SPyofgame    5:21 p.m. 25 Tháng 6, 2020

          Nhưng interative-problem thì \n có thể ILE trong khi endl thì không mà anh :v


          • 0
            vinhntndu    5:22 p.m. 25 Tháng 6, 2020

            cứ hỏi mấy ông 12TH đi, chắc mấy ông còn cay vụ endl và '\n' lắm


            • 0
              SPyofgame    5:33 p.m. 25 Tháng 6, 2020

              lmao endl gồm cả '\n' lẫn std::flush() nên chậm là đúng :v


              • 0
                cuom1999    10:49 a.m. 26 Tháng 6, 2020

                Trên Codeforces thì phải flush (bằng endl chẳng han). Nhưng bên này thì k cần.


                • 0
                  SPyofgame    10:49 a.m. 26 Tháng 6, 2020

                  Giờ em mới biết, trước giờ em tưởng interactive luôn phải flush :v Thanks anh

      5 bình luận nữa