Chuồng Bò Tròn

Lời giải: Circular Barn

Hướng tiếp cận

Phân tích trò chơi dựa trên lý thuyết trò chơi và tính chất mod 4.

Nhận xét quan trọng

Với một phòng: Farmer John thắng khi và chỉ khi $a_1$ không chia hết cho 4. Chiến lược tối ưu liên quan đến việc cả hai chọn giá trị sao cho tổng hai lượt đồng dư 0 mod 4.

Thuật toán

1. Tiền xử lý: Sàng số nguyên tố đến $5\times {10}^6$.
2. Với mỗi giá trị $v$, tính $\text{min\_turns}[v]$: số lượt tối thiểu để giảm $v$ về 0.
3. Phòng quyết định là phòng có $\lfloor \text{min\_turns}/2\rfloor$ nhỏ nhất (kết thúc sớm nhất).
4. Nếu $\text{min\_turns}$ của phòng đó là lẻ thì John thắng, ngược lại Nhoj thắng.

Độ phức tạp

• Tiền xử lý: $O(M\log \log M)$ với $M=5\times {10}^6$.
• Mỗi bộ test: $O(N)$.