Đoán Mảng

Điểm: 0,10 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Input: stdin

Output: stdout

Dạng bài

Ngôn ngữ cho phép

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho một mảng nguyên ~a[1..n]~ thỏa mãn:

~a[1]~ là giá trị nhỏ nhất của mảng,
~a[n]~ là giá trị lớn nhất của mảng,
với mọi ~2 \le i \le n~, ta có ~|a[i] - a[i-1]| = 1~.

Bạn được cho thêm một tham số ~k~ và biết chắc rằng tồn tại ít nhất một vị trí ~id~ sao cho ~a[id] = k~. Nhiệm vụ của bạn là tìm ra một vị trí như vậy bằng cách thực hiện tối đa 16 lượt hỏi.

Input

Ban đầu, bạn cần đọc vào hai số nguyên ~n,~ ~k~ ~(1 \le n \le 10000)~ — kích thước mảng và giá trị cần tìm.

Interaction

Để thực hiện truy vấn, in ra một số nguyên id ~(1 \le id \le n)~ và đọc vào một chuỗi — phản hồi của máy chấm. Lưu ý hãy flush luồng ra chuẩn sau mỗi dòng được in ra bằng lệnh fflush(stdout) hoặc std::endl trong ngôn ngữ lập trình C++ hoặc các câu lệnh tương ứng ở các ngôn ngữ lập trình khác.

Máy chấm sẽ phản hồi một trong ba chuỗi:

BIGGER — tức là ~a[id] < k~.
SMALLER — tức là ~a[id] > k~.
HOLA — tức là ~a[id] = k~. Chương trình của bạn phải kết thúc sau khi nhận được phản hồi này.

Nếu bạn hỏi quá 16 lượt mà vẫn chưa nhận được HOLA, chương trình của bạn sẽ nhận được kết quả Wrong Answer.

Sample Input 1

BIGGER
SMALLER
HOLA

Sample Output 1

3
5
4

Notes

Giả sử mảng ẩn là ~[2,3,4,5,6,7]~ và ~k = 5~. Máy chấm in: ~6~ ~5~.

Truy vấn 3: ~a[3] = 4 < 5~, máy chấm trả về BIGGER.
Truy vấn 5: ~a[5] = 6 > 5~, máy chấm trả về SMALLER.
Truy vấn 4: ~a[4] = 5 = k~, máy chấm trả về HOLA. Dừng chương trình.

Bình luận

Bình luận

Hãy đọc nội quy trước khi bình luận.

pppssslc đã bình luận lúc 22, Tháng 3, 2026, 15:37

UNOFFICAL SOLUTION

Nhận xét:

Nếu tồn tại ~a[i] < k < a[j] (i < j)~ thì chắc chắn tồn tại ~i < id < j~ thỏa mãn ~a[id] = k~.

Hint:

Binary search

Code mẫu:

// Author: pppssslc
// Date: 22/03/2026
#include<bits/stdc++.h>

using namespace std;

template<class X, class Y> void mini(X &x, const Y &y){
  x = min(x, y);
}

template<class X, class Y> void maxi(X &x, const Y &y){
  x = max(x, y);
}

typedef string str;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef double db;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pldld;
typedef pair<db, db> pdd;
typedef pair<char, char> pcc;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<char> vc;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> vll;
typedef vector<vector<char>> vcc;
typedef map<int, int> mpii;
typedef map<ll, ll> mpll;
typedef set<int> si;
typedef set<ll> sl;
typedef complex<ld> cd;

#define se second
#define fi first
#define Rep(i, l, r, x) for(int i = l; i < (int)r; i += x)
#define Repd(i, l, r, x) for(int i = l; i > (int)r; i -= x)
#define For(i, l, r, x) for(int i = l; i <= (int)r; i += x)
#define Ford(i, l, r, x) for(int i = l; i >= (int)r; i -= x)
#define Fore(x, a) for(auto x: a)
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define ins insert
#define era erase
#define upb upper_bound
#define lwb lower_bound
#define all(a) a.begin(), a.end()

const db PI = acos(-1);
const ll inf = 1e18 + 1;
const int mod = 1e9 + 7;
const int maxn = 1e3 + 1;

signed main(){
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr); cout.tie(nullptr);
  if(fopen("D:/inp.txt", "r"))
      freopen("D:/inp.txt", "r", stdin),
      freopen("D:/out.txt", "w", stdout);
  int n, k; cin >> n >> k;
  int l = 1, r = n;
  while(l <= r){
      int m = l + r >> 1;
      cout << m << endl;
      str inp; cin >> inp;
      if(inp == "BIGGER") l = m + 1;
      else if(inp == "SMALLER") r = m - 1;
      else break;
  }
  cerr << "TIME ELAPSED: " << 1.0 * clock() / CLOCKS_PER_SEC << "s.\n";
  return 0;
}