Cân Đĩa Tìm Xu Giả
Points
20
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Đây là bài toán mô phỏng tương tác (không tương tác trực tiếp — toàn bộ dữ liệu được cho trước).
Có $N$ đồng xu được đánh số từ $1$ đến $N$, trong đó có đúng một đồng xu giả mang số hiệu $X$ nặng hơn các đồng xu thật còn lại (các đồng xu thật có khối lượng bằng nhau). Ta sử dụng chiến lược cân chia ba tối ưu trên đoạn ứng viên $[L, R]$ (ban đầu $L = 1, R = N$):
- Khi $L < R$, gọi $S = R - L + 1$ là số đồng xu đang xét và $k = \lfloor S / 3 \rfloor$ (nếu $S = 2$ thì $k = 1$, thực chất vẫn là $\lfloor S / 3 \rfloor$ chỉ bằng $0$ khi $S=2$ nên quy ước $k = \max(1, \lfloor S / 3 \rfloor)$).
- Ta đặt $k$ đồng xu $[L, L+k-1]$ lên đĩa trái và $k$ đồng xu $[L+k, L+2k-1]$ lên đĩa phải; phần còn lại $[L+2k, R]$ để ngoài.
- Nếu đĩa trái nặng hơn, kết quả là
LEFTvà đoạn mới là $[L, L+k-1]$. - Nếu đĩa phải nặng hơn, kết quả là
RIGHTvà đoạn mới là $[L+k, L+2k-1]$. - Nếu hai đĩa thăng bằng, kết quả là
EQUALvà đoạn mới là $[L+2k, R]$. - Quá trình dừng lại khi $L = R$.
Hãy mô phỏng các lần cân và in ra kết quả từng bước.
Dữ liệu vào
- Một dòng chứa hai số nguyên $N$ và $X$ ($1 \le X \le N \le 10^9$).
Dữ liệu ra
- Dòng đầu tiên ghi số nguyên $K$ là số lần cân.
- $K$ dòng tiếp theo, mỗi dòng ghi
RES L Rtrong đóRESlàLEFT,RIGHT, hoặcEQUAL, vàL,Rlà đoạn ứng viên mới sau lần cân đó.
Ví dụ
| Input | Output |
|---|---|
| 9 5 | 2 RIGHT 4 6 RIGHT 5 5 |
Giới hạn
- $1 \le X \le N \le 10^9$
Community Discussion