Giúp giải đề HSG tỉnh tìm số lượng tờ tiền nhỏ nhất thoả mãn

[synav]

Nhờ mn giúp em, em nên giải theo cách não v? Em dùng 7 hàm for nhưng quá chậm ạ! MN gợi ý giúp em ạ

[noname00 (HK boy)]

Giả sử có danh sách mệnh giá menh_gia = {1, 2, 5, 10, 20, 50, 100} và danh sách so_luong biểu thị có so_luong[i] tờ tiền có mệnh giá menh_gia[i].

Ta có menh_gia[1] < menh_gia[2] < ... < menh_gia[7], theo giả thiết thì ta cần phải đảm bảo so_luong[1] >= so_luong[2] >= ... >= so_luong[7] > 0.

Do vậy đáp án đơn giản nhất chính là

• so\_luong[7] = \left\lfloor \dfrac{N}{\sum_{i=1}^{7} menh\_gia[i]} \right\rfloor

• so\_luong[6] = \left\lfloor \dfrac{N - menh\_gia[7] * so\_luong[7]}{\sum_{i=1}^{6} menh\_gia[i]} \right\rfloor

• so\_luong[5] = \left\lfloor \dfrac{N - menh\_gia[7] * so\_luong[7] - menh\_gia[6] * so\_luong[6]}{\sum_{i=1}^{5} menh\_gia[i]} \right\rfloor

• …