Lâu lắm mới dám quay lại làm Codeforces. Nhưng cái vấn đề vẫn là làm nhiều vẫn ngu, vô thưởng vô phạt.
Tóm tắt đề bài: Raze và Breach đang chơi một trò chơi với nhau: cho một số nguyên có n chữ số, mỗi người lần lượt đánh dấu một chữ số trong số nguyên đó. Biết rằng Raze chỉ được đánh dấu các chữ số ở vị trí lẻ và Breach chỉ được đánh dấu các chữ số ở vị trí chẵn, trò chơi dừng lại khi chỉ còn duy nhất một chữ số cuối cùng chưa được đánh dấu. Nếu chữ số cuối cùng đó là số lẻ thì Raze thắng, ngược lại thì Breach thắng.
Biết rằng Raze chơi lượt đầu tiên và hai người chơi tối ưu nhất có thể. Tìm xem ai là người thắng?
Hướng giải: Dù cả hai người chơi tối ưu nhất có thể thì người chơi lượt cuối cùng (trước khi chỉ còn một chữ số chưa được đánh dấu) là người quyết định kết quả game. Khi đó con số cuối cùng còn lại sẽ nằm ở vị trí của người chơi không-chơi-lượt-cuối-cùng, và tùy thuộc vào con số đó mà ta đưa ra kết quả.
Nói đến đây thì nghe có vẻ khó nhưng quá trình giải có thể tóm tắt như sau:
- Kiểm tra xem số lượng chữ số chẵn hay lẻ.Điều này rất quan trọng, vì nếu số lượng chữ số chẵn và theo ta đã biết là Raze đi trước, thì ở lượt cuối cùng là lượt của Breach và ngược lại, nếu số lượng chữ số lẻ thì lượt cuối là lượt của Raze. Như mình đã nói ở trên, người chơi cuối cùng sẽ quyết định kết quả cả game.
- Với mỗi trường hợp số lượng chữ số chẵn hoặc lẻ, kiểm tra xem người chơi lượt cuối cùng có ít nhất một chữ số có lợi cho mình hay không?Ngắn gọn hơn: ví dụ Raze là người chơi lượt cuối cùng thì ta kiểm tra xem ở những vị trí Raze có thể chọn có tồn tại số lẻ nào hay không, nếu có thì Raze thắng.
D1. Sage's Birthday (Easy Version)
Tóm tắt đề bài: Có n khối cầu băng được xếp thành một hàng dọc và được đánh số lần lượt từ 1 đến n, từ trái qua phải. Mỗi khối cầu băng có giá tiền là một số nguyên dương, ở version này thì không có khối cầu băng nào đồng giá. Một khối cầu băng được gọi là rẻ nếu giá của nó nhỏ hơn hai khối cầu băng kề cạnh bên trái và bên phải. Lưu ý rằng hai khối cầu băng ngoài cùng sẽ không rẻ.
Biết rằng bạn có thể sắp xếp lại thứ tự các khối cầu băng theo thứ tự mà bạn thích, tìm số lượng khối cầu băng rẻ tối đa mà bạn có thể mua, chỉ ra thứ tự các khối cầu băng được sắp xếp để có được số lượng khối cầu rẻ tối đa đó.
Hướng giải: Algoritham(*) thần thánh: sort n khối cầu theo thứ tự tăng dần, sau đó in các khối cầu theo hình gợn sóng. Có thể chứng minh được số lượng khối cầu tối đa có thể mua luôn bằng n / 2 (làm tròn dưới, nếu n lẻ) và (n / 2) - 1 (nếu n chẵn).
Chú ý câu văn in đậm màu đỏ bên trên. Trong trường hợp n chẵn, chỉ cần tráo vị trí hai khối cầu cuối cùng để khối cầu đắt hơn ở ngoài cùng. Khi đó số lượng khối cầu tối đa có thể mua sẽ là (n / 2) - 1.
Happy coding!
(*) Algoritham: "greedy algorithm nên được gọi là algoritham" - Tươi Image APCS
No comments:
Post a Comment