Chạy Trên Vòng Tròn

Lời giải: Bò Chạy

Hướng tiếp cận

Bài toán là cây AND/OR: FJ (OR node) chọn B hoặc T để đảm bảo thắng, Bessie (AND node) cần cả hai lựa chọn đều dẫn đến thắng. Giải đệ quy từ trên xuống với short-circuit evaluation ngẫu nhiên để tối ưu hóa thực tế.

Nhận xét quan trọng

1. Cấu trúc cây AND/OR với chiều sâu $N\le 14$: tại mỗi vòng, FJ chọn (OR), Bessie phản ứng (AND). Tổng số nút cây là $O(4^N)$ nhưng short-circuit cắt tỉa rất mạnh.
2. FJ muốn chiến lược từ điển nhỏ nhất: thử B trước (vì B < T). Nếu B đảm bảo thắng thì chọn B; ngược lại thử T.
3. Công thức cập nhật vị trí: $R\leftarrow (R\times (1+X_{top})+X_{bot})modM$. Dùng __int128 để tránh tràn số khi $R$ và $X$ lên tới ${10}^9$.
4. Ngẫu nhiên hóa thứ tự kiểm tra lựa chọn của Bessie giúp tăng tốc tìm kiếm (nếu một lựa chọn thua, trả về sớm).

Thuật toán

1. Đọc $N$, $M$, $K$, chuỗi nước đi của Bessie, và 8 giá trị lá bài mỗi vòng.
2. Định nghĩa check_fj(round, R, fj): kiểm tra nếu FJ chọn fj (0=T, 1=B), thì với mọi lựa chọn của Bessie, kết quả đều thắng (AND). Nếu là vòng cuối kiểm tra winning(R_new), ngược lại đệ quy can_win(round+1, R_new).
3. Định nghĩa can_win(round, R): thử B trước (fj=1), nếu check_fj trả về true thì thắng; ngược lại thử T.
4. Mô phỏng thực tế: tại vòng $i$, thử B trước; nếu check_fj(i, R, 1) thì ghi 'B', theo dõi nước đi thực của Bessie để cập nhật $R$; ngược lại ghi 'T'.
5. In chuỗi nước đi của FJ.

Độ phức tạp

• Thời gian: $O(2^N)$ trong trường hợp xấu nhất (cây AND/OR đầy đủ), nhưng short-circuit cắt tỉa mạnh trong thực tế
• Bộ nhớ: $O(N)$ (chiều sâu đệ quy)