Cân Đĩa Tìm Xu Giả

Buổi 63 — Interactive & Constructive
Points
20
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề 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à LEFT và đoạn mới là $[L, L+k-1]$.
  • Nếu đĩa phải nặng hơn, kết quả là RIGHT và đoạn mới là $[L+k, L+2k-1]$.
  • Nếu hai đĩa thăng bằng, kết quả là EQUAL và đ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 R trong đó RES là LEFT, RIGHT, hoặc EQUAL, và L, R là đ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$
Draft saved