BAHT - Đổi Tiền BAHT
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: ami

Các bạn hẳn đã quen với bài toán đổi tiền quen thuộc. Ami có các đồng tiền ฿25, ฿10, ฿5 và ฿1. ฿ là kí hiệu đồng baht của Thái Lan. Nếu Ami có ฿x, Ami có thể đổi ฿x thành các đồng tiền có mệnh giá trên, sao cho tổng mệnh giá các đồng tiền chính bằng x.

Ví dụ Ami  có ฿6,  có thể dùng 1 đồng ฿5 và 1 đồng ฿1 hoặc 6 đồng ฿1.

Ami có rất nhiều tiền. Do đó, với các số i từ 0 đến k, các bạn cần tìm xem, có bao nhiêu giá trị i mà tồn tại 1 cách đổi ฿i thành các đồng tiền ฿25, ฿10, ฿5 và ฿1 sao cho không dùng quá x đồng tiền.

Dữ liệu vào

Gồm 2 số nguyên dương x và k (x , k ≤ 1015)

Dữ liệu ra

Một số nguyên là số giá trị i thoả mãn yêu cầu. 

Ví dụ

  • input
    1 30
    output
    5

Giải thích

Các giá trị i là 5 10 25 và 1.

Với ฿0, chỉ có 1 cách đổi duy nhất : không dùng đồng nào.

Với ฿1, chỉ có 1 cách đổi duy nhất : dùng 1 đồng ฿1.

Với ฿5, có thể đổi thành 1 đồng ฿5, 5 đồng ฿1.

Với ฿25, có thể đổi thành 5 đồng ฿5, 25 đồng ฿1, 1 đồng ฿25, ...

Với ฿10, có thể đổi thành 10 đồng ฿1, 1 đồng ฿10, 2 đồng ฿5.

Có thể thấy mỗi giá trị trên đều có cách đổi chỉ dùng không quá 1 đồng tiền.

Back to Top