Editorial for Đổi tiền
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.
Submitting an official solution before solving the problem yourself is a bannable offence.
Nếu \(S\) giới hạn nhỏ lại thì bài này là bài toán đổi tiền cơ bản bằng QHĐ, Nhưng do \(S\) lớn nên QHĐ sẽ không thể thực hiện được.
Điều đó khiến ta nghĩ theo một hướng khác.
Nhận xét khi \(S\) cực lớn luôn thì ta dùng nhiều tờ lớn nhất nhất để rút cho đến khi thực sự cần đến những tờ nhỏ (do tiền nhỏ mà \(S\) lại lớn quá). Do đó tham lam loại cuối cùng.
Sau đó, khi \(S\) nhỏ lại thì QHĐ tìm giá trị đó. Có thể khởi tạo \(F[.]\) khoảng 1 giây (chạy \(10^6\) cho hai vòng lặp)
Nguồn: https://vnspoj.github.io/
Comments