Số bí mật của Snape

Điểm: 1,00 (OI)

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

Python 3 5.0s

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

Input: stdin

Output: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

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

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

Mục tiêu của bạn là xác định chính xác giá trị của $x$ .

Giao thức tương tác

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

? y

trong đó $1 \leq y \leq n$ . Thầy Snape sẽ trả lời:

YES nếu $x$ chia hết cho $y$
NO nếu ngược lại

Quy tắc đặc biệt

Giới hạn câu hỏi: Bạn được hỏi tối đa $25$ câu hỏi.

Tối đa một lời nói dối: Thầy Snape được phép nói dối nhiều nhất một lần. Cụ thể:

Đúng một câu trả lời có thể sai
Tất cả các câu trả lời còn lại đều đúng với $x$ đã chọn

Thầy Snape biến hóa: Thầy Snape không cố định $x$ từ đầu. Sau mỗi câu hỏi, Thầy Snape có thể thay đổi $x$ , miễn là:

Tất cả các câu trả lời trước đó (trừ tối đa một lời nói dối) vẫn nhất quán với $x$ mới

Nhiệm vụ

Sau khi hỏi xong, in ra câu trả lời cuối cùng:

! x

Câu trả lời này không tính vào giới hạn câu hỏi.

Quan trọng: Vì Thầy Snape thích biến hoá, bạn phải đảm bảo rằng sau tất cả các câu hỏi, chỉ còn duy nhất một giá trị $x$ thỏa mãn các câu trả lời (cho phép tối đa 1 câu trả lời sai). Nếu còn nhiều hơn một giá trị khả thi, Thầy Snape sẽ chọn giá trị khác với câu trả lời của bạn.

Dữ liệu vào

Dòng đầu tiên chứa một 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 20$
Bạn được hỏi tối đa $25$ câu hỏi

Ví dụ

Input	Output
10
	? 2
YES
	? 3
NO
	? 4
YES
	? 5
YES
	? 7
NO
	? 8
NO
	? 10
NO
	! 4

Ghi chú

Trong ví dụ trên, Thầy Snape đã nói dối 1 lần ở câu hỏi ? 5. Thực tế $x = 4$ không chia hết cho 5, nhưng Thầy Snape trả lời YES.

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.