Rút tiền

Tác giả:

Dạng bài

Điểm: 777 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

An là một đại gia có tiếng trong làng và hiện tại anh ấy đang có \(n\) đô la trong tài khoản ngân hàng. Vì sợ bị các hacker lừa đảo rút hết tiền của mình (do thế giới ngày càng phức tạp) nên anh ấy quyết định đi rút tiền mặt.
Cụ thể như sau, ở cây ATM của ngân hàng chỉ cho phép anh ấy mỗi lần rút tiền chỉ có một trong các mệnh giá như sau: \(1,5,10,20,100\) đô la mà thôi.
Hỏi anh ấy cần ít nhất bao nhiêu lần rút thì hết toàn bộ số tiền anh ấy có trong ngân hàng ?

Input

Dòng đầu tiên chứa số nguyên dương \(t(1\le t\le 100)\) - Thể hiện số testcase
\(t\) dòng tiếp theo, mỗi dòng chứa số nguyên dương \(n(1\le n\le 10^9)\) thể hiện số tiền An có trong ngân hàng

Output

Ứng với mỗi giá trị của \(n\), hãy in kết quả ra màn hình.

Example

Test 1

Input

2
125
43

Output

3
5

Note

Ứng với \(n=125\), thì 3 lần rút lần lượt là: \(100,20,5\)
Ứng với \(n=43\), thì 5 lần rút lần lượt là: \(20,20,1,1,1\)

Bình luận

-1

t = int(input())
a = []
money = [100,20,10,5,1]
for i in range(t):
    n = int(input())
    ans = 0
    for z in range(5):
        ans += n//money[z]
        n -= money[z]*(n//money[z])
    a.append(ans)
for i in range(len(a)):
    print(a[i])

2 bình luận nữa