영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
시간 제한 1초 · 메모리 제한 512 MB
Problem
There are n chairs arranged in a circle. Each chair is either red or blue. The chairs are numbered 1, 2,…, n; chairs i and i+1 are next to each other for all 1 ≤ i ≤ n. Here chair n+1 refers to chair 1.
Your task is to find two chairs that have the same color and are next to each other.
To do this, you can ask questions: you can choose a chair and you will be told the color of that chair.
Interaction
This is an interactive problem. Your code will interact with the grader using standard input and output. You should start by reading a single integer n: the number of chairs.
On your turn, you can print one of the following:
- "? i", where 1 ≤ i ≤ n: ask the color of chair i. The grader will return
RorBfor red or blue. - "! i": report that chairs i and i+1 have the same color. Your program must terminate after this.
Each line should be followed by a line break. You must make sure the output gets flushed after printing each line.
Constraints
- 3 ≤ n ≤ 2 · 10^5, n is odd
- you can ask at most 20 questions of type ?
Example
5
? 1
R
? 2
B
? 3
B
! 2