Ghế Màu

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.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

Có $n$ chiếc ghế xếp thành vòng tròn, đánh số từ $1$ đến $n$ . Ghế $i$ kề với ghế $i + 1$ (với $1 \leq i < n$ ) và ghế $n$ kề với ghế $1$ . Mỗi ghế được tô màu đỏ (R) hoặc xanh (B).

Nhiệm vụ của bạn là tìm hai ghế kề nhau có cùng màu.

Giao thức tương tác

Đây là bài toán tương tác. Chương trình của bạn giao tiếp với hệ thống đánh giá thông qua đầu vào/ra chuẩn.

Đầu tiên, chương trình đọc số nguyên $n$ .

Sau đó, bạn có thể thực hiện hai loại thao tác:

? i (với $1 \leq i \leq n$ ): Hỏi màu của ghế thứ $i$ . Hệ thống trả lời R (đỏ) hoặc B (xanh).
! i: Khai báo rằng ghế $i$ và ghế kế tiếp (ghế $i + 1$ , hoặc ghế $1$ nếu $i = n$ ) có cùng màu. Chương trình kết thúc sau thao tác này.

Bạn được phép hỏi tối đa $20$ câu hỏi dạng ?.

Quan trọng: Sau mỗi lần in ra, bạn phải flush output:

C++: cout << endl; hoặc cout.flush();
Python: print(..., flush=True)

Ràng buộc

$3 \leq n \leq 2 \cdot 10^{5}$
$n$ là số lẻ
Số truy vấn tối đa: $Q \leq 20$

Ví dụ

Chương trình	Hệ thống	Giải thích
	5	$n = 5$ ghế. Màu: R B B R B
? 1	R	Ghế 1 màu đỏ
? 2	B	Ghế 2 màu xanh
? 3	B	Ghế 3 màu xanh
! 2		Ghế 2 và ghế 3 đều xanh. Đúng!

Ghi chú

Vì $n$ là số lẻ, luôn tồn tại ít nhất một cặp ghế kề nhau có cùng màu (nguyên lý chuồng bồ câu: không thể tô xen kẽ hoàn hảo trên vòng tròn có số lẻ đỉnh).

Bình luận

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