Ôn tập cuối năm

Bạn chưa đăng nhập. Vui lòng đăng nhập để hỏi bài
Thanh Bình

DPRCCOI - ĐỔI TIỀN

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

 

     Ở AnLuuLand họ có một hệ thống tiền tệ rất kỳ lạ. Mỗi đồng tiền vàng của AnLuuLand có một số nguyên được viết trên đó. Một đồng n có thể được trao đổi trong ngân hàng thành ba đồng tiền: n div 2, n div 3 và n div 4.

     Bạn cũng có thể đổi tiền AnLuuLand thành đô la Mỹ. Tỷ giá hối đoái là 1:1. Nhưng bạn không thể mua tiền AnLuuLand.

     Bạn có đồng vàng ghi số n. Số đô la Mỹ tối đa bạn có thể đổi được là bao nhiêu?

Dữ liệu nhập:

- Dữ liệu nhập: sẽ chứa một số trường hợp thử nghiệm (không quá 10).

- Mỗi testcase là một dòng duy nhất có số n (0 ≤ n ≤ 109). Đó là số được viết trên đồng tiền của bạn.

Kết quả:

- Đối với mỗi trường hợp thử nghiệm xuất ra một dòng duy nhất, chứa số đô la Mỹ tối đa bạn có thể kiếm được.

Ví dụ

input

0
1
2
3
4
5
12
32
12345
7985
1000000000

output

0
1
2
3
4
5
13
35
21629
13137
4243218150

Chú thích:

- Bạn có thể thay đổi 12 thành 6, 4 và 3, sau đó đổi chúng thành $6 + $4 + $3 = $13.

- Nếu bạn thử đổi xu 2 thành 3 đồng xu nhỏ hơn, bạn sẽ nhận được 1, 0 và 0, và sau đó bạn có thể nhận được không quá 1 đô la trong số đó. Tốt hơn là chỉ cần thay đổi 2 đồng tiền trực tiếp thành 2 đô la.

Nguyễn Hoàng Duy
27 tháng 6 2023 lúc 16:57

def exchange(n, memo):
    if n in memo:
        return memo[n]
    if n == 0:
        return 0
    max_exchange = max(n, exchange(n // 2, memo) + exchange(n // 3, memo) + exchange(n // 4, memo))
    memo[n] = max_exchange
    return max_exchange

while True:
    try:
        n = int(input())
        memo = {}
        print(exchange(n, memo))
    except:
        break
    


Các câu hỏi tương tự
Thanh Bình
Xem chi tiết
Thanh Bình
Xem chi tiết
Hoàng Yến Nghiêm
Xem chi tiết
siêu phẩm zed
Xem chi tiết
Thanh Bình
Xem chi tiết
Phan Văn Thái Dương
Xem chi tiết
DuaHaupro1
Xem chi tiết
DuaHaupro1
Xem chi tiết
Tài Tuệ Lê
Xem chi tiết