Số bí mật của Dumbledore

Điểm: 4,00 (OI)

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

Python 3 5.0s

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

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Thầy Dumbledore đã chọn một số nguyên bí mật $x$ trong khoảng từ $1$ đến $n$ .

Bạn có thể đặt câu hỏi theo định dạng:

? y

Thầy Dumbledore sẽ trả lời:

YES nếu $x \leq y$
NO nếu $x > y$

Sau khi tìm ra đáp án, in ra:

! x

Dữ liệu vào

Dòng đầu tiên chứa số nguyên $n$ .

Dữ liệu ra

Để hỏi: ? y

Để trả lời: ! x

Sau mỗi truy vấn, bạn phải flush output.

Ràng buộc

$1 \leq n \leq 10^{9}$
Bạn được hỏi tối đa $30$ câu hỏi

Ví dụ

Input	Output
10
	? 5
NO
	? 8
YES
	? 6
NO
	? 7
YES
	! 7

Ghi chú

Trong ví dụ, $x = 7$ :

$7 > 5$ nên trả lời NO
$7 \leq 8$ nên trả lời YES
$7 > 6$ nên trả lời NO
$7 \leq 7$ nên trả lời YES → tìm được đáp án

Tham khảo: Hướng dẫn giải bài tập Interactive

Bình luận

Không có bình luận tại thời điểm này.