Bài 42: Đổi tiền 2

Bài 42:
Cho N (đồng), muốn đổi tiền chỉ gồm các tờ tiền mệnh giá 500, 200 và 100.
Hãy đưa ra tổng số tờ tiền nhiều nhất và ít nhất có thể có được
BAI42.INP BAI42.OUT
1000 2
10
❖ Thuật toán:
đặt rmax = 0, rmin = n
Thuật toán: Vét cạn
Cách 1: Độ phức tạp của thuật toán O(N3/107)
Gọi a là số lượng tờ tiền 500 rút được (0 ≤ a ≤  N/500)
Gọi b là số lượng tờ tiền 200 rút được (0 ≤ b ≤  N/200)
Gọi c là số lượng tờ tiền 100 rút được (0 ≤ c ≤  N/100)
Đổi N đồng theo yêu cầu đề bài: 500*a + 200*b + 100*c = N
For(a, 0, N/500)
  For(b,0, N/200)
    For(c,0,N/100)
        If (500*a + 200*b + 100*c == N)
                 so sánh rồi cập nhật giá trị rmax, rmin
đưa rmax, rmin ra
Cách 2: Độ phức tạp của thuật toán O(N2/105)
Đổi N đồng theo yêu cầu đề bài: Điều kiện (N – (500*a + 200*b)) % 100 == 0)
For(a, 0, N/500)
  For(b,0, N/200)
             p = N – (500*a + 200*b);            
             If (p % 100 == 0 and p > 0 or p == 0)
                 so sánh rồi cập nhật giá trị rmax, rmin
đưa rmax, rmin ra

Video bải giảng:

Code:

n = int(input())
p = False
rmin = n
rmax = 0
for a in range(n // 500 + 1):
    for b in range(n // 200 + 1):
        for c in range(n // 100 + 1):
            if a * 500 + b * 200 + c * 100 == n:
                p = True
                temp = t100 + t200 + t500
                if temp > rmax:
                    rmax = temp
                if temp < rmin:
                    rmin = temp
if not p:
    print('NONE')
else:
    print(rmin)
    print(rmax)

Code:

n = int(input())
p = False
rmin = n
rmax = 0
for a in range(n // 500 + 1):
   for b in range(n // 200 + 1):
       m = n - (a * 500 + b * 200)
       if m % 100 == 0 and m > 0 or m == 0:
           p = True
           temp = a + b + m // 100
           if temp > rmax:
               rmax = temp
           if temp < rmin:
               rmin = temp
if not p:
   print('NONE')
else:
   print(rmin)
   print(rmax)