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/