Hướng dẫn giải của Chuồng Bò Tròn

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: huunguyen

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

Tiền xử lý: Sàng số nguyên tố đến $5 \times 10^{6}$ .
Với mỗi giá trị $v$ , tính $min\_turns [v]$ : số lượt tối thiểu để giảm $v$ về 0.
Phòng quyết định là phòng có $⌊ min\_turns / 2 ⌋$ nhỏ nhất (kết thúc sớm nhất).
Nếu $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)$ .

Bình luận

Không có bình luận tại thời điểm này.