Đổi Tiền (DPRCCOI)

Nguồn: VinhDinhCoder Độ khó: Trung bình Quy hoạch động Đệ quy có nhớ Map

Đề bài

DPRCCOI – Đổi tiền

Ở 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 \text{ div } 2$, $n \text{ div } 3$ và $n \text{ div } 4$. Với $\text{div}$ là phép chia lấy nguyên.

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 vào: 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$. Đó 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.

Ràng buộc: $0 \le n \le 10^9$.

Ví dụ – input

0
1
2
3
4
5
12
32
12345
7985
1000000000

Ví dụ – output

0
1
2
3
4
5
13
35
21629
13137
4243218150

Lời mở đầu

Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇. Đây là một bài rất hay để thấy được sức mạnh của đệ quy có nhớ: chỉ thêm đúng 1 cái map vào code vét cạn là từ TLE thành AC luôn.

Trước tiên mình sẽ tóm tắt lại đề bài một cách đơn giản nhất để bạn nào chưa hiểu như sau. Bạn đang có 1 đồng tiền vàng giá trị $n$. Bạn có thể:

• Đổi 1 đồng $n$ thành 3 đồng tiền vàng có giá trị lần lượt là n / 2, n / 3 và n / 4 (trong C++ chính là phép chia nguyên đó anh em, chia làm tròn xuống nha; ví dụ 10 / 3 = 3). Các đồng mới lại có thể tiếp tục đem đi đổi như vậy.
• Hoặc đổi đồng tiền vàng sang đô la Mỹ với tỷ giá $1:1$, tức đồng tiền vàng giá trị $8$ đổi được $8$ đô la; tổng quát đồng giá trị $n$ đổi được $n$ đô la.

Đầu vào có tối đa 10 đồng tiền vàng (không cho trước là bao nhiêu đồng, cứ đọc đến hết), mỗi đồng có giá trị $0 \le n \le 10^9$; với mỗi đồng hãy in ra số đô la Mỹ tối đa có thể kiếm được.

Mình giải thích vài giá trị trong ví dụ để bạn nào chưa hiểu đề sẽ hiểu rõ:

• $n = 0$: nếu đổi thành 3 đồng con thì được $0/2 = 0$, $0/3 = 0$, $0/4 = 0$. Vậy có đổi hay giữ nguyên thì cũng chỉ được 0 đô la mà thôi.
• $n = 1$: đổi thành 3 đồng con thì được 3 đồng giá trị $0$. Vậy ta không đổi mà đem luôn đồng ban đầu đi đổi đô, được 1 đô la.
• $n = 12$: đổi thành 3 đồng con là $6$, $4$ và $3$. Đem 3 đồng này đổi sang đô la thì được $6 + 4 + 3 = $ 13 đô la, lời hơn giữ nguyên ($12$).
• $n = 32$: đổi thành 3 đồng con là $16$, $10$ và $8$. Ta tiếp tục đổi đồng $16$ ra thì được thêm 3 đồng con nữa là $8$, $5$ và $4$. Tổng cộng giờ ta có các đồng $\{8, 5, 4, 10, 8\}$, đổi hết sang đô la thì được $8 + 5 + 4 + 10 + 8 = $ 35 đô la.

32→16108→854108⇒35 $

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Cách 1Đệ quy vét cạn · 22/30 test (TLE)Cách 2Đệ quy có nhớ + map · AC

Cách 1Đệ quy vét cạn – thử mọi cách đổi

Cách làm đơn giản nhất của bài này chính là ta sẽ vét cạn nha, tức là ta sẽ thử mọi trường hợp có thể. Với 1 đồng xu có giá trị $n$ thì ta có đúng 2 lựa chọn:

• Đổi thẳng sang $n$ đô la.
• Hoặc đổi sang 3 đồng xu $n/2$, $n/3$, $n/4$. Vậy khi nào thì ta kiếm được nhiều đô la nhất từ 3 đồng xu đó? Dĩ nhiên là (số đô la tối đa kiếm được từ đồng $n/2$) + (số đô la tối đa kiếm được từ đồng $n/3$) + (số đô la tối đa kiếm được từ đồng $n/4$) đúng không? Vì 3 đồng xu này đổi độc lập với nhau, muốn tổng cả 3 được tối đa thì mỗi đồng cũng phải đổi ra được nhiều đô la nhất có thể.

Vậy số đô la tối đa đổi được từ đồng xu $n$ sẽ là $\max(n,\ \text{tối đa từ } n/2 + \text{tối đa từ } n/3 + \text{tối đa từ } n/4)$. Ta xây dựng hàm đệ quy như sau:

• Hàm: Try(n) trả về số đô la tối đa ta có thể đổi được từ đồng xu có giá trị $n$.
• Điều kiện dừng: khi n == 0 thì số đô la tối đa đổi được là $0$. Lý do ta chọn điều kiện dừng là $n = 0$ mà không phải số khác là vì một đồng xu khi tách ra sẽ bị chia cho 2, 3 hoặc 4. Cứ liên tục tách (tức là liên tục chia) thì cuối cùng chắc chắn chỉ còn đồng xu $0$. Vậy để tránh đệ quy vô hạn thì gặp đồng $0$ ta return 0 luôn, vì đồng $0$ đổi sang được $0$ đô la.
• Xử lý chạy: như phân tích ở trên, ta return max(n, Try(n / 2) + Try(n / 3) + Try(n / 4));

Công thức đệ quy

$\text{Try}(n) = \max\big(n,\ \text{Try}(n/2) + \text{Try}(n/3) + \text{Try}(n/4)\big)$, với $\text{Try}(0) = 0$.

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;

ll Try(ll n){
    if(n == 0){
        return 0;
    }
    return max(n, Try(n / 2) + Try(n / 3) + Try(n / 4));
}

int main(){
    // freopen("dprccoi.inp", "r", stdin);
    // freopen("dprccoi.out", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll n;
    while(cin >> n){
        cout << Try(n) << endl;
    }
    return 0;
}

import sys

def Try(n):
    if n == 0:
        return 0
    return max(n, Try(n // 2) + Try(n // 3) + Try(n // 4))

for tok in sys.stdin.read().split():
    n = int(tok)
    print(Try(n))

Giải thích 1 số chỗ trong code ở trên:

• while(cin >> n): vì đầu vào không cho biết trước có bao nhiêu đồng xu nên mình dùng cú pháp này để đọc tới khi hết dữ liệu thì thôi. Khi hết dữ liệu, cin >> n thất bại và vòng while dừng lại. Bản Python thì đọc hết bằng sys.stdin.read().split() rồi duyệt từng số.
• Code gốc của mình có 2 dòng freopen("dprccoi.inp", ...) / freopen("dprccoi.out", ...) để đọc ghi file. Khi nộp trên CLUE OJ (đọc/ghi chuẩn) thì các bạn để chúng ở dạng chú thích như trên là được; nếu đề thi yêu cầu đọc ghi file thì bỏ dấu // đi nhé.

Em bấm Tiếp trong khung chạy tay bên dưới để xem cây đệ quy được "bung" ra như thế nào. Để ý ô "Mỗi Try(x) đã bị gọi bao nhiêu lần": chỉ với $n = 32$ thôi mà nhiều hàm đã bị gọi đi gọi lại rồi.

C++▶ Chạy tay từng dòng codeCách 1: Try(n) = max(n, Try(n/2) + Try(n/3) + Try(n/4)), Try(0) = 0, không nhớ gì cả.

Dữ liệu vào (stdin) – sửa thoải mái12 32

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2#define endl '\n'

3using namespace std;

4typedef long long ll;

5

6ll Try(ll n){

7 if(n == 0){

8 return 0;

9 }

10 return max(n, Try(n / 2) + Try(n / 3) + Try(n / 4));

11}

12

13int main(){

14 // freopen("dprccoi.inp", "r", stdin);

15 // freopen("dprccoi.out", "w", stdout);

16 ios_base::sync_with_stdio(0);

17 cin.tie(0);

18 ll n;

19 while(cin >> n){

20 cout << Try(n) << endl;

21 }

22 return 0;

23}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: chỉ tốn bộ nhớ cho ngăn xếp đệ quy, độ sâu tối đa khoảng $\log_2 n \approx 30$ tầng, tức $O(\log n)$.
• Thời gian: mỗi lời gọi lại tách ra 3 lời gọi con, và cùng một giá trị bị tính đi tính lại rất nhiều lần. Mình đếm thử số lời gọi hàm Try: với $n = 32$ là $130$ lần, $n = 10^6$ là khoảng $9.6 \cdot 10^6$ lần, còn $n = 10^9$ là khoảng $1.5 \cdot 10^{10}$ lần!

Không gian$O(\log n)$

Thời giantăng cực nhanh theo $n$

Chỉ được 22/30 test

Với cách trên thì ta chỉ được 22/30 test, còn lại bị TLE. Đó là do test còn dễ chứ nếu giả sử các test đều có $n = 10^9$ thì code này sẽ bị TLE hết luôn nhé. Mình đo thử bản C++ chỉ với 1 đồng $n = 10^9$ đã chạy hơn 30 giây.

Cách 2Đệ quy có nhớ (quy hoạch động top-down) với map

Giờ ta sẽ đến với cách làm có thể giúp ta AC (accepted – được chấp nhận) bài này nha.

Ta sẽ nhận ra rằng bài này có các bài toán con trùng lặp. Vậy dựa vô đâu mà ta biết sẽ có bài toán con trùng lặp? Giờ ta lấy tạm $n = 1600$ đi: ta tách ra làm 3 đồng xu là $800$, $533$ và $400$. Bây giờ ta tách đồng xu $800$ ra nữa, ta sẽ được $400$, $266$, $200$. Anh em thấy trùng rồi chứ, ta đã tách được 2 đồng xu $400$ kìa.

Tổng quát hơn: đồng $n$ tách thành $n/2$, $n/3$, $n/4$. Tách đồng $n/2$ ra ta được $n/4$, $n/6$, $n/8$ – đồng $n/4$ bị trùng. Tách đồng $n/3$ thử, ta được $n/6$, $n/9$, $n/12$ – lại lần nữa đồng $n/6$ bị trùng. Thật ra chỉ cần thấy trùng 1 lần là ta đã kết luận được bài có bài toán con trùng lặp rồi.

Ý tưởng đệ quy có nhớ

Nếu đã tính Try(400) rồi thì ta lưu kết quả lại, lần sau gặp lại chỉ việc trả về luôn, không tính lại nữa. Cụ thể: sau điều kiện dừng, ta kiểm tra xem đã từng tính Try(n) chưa; nếu rồi thì trả về luôn, còn chưa thì tính, lưu lại rồi mới trả về. Phương pháp này được gọi là quy hoạch động top-down hay còn gọi là đệ quy có nhớ đó anh em.

Minh hoạ: cây đệ quy khi không nhớ và khi có nhớ

Em nhập $n$, chọn chế độ rồi bấm Tiếp để xem từng lời gọi. Ở chế độ không nhớ, các dòng có nhãn đỏ "tính lại" là những Try(x) đã từng tính xong trước đó mà vẫn phải tính lại từ đầu. Ở chế độ có nhớ, gặp lại thì chỉ "lấy từ map" (nhãn tím) là xong, cây gọn hơn hẳn. Thử $n = 32$ ở cả 2 chế độ để so sánh nha:

n Chế độ Không nhớ (cách 1)Có nhớ bằng map (cách 2)

Ví dụ nhanh:

Với $n = 32$: không nhớ phải gọi hàm $130$ lần, có nhớ thì chỉ còn $28$ lần. Còn với $n = 10^9$, bấm ⏭ sẽ thấy map chỉ lưu đúng $241$ giá trị khác nhau, trong khi cách 1 phải gọi hàm khoảng $1.5 \cdot 10^{10}$ lần!

Lưu kết quả vào đâu? Mảng, map hay unordered_map?

Vì $n \le 10^9$ nên ta không thể dùng mảng hay vector để lưu kết quả Try(n) được: một mảng $10^9$ phần tử sẽ rất tốn bộ nhớ. Nhưng như minh hoạ ở trên, bài này lại không có quá nhiều bài toán con khác nhau, vì ở mỗi lần gọi đệ quy thì $n$ bị chia 2, chia 3, chia 4 nên giảm xuống rất nhanh.

mapBản chất là một cây đỏ đen (red-black tree), một cây nhị phân tìm kiếm cân bằng. Truy xuất hay thêm phần tử mất $O(\log K)$ với $K$ là size của map, cộng chút chi phí cân bằng cây khi thêm phần tử. Vì số bài toán con ít nên $K$ nhỏ, nhìn chung không tốn bao nhiêu thời gian. Ưu điểm: mọi trường hợp đều đảm bảo $O(\log K)$.

unordered_mapLưu theo bảng băm (hash table) thay vì cây, tìm kiếm và thêm phần tử trung bình chỉ $O(1)$, nhanh như truy xuất mảng luôn mà không tốn chi phí cân bằng cây. Nhưng về lý thuyết, trường hợp xấu nhất (hàm băm bị xung đột nhiều) có thể lên tới $O(K)$, và cái này mình không kiểm soát được, phó mặc cho cấu trúc dữ liệu có sẵn.

Kinh nghiệm chọn map hay unordered_map

Không phải lúc nào unordered_map cũng tốt hơn map. Dùng map tuy độ phức tạp cao hơn nhưng ta cảm thấy yên tâm hơn 🤣. Kinh nghiệm là nếu các bạn code dùng map mà bị TLE thì cứ thử thay bằng unordered_map rồi nộp lại xem: nếu được thêm test nào nữa thì tốt, còn nếu thấy 1 số test đang từ AC chuyển sang TLE thì quay xe lại map thôi 🤪. Bài này dùng cả 2 đều AC nha: chỉ việc sửa dòng khai báo thành unordered_map<ll, ll> mp; là xong.

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;

map<ll, ll> mp;

ll Try(ll n){
    if(n == 0){
        return 0;
    }
    if(mp[n] != 0){
        return mp[n];
    }
    return mp[n] = max(n, Try(n / 2) + Try(n / 3) + Try(n / 4));
}

int main(){
    // freopen("dprccoi.inp", "r", stdin);
    // freopen("dprccoi.out", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll n;
    while(cin >> n){
        cout << Try(n) << endl;
    }
    return 0;
}

import sys

mp = {}

def Try(n):
    if n == 0:
        return 0
    if mp.get(n, 0) != 0:
        return mp[n]
    mp[n] = max(n, Try(n // 2) + Try(n // 3) + Try(n // 4))
    return mp[n]

for tok in sys.stdin.read().split():
    n = int(tok)
    print(Try(n))

Giải thích 1 số chỗ trong code ở trên:

1. Tại sao map<ll, ll> mp là biến toàn cục mà không tạo một map trống mới mỗi lần lặp while(cin >> n) rồi truyền tham chiếu vào hàm Try()? Bởi vì nếu trước đó ta đã tính số tiền tối đa của đồng $100$ chẳng hạn, thì đến lúc gặp đồng $200$, rất nhiều bài toán con đã được tính sẵn từ đồng trước rồi. Để map toàn cục thì các đồng sau được "hưởng ké" kết quả của các đồng trước. Chẳng hạn đầu vào là 10 đồng $10^9$ thì ta chỉ phải tính đúng 1 lần thôi.
2. if(mp[n] != 0): mặc định các giá trị trong map chưa được gán sẽ bằng $0$ (khi truy cập mp[n] mà chưa có thì map tự tạo mp[n] = 0). Với $n \ge 1$ thì Try(n) ≥ n ≥ 1, không bao giờ bằng 0. Nên nếu mp[n] != 0 thì chứng tỏ ta đã tính Try(n) và lưu vào rồi; còn bằng 0 thì ta đi tính để gán vào thôi.
3. return mp[n] = max(...); câu lệnh này thực chất là gán mp[n] = max(n, Try(n / 2) + Try(n / 3) + Try(n / 4)) rồi mới return mp[n] nha.

Trong khung chạy tay dưới đây, phần map mp sẽ hiện từng phần tử được thêm vào (ô vàng là phần tử vừa được map tự tạo với giá trị 0 hoặc vừa được gán). Bấm thử test "Hai đồng 32 và 64" để thấy đồng thứ hai được dùng lại kết quả của đồng thứ nhất:

C++▶ Chạy tay từng dòng codeCách 2: như cách 1 nhưng lưu Try(n) vào map toàn cục mp, gặp lại thì trả về luôn.

Dữ liệu vào (stdin) – sửa thoải mái32

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2#define endl '\n'

3using namespace std;

4typedef long long ll;

5

6map<ll, ll> mp;

7

8ll Try(ll n){

9 if(n == 0){

10 return 0;

11 }

12 if(mp[n] != 0){

13 return mp[n];

14 }

15 return mp[n] = max(n, Try(n / 2) + Try(n / 3) + Try(n / 4));

16}

17

18int main(){

19 // freopen("dprccoi.inp", "r", stdin);

20 // freopen("dprccoi.out", "w", stdout);

21 ios_base::sync_with_stdio(0);

22 cin.tie(0);

23 ll n;

24 while(cin >> n){

25 cout << Try(n) << endl;

26 }

27 return 0;

28}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: $O(K)$ với $K$ là số giá trị khác nhau xuất hiện trong cây đệ quy. Mình đếm thử: với $n = 10^9$ thì $K$ chỉ là $241$ (chưa tính đồng $0$). Thực ra mọi giá trị xuất hiện đều có dạng $\left\lfloor \dfrac{n}{2^a 3^b} \right\rfloor$ (vì chia 4 cũng là chia 2 hai lần), nên $K$ chỉ cỡ $O(\log^2 n)$.
• Thời gian: mỗi giá trị chỉ được tính đúng 1 lần, mỗi lần tốn vài thao tác trên map $O(\log K)$. Tổng cộng khoảng $O(K \log K)$ cho mỗi đồng, chạy tức thì.

Không gian$O(K)$, $K \approx 241$

Thời gian$O(K \log K)$

Còn quy hoạch động bottom-up thì sao?

Ở trên mình dùng quy hoạch động top-down rồi thì phải có bottom-up chứ? Đúng là có thật và nó vô cùng dễ: gọi $F[n]$ là số tiền tối đa đổi được từ đồng $n$ thì $F[n] = \max(n,\ F[n/2] + F[n/3] + F[n/4])$, trường hợp cơ sở $F[0] = 0$, cứ for $n$ từ 1 lên là xong. Nhưng độ phức tạp là $O(n)$ mà $n$ có thể lên tới $10^9$: cả thời gian lẫn bộ nhớ ta đều không đáp ứng được, vì một mảng tận $10^9$ phần tử là quá lớn. Vậy nên bài này ta dùng quy hoạch động top-down – đệ quy có nhớ thôi nha. Đây cũng là một ví dụ hay cho thấy top-down đôi khi "ăn đứt" bottom-up: nó chỉ tính đúng những bài toán con thật sự cần.

Ghi chú của mình: code C++ và Python của cả 2 cách đều cho đúng output của ví dụ đề, và đã được so với code quy hoạch động bottom-up (mảng $F$ tới $2 \cdot 10^6$) trên 300 bộ test ngẫu nhiên (mỗi bộ 1–10 đồng, $n \le 2 \cdot 10^6$) – khớp hết. Với 10 đồng $n$ ngẫu nhiên gần $10^9$: cách 2 bản C++ và Python đều chạy dưới 0.05 giây; còn cách 1 bản C++ với chỉ 1 đồng $n = 10^9$ đã mất hơn 30 giây (với $n = 10^8$ khoảng 5 giây), đúng như phân tích.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇