Editorial for Chơi game
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
- 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)~
Comments