Tiền Tệ (TIENTE)

Nguồn: NTUCoder Độ khó: Trung bình Vét cạn Duyệt bitmask Dãy nhị phân

Đề bài

TT – TIENTE

Một người mẹ muốn chia đều cho hai đứa con số tiền trong túi của mình. Khi rút tiền trong túi ra, bà thấy có $n$ đồng tiền $(n \le 20)$ với các loại mệnh giá khác nhau. Bà cảm thấy lo lắng chia cho hai người con có được không.

Yêu cầu: Bạn hãy giúp bà ấy chia tiền cho hai người con. Nếu chia được thì nêu rõ số cách chia.

Dữ liệu vào: Gồm 02 dòng:

• Dòng đầu ghi số $n$ là số đồng tiền $(1 \le n \le 20)$.
• Dòng sau ghi mệnh giá các đồng tiền là các số nguyên dương có cùng đơn vị tính $(0 \le t[i] \le 500)$.

Dữ liệu ra:

• Dòng thứ nhất ghi số cách chia, nếu không thể chia được thì ghi "Khong chia duoc".
• Các dòng sau trong trường hợp chia được, mỗi dòng là 01 cách chia với quy ước người thứ nhất có tên là "A", người thứ hai có tên là "B" và phải tương ứng với thứ tự của các đồng tiền mà bà đưa ra.

Giới hạn: thời gian 1 giây, bộ nhớ 128 MB.

Ví dụ 1 – input

6
1 2 2 5 10 10

Ví dụ 1 – output

4
A A A B A B
A A A B B A
B B B A A B
B B B A B A

Ví dụ 2 – input

6
1 2 2 5 10 1

Ví dụ 2 – output

khong chia duoc

Chữ "khong chia duoc"

Đề ghi "Khong chia duoc" (chữ K hoa) nhưng ví dụ lại in "khong chia duoc" (chữ thường). Code bên dưới in theo đúng ví dụ, tức chữ thường.

Lời mở đầu

Các bạn hãy giúp bà Mẹ để tránh cảnh 2 anh em huynh đệ tương tàn nào 😆. 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 😇.

Trước khi vào bài, các bạn nhớ lại ngưỡng an toàn mình hay nhắc: với các hệ thống chấm giới hạn 1 giây thì toàn bài chỉ nên lặp khoảng $(3 \div 5) \cdot 10^7$ lần (C/C++), cao lắm là $10^8$ thì hên xui; Python, Java, C# chạy chậm hơn nên ngưỡng còn thấp hơn. Bài này giới hạn 1 giây.

Giải thích ví dụ 1: tổng 6 đồng tiền là $1 + 2 + 2 + 5 + 10 + 10 = 30$, mỗi người con phải được đúng $15$. Ví dụ dòng A A A B A B nghĩa là đồng tiền thứ 1, 2, 3, 5 cho A ($1 + 2 + 2 + 10 = 15$), đồng thứ 4, 6 cho B ($5 + 10 = 15$) – chia đều ✔. Có cả thảy 4 cách như vậy. Ví dụ 2 thì tổng là $21$, số lẻ, chia đôi sao nổi nên in khong chia duoc.

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 1Vét cạn mọi dãy nhị phân · O(N·2^N)Cách 2Cải tiến nhỏ: lưu số i, đỡ tốn bộ nhớ

Cách 1Vét cạn bằng các dãy nhị phân độ dài N – O(N·2^N)

Nếu bài này chỉ yêu cầu tìm 1 cách chia bất kỳ thì có nhiều cách tối ưu, ví dụ Quy hoạch động: bài toán tìm dãy con có tổng bằng $S$, với $S$ là tổng tiền chia 2. Nhưng ở đây đề yêu cầu liệt kê tất cả các cách chia, nên ta phải vét cạn thôi. Thường người ta sẽ dùng đệ quy quay lui; nhưng ở bài này mình hướng dẫn một cách khác – bản chất vẫn là quay lui (thử hết mọi khả năng) nhưng không dùng đệ quy, để các bạn dễ theo dõi luồng chạy hơn.

Vét cạn ở đây hiểu thế nào? Giả sử mẹ có 2 đồng tiền. Xét đồng thứ 1 có 2 lựa chọn: cho A hoặc cho B; đồng thứ 2 cũng có 2 lựa chọn như vậy. Nếu gọi "cho A" là bit $0$, "cho B" là bit $1$ thì ta có các tình huống:

Đồng 1	Đồng 2
0 (A)	0 (A)
0 (A)	1 (B)
1 (B)	0 (A)
1 (B)	1 (B)

3 đồng tiền: 8 tình huống
0 0 0	0 1 1	1 1 0
0 0 1	1 0 0	1 1 1
0 1 0	1 0 1

Các bạn thấy quen không? Đó chính là bài toán liệt kê các dãy nhị phân độ dài N đấy, với $N$ là số đồng tiền ($2^N$ dãy). Với mỗi dãy, vị trí nào là $0$ thì cộng mệnh giá đồng tiền đó vào sumA, là $1$ thì cộng vào sumB. Xét xong dãy mà sumA == sumB thì dãy đó là 1 cách chia, ta lưu vào mảng kết quả res. Xét hết các dãy rồi: res rỗng thì in "khong chia duoc", ngược lại in số cách và từng dãy (bit 0 in A, bit 1 in B). Đơn giản vậy thôi.

Sinh dãy nhị phân từ số i

Cho $i$ chạy từ $0$ đến $2^N - 1$, đổi $i$ sang hệ nhị phân (chia 2 lấy dư liên tục) và ghi các bit từ cuối mảng về đầu, phần đầu thiếu thì để sẵn $0$. Ví dụ $N = 3$, $i = 6$: $6 \bmod 2 = 0$, $3 \bmod 2 = 1$, $1 \bmod 2 = 1$ → dãy 1 1 0. Vì $i$ tăng dần nên các dãy được liệt kê theo đúng thứ tự từ điển, khớp với thứ tự in ở ví dụ của đề.

Em nhập mệnh giá các đồng tiền rồi bấm Tiếp để xem lần lượt từng dãy nhị phân, đồng nào cho A (xanh), đồng nào cho B (cam), và cách chia nào được ghi nhận:

Mệnh giá t

Ví dụ nhanh:

Để hiểu được code bên dưới, các bạn cần làm được bài liệt kê các dãy nhị phân độ dài $N$ trước nhé. Source code để các bạn tham khảo nếu làm theo hướng này:

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin >> n;
    vector<int> t(n);
    int sum = 0;
    for(int i = 0; i < n; ++i){
        cin >> t[i];
        sum += t[i];
    }
    if(sum % 2 != 0){
        cout << "khong chia duoc";
    }
    else{
        int sz = (int)pow(2.0, n);
        vector<vector<int>> res;
        for(int i = 0; i < sz; ++i){
            int sumB = 0;
            int temp = i, j = n - 1;
            vector<int> a(n, 0);
            while(temp != 0){
                a[j] = temp % 2;
                temp /= 2;
                if(a[j] == 1){
                    sumB += t[j];
                }
                j--;
            }
            if(sumB * 2 == sum){
                res.push_back(a);
            }
        }
        if((int)res.size() == 0){
            cout << "khong chia duoc";
        }
        else{
            cout << (int)res.size();
            for(int i = 0; i < (int)res.size(); ++i){
                cout << "\n";
                for(int j = 0; j < (int)res[i].size(); ++j){
                    cout << (res[i][j] == 0 ? "A " : "B ");
                }
            }
        }
    }
    return 0;
}

n = int(input())
t = list(map(int, input().split()))
total = sum(t)
if total % 2 != 0:
    print("khong chia duoc")
else:
    sz = 2 ** n
    res = []
    for i in range(sz):
        sumB = 0
        temp, j = i, n - 1
        a = [0] * n
        while temp != 0:
            a[j] = temp % 2
            temp //= 2
            if a[j] == 1:
                sumB += t[j]
            j -= 1
        if sumB * 2 == total:
            res.append(a)
    if len(res) == 0:
        print("khong chia duoc")
    else:
        out = [str(len(res))]
        for a in res:
            out.append("".join("A " if x == 0 else "B " for x in a))
        print("\n".join(out))

Bấm Tiếp để chạy tay từng dòng code (phần "Dữ liệu" vẽ mảng mệnh giá t và dãy bit a đang tạo):

C++▶ Chạy tay từng dòng codeCách 1: duyệt i = 0..2^n - 1, đổi i ra dãy bit a, tính sumB, sumB * 2 == sum thì lưu a.

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

Dữ liệu mẫu:

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

2using namespace std;

3

4int main(){

5 int n;

6 cin >> n;

7 vector<int> t(n);

8 int sum = 0;

9 for(int i = 0; i < n; ++i){

10 cin >> t[i];

11 sum += t[i];

12 }

13 if(sum % 2 != 0){

14 cout << "khong chia duoc";

15 }

16 else{

17 int sz = (int)pow(2.0, n);

18 vector<vector<int>> res;

19 for(int i = 0; i < sz; ++i){

20 int sumB = 0;

21 int temp = i, j = n - 1;

22 vector<int> a(n, 0);

23 while(temp != 0){

24 a[j] = temp % 2;

25 temp /= 2;

26 if(a[j] == 1){

27 sumB += t[j];

28 }

29 j--;

30 }

31 if(sumB * 2 == sum){

32 res.push_back(a);

33 }

34 }

35 if((int)res.size() == 0){

36 cout << "khong chia duoc";

37 }

38 else{

39 cout << (int)res.size();

40 for(int i = 0; i < (int)res.size(); ++i){

41 cout << "\n";

42 for(int j = 0; j < (int)res[i].size(); ++j){

43 cout << (res[i][j] == 0 ? "A " : "B ");

44 }

45 }

46 }

47 }

48 return 0;

49}

ChậmVừaNhanhRất nhanh

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

1. Mảng mình dùng kiểu vector – mảng động của STL C++, rất tiện, bạn nào chưa biết thì nên tìm hiểu nhé. vector<int> t(n); là mảng $n$ số nguyên; vector<int> a(n, 0); là mảng $n$ số nguyên, tất cả bằng $0$; vector<vector<int>> res; là mảng 2 chiều.
2. Vòng for đọc mệnh giá tận dụng tính luôn tổng sum. Nếu sum lẻ thì kết luận ngay không chia được (muốn chia đôi thì phải chia hết cho 2), khỏi xét dãy nào.
3. Với mỗi dãy bit a (ban đầu toàn $0$), temp liên tục chia 2 để lấy bit, ghi từ cuối mảng về đầu; temp hết bit sớm thì phần đầu vẫn là các bit $0$ đã khởi tạo sẵn. Lý thuyết cần 2 biến sumA, sumB, nhưng thực tế chỉ cần sumB (cộng khi bit là $1$), vì sumA = sum - sumB. Hai người bằng nhau khi sumB * 2 == sum.
4. Chỗ so sánh, một số bạn sẽ viết sum / 2 == sumB. Tốt nhất nên tránh phép chia, dùng phép nhân cho chắc ăn (ở đây ta đã chắc sum chẵn nên chia cũng ra đúng, nhưng tập thói quen tránh chia vẫn tốt hơn, vì phép chia nguyên/chia thực dễ gây sai lệch ở những bài khác).

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

• Không gian: $O(N)$ mảng mệnh giá + $O(N)$ dãy bit + $O(K \cdot N)$ cho mảng res, với $K$ là số cách chia tìm được. Tốt nhất là không chia được ($K = 0$, chỉ $O(N)$). Trung bình như ví dụ 1: $2^6 = 64$ dãy mà chỉ $K = 4$ cách. Nhưng xấu nhất: đề cho $0 \le t[i] \le 500$, nếu tất cả đều bằng $0$ thì dãy nào cũng là đáp án (hai bên đều bằng $0$), $K = 2^N$ ⇒ $O(N \cdot 2^N)$.
• Thời gian: tốt nhất là sum lẻ, chỉ $O(N)$. Còn lại phải xét đủ $2^N$ dãy, mỗi dãy $N$ bit ⇒ $O(N \cdot 2^N)$; bước in res xấu nhất (toàn số 0) cũng $O(N \cdot 2^N)$. Tổng quát $O(N \cdot 2^N)$.

Không gian$O(N \cdot 2^N)$

Thời gian$O(N \cdot 2^N)$

Với $N = 20$: $20 \cdot 2^{20} = 20\,971\,520$, tầm 21 triệu lần lặp, vẫn trong ngưỡng $(3 \div 5) \cdot 10^7$ nên cách làm này không bị TLE.

Trường hợp toàn đồng 0 khá "nặng"

Mình chạy thử code C++ ở trên với $N = 20$ toàn mệnh giá $0$: có $2^{20} = 1\,048\,576$ cách, phải in ra khoảng 43 MB chữ, chạy mất khoảng 0,75–1,5 giây và tốn khoảng 123 MB bộ nhớ (mỗi cách là 1 vector riêng) – sát nút giới hạn 128 MB. Với dữ liệu thường (ví dụ 20 đồng ngẫu nhiên, hay 20 đồng 500) thì chỉ mất 0,1–0,2 giây. Bản Python làm y hệt thì chậm hơn nhiều (5–8 giây với $N = 20$) ⇒ chỉ để tham khảo, nộp Python thì dùng bản ở cách 2.

Cách 2Cải tiến nhỏ: lưu số i thay cho cả dãy bit – O(N·2^N)

Phần này mình bổ sung thêm cho trường hợp xấu nhất ở trên, ý tưởng vẫn y như cách 1. Để ý rằng dãy bit của một cách chia chính là biểu diễn nhị phân của số $i$, nên khỏi cần lưu cả mảng a: chỉ cần lưu số $i$ (1 số int), lúc in ra thì lấy lại bit thứ $j$ (tính từ trái) bằng (i >> (n - 1 - j)) & 1. Thêm 2 dòng tăng tốc nhập xuất cho cin/cout vì lượng chữ in ra có thể rất lớn.

Lấy bit của đồng tiền thứ j

Đồng tiền thứ $j$ (đếm từ $0$, từ trái sang) ứng với bit thứ $n - 1 - j$ của số $i$: $\text{bit} = \left\lfloor i / 2^{\,n-1-j} \right\rfloor \bmod 2$, trong C++ viết là (i >> (n - 1 - j)) & 1. Đây chính là bit $a[j]$ mà cách 1 tạo ra bằng cách chia 2 liên tục.

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

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    vector<int> t(n);
    int sum = 0;
    for(int i = 0; i < n; ++i){
        cin >> t[i];
        sum += t[i];
    }
    vector<int> res;
    if(sum % 2 == 0){
        int sz = 1 << n;
        for(int i = 0; i < sz; ++i){
            int sumB = 0;
            for(int j = 0; j < n; ++j){
                if((i >> (n - 1 - j)) & 1){
                    sumB += t[j];
                }
            }
            if(sumB * 2 == sum){
                res.push_back(i);
            }
        }
    }
    if((int)res.size() == 0){
        cout << "khong chia duoc";
    }
    else{
        cout << (int)res.size();
        for(int i = 0; i < (int)res.size(); ++i){
            cout << "\n";
            for(int j = 0; j < n; ++j){
                cout << (((res[i] >> (n - 1 - j)) & 1) ? "B " : "A ");
            }
        }
    }
    return 0;
}

import sys

data = sys.stdin.read().split()
n = int(data[0])
t = list(map(int, data[1:n + 1]))
total = sum(t)
res = []
if total % 2 == 0:
    sz = 1 << n
    # s[i] = sumB của số i: đồng tiền thứ j ứng với bit (n - 1 - j)
    w = [t[n - 1 - b] for b in range(n)]
    s = [0] * sz
    for i in range(1, sz):
        low = i & -i
        s[i] = s[i ^ low] + w[low.bit_length() - 1]
    res = [i for i in range(sz) if s[i] * 2 == total]
if len(res) == 0:
    print("khong chia duoc")
else:
    tbl = str.maketrans({"0": "A ", "1": "B "})
    fmt = "0" + str(n) + "b"
    out = sys.stdout
    out.write(str(len(res)))
    for k in range(0, len(res), 4096):  # in từng khúc cho đỡ tốn bộ nhớ
        out.write("".join("\n" + format(i, fmt).translate(tbl) for i in res[k:k + 4096]))
    out.write("\n")

Bản Python mình tính sumB của số $i$ dựa vào số nhỏ hơn đã tính: bỏ bit 1 thấp nhất của $i$ (low = i & -i) ta được số i ^ low đã có sẵn tổng, cộng thêm mệnh giá của đồng tiền ứng với bit đó là xong – mỗi số chỉ tốn 1 phép thay vì $N$ phép, Python mới chạy nổi. Dòng in thì dùng format(i, "0Nb") để ra chuỗi nhị phân đủ $N$ chữ số rồi đổi 0 → A, 1 → B.

Không gian$O(2^N)$

Thời gian$O(N \cdot 2^N)$

Với $N = 20$ toàn số $0$: bản C++ này chạy khoảng 0,5 giây và chỉ tốn khoảng 11 MB bộ nhớ; bản Python khoảng 2 giây, 58 MB.

Ghi chú của mình: code C++ và Python của cả 2 cách đã được kiểm tra với 400 bộ test ngẫu nhiên ($n \le 10$, có nhiều đồng $0$, mệnh giá nhỏ để nhiều cách chia, và mệnh giá tới 500), so với code vét cạn viết riêng bằng itertools.product – khớp hết, cả số cách lẫn thứ tự các dòng. Với $n = 20$: mệnh giá ngẫu nhiên thì cách 1 (C++) chạy khoảng 0,1 giây; toàn số 0 (1.048.576 cách) thì số liệu như mình ghi ở trên.

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 😇