Hướng dẫn giải của Chơi game
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 làm lời giải.
Nộp code mẫu trước khi tự giải được bài tập là một hành vi có thể bị ban.
Tác giả:
- Cách ~1~: Lưu trạng thái màn hình và vị trí cuối cùng của trái banh ở mỗi lần quay. Độ phức tạp ~O(K \times N^2)~
- Cách ~2~: Nhận xét thấy chỉ có ~4~ trạng thái của màn hình, vì vậy có thể tính trước ~4~ trạng thái này, mỗi lần quay chỉ tính vị trí rơi của trái banh. Độ phức tạp ~O(N^2+ N \times K)~
- Cách ~3~: Bổ sung thêm việc tính trước vị trí rơi của trái banh ở mỗi điểm ban đầu trên màn hình ứng với mỗi trạng thái của màn hình (~4~ trạng thái). Việc tính trước này mất ~O(N^2)~ nếu dùng quy hoạch động. Như vậy độ phức tạp ~O(N^2+ K)~
Bình luận