Cân đĩa (THTB Vòng Sơ loại)

Tác giả:

Dạng bài

Điểm: 400 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Cho một cân hai đĩa và \(n\) quả cân có khối lượng đôi một khác nhau \(w_1, w_2, . . , w_n\). Tiến hành đặt lần
lượt từng quả cân lên một trong hai đĩa của cân và đảm bảo rằng tổng khối lượng bên trái luôn nhỏ
hơn hoặc bằng tổng khối lượng bên phải.

Yêu cầu: Cho \(n\) quả cân có khối lượng \(w_1, w_2, . . , w_n\), hãy đếm số cách xếp \(n\) quả cân thỏa mãn.

Hai cách được gọi là khác nhau nếu thứ tự xếp các quả cân khác nhau hoặc tồn tại một quả cân nằm
ở đĩa khác nhau.

Input

Vào từ thiết bị vào chuẩn có khuôn dạng:

Dòng 1: chứa số nguyên \(n\);
Dòng 2: chứa \(n\) số nguyên dương \(w_1, w_2, . . , w_n\).

Output

Ghi ra thiết bị ra chuẩn một dòng chứa một số nguyên là số cách xếp \(n\) quả cân lên đĩa.

Scoring

Subtask \(1\) (\(40\%\) số điểm): \(n \le 7\) và \(w_i \le 1000 (1 \le i \le n)\);
Subtask \(2\) (\(40\%\) số điểm): \(n \le 14\) và \(w_i \le 1000 (1 \le i \le n)\);
Subtask \(3\) (\(20\%\) số điểm): \(n \le 28\) và \(w_i = 2^{i−1} (1 \le i \le n)\).

Example

Test 1

Input

2
1 2

Output

Note

Ở ví dụ bên trái, có 8 cách sắp xếp các quả cân lên hai bàn cân như sau:

Đặt quả cân 1 bên trái rồi đặt quả cân 2 bên trái;
Đặt quả cân 1 bên trái rồi đặt quả cân 2 bên phải;
Đặt quả cân 1 bên phải rồi đặt quả cân 2 bên trái;
Đặt quả cân 1 bên phải rồi đặt quả cân 2 bên phải;
Đặt quả cân 2 bên trái rồi đặt quả cân 1 bên trái;
Đặt quả cân 2 bên trái rồi đặt quả cân 1 bên phải;
Đặt quả cân 2 bên phải rồi đặt quả cân 1 bên trái;
Đặt quả cân 2 bên phải rồi đặt quả cân 1 bên phải.
Tuy nhiên chỉ có 3 cách (cách 4, 7, 😎 là đảm bảo trong toàn bộ quá trình sắp xếp các quả cân,
đĩa bên trái luôn nhỏ hơn hoặc bằng đĩa cân bên phải.

Test 2

Input

3
10 11 12

Output

Bình luận

Em xin chia sẻ lời giải bài toán này như sau:

Bài chỉ mang tính chất tham khảo, vui lòng không chép code :<

Hint: Với mỗi quả cân w[i] ta có thể chưa đặt ( 0 ), đặt vào bên trái ( 1 ) hoặc đặt vào bên phải ( 2 ). Vậy có thể dùng một dãy tam phân có độ dài là n để mô tả trạng thái bài toán.

Với 1 trạng thái dãy tam phân, ta tính số cách để tiếp tục đặt đến hết thỏa mãn:

Giả sử dãy tam phân tam phân hiện tại là x ( int x[14] )
Xét lần lượt các quả cân chưa đặt ( x[i] == 0 ) thì ta có thể xét 2TH:
+ Nếu mà cân nặng bên trái khi thêm quả cân thứ i vào mà vẫn nhỏ hơn hoặc bằng cân nặng bên phải thì ta có thể đặt quả cân thứ i sang bên trái
+Quả cân thứ i sẽ đặt sang bên phải
Gọi để quy tiếp cho tới khi đặt hết

Code của phần trên như sauu:

long long tinh(int d){
    int x[14];
    int d2=d;
    for(int i=0;i<n;i++){
        x[i]=d2%3;
        d2=d2/3;
    }
    long long sum1=0, sum2=0, sl=0;
    for(int i=0;i<n;i++){
        if(x[i]==1){
            sum1+=w[i];
            sl++;
        }
        else if(x[i]==2){
            sum2+=w[i];
            sl++;
        }
    }
    if(sl==n)   return 1;

    long long cnt=0;
    for(int i=0;i<n;i++){
        if(x[i]==0){
            if(sum1+w[i]<=sum2){
                cnt=cnt+tinh(d+p[i]);
            }
            cnt=cnt+tinh(d+2*p[i]);
        }
    }
    return cnt;
}

Đẩy mảng có nhớ để “tăng tốc” thành DP

Code để có được 80 điểm:

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

long long n, w[30], p[30], dp[50000005], l[50000005];

long long tinh(int d){
    if(dp[d]==1)    return l[d];
    int x[30];
    int d2=d;
    for(int i=0;i<n;i++){
        x[i]=d2%3;
        d2=d2/3;
    }
    long long sum1=0, sum2=0, sl=0;
    for(int i=0;i<n;i++){
        if(x[i]==1){
            sum1+=w[i];
            sl++;
        }
        else if(x[i]==2){
            sum2+=w[i];
            sl++;
        }
    }
    if(sl==n)   return 1;

    long long cnt=0;
    for(int i=0;i<n;i++){
        if(x[i]==0){
            if(sum1+w[i]<=sum2){
                cnt=cnt+tinh(d+p[i]);
            }
            cnt=cnt+tinh(d+2*p[i]);
        }
    }
    dp[d]=1;
    l[d]=cnt;
    return cnt;
}

int main(){
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> w[i];
    }
    p[0]=1;
    for(int i=1;i<n;i++){
        p[i]=p[i-1]*3;
    }
    cout << tinh(0);
}

Tiếp theo là sub 3, ở sub 3 thì ta có thể thấy n<=28, nhưng có một điều đặc biệt ở đây đó chính là w[i]=2^(i-1), dùng chương trình trên để tìm quy luật

Sau khi thử vài test như sau

Input: 2 1 2        Output: 3
Input: 3 1 2 4      Output: 15
Input: 4 1 2 4 8        Output: 105

Như vậy quy luật sub 3 là f[n]=f[n-1]*(2n+1), với f[0]=1

Nhưng vì số rất lớn ( Có thể lên tới 40 chữ số ) nên để AC thì ta phải sử dụng Bignum

Code để AC:

long long n, w[30], p[30], dp[50000005], l[50000005];

string nhan(string a, int b){
    int nho=0, res;
    string c="";
    for(int i=a.length()-1;i>=0;i--){
        res=(a[i]-48)*b+nho;
        nho=res/10;
        c=char((res%10)+48)+c;
    }
    while(nho>0){
        c=char((nho%10)+48)+c;
        nho=nho/10;
    }
    return c;
}

long long tinh(int d){
    if(dp[d]==1)    return l[d];
    int x[30];
    int d2=d;
    for(int i=0;i<n;i++){
        x[i]=d2%3;
        d2=d2/3;
    }
    long long sum1=0, sum2=0, sl=0;
    for(int i=0;i<n;i++){
        if(x[i]==1){
            sum1+=w[i];
            sl++;
        }
        else if(x[i]==2){
            sum2+=w[i];
            sl++;
        }
    }
    if(sl==n)   return 1;

    long long cnt=0;
    for(int i=0;i<n;i++){
        if(x[i]==0){
            if(sum1+w[i]<=sum2){
                cnt=cnt+tinh(d+p[i]);
            }
            cnt=cnt+tinh(d+2*p[i]);
        }
    }
    dp[d]=1;
    l[d]=cnt;
    return cnt;
}
// :3
int main(){
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> w[i];
    }
    p[0]=1;
    for(int i=1;i<n;i++){
        p[i]=p[i-1]*3;
    }
    if(n<=14)   cout << tinh(0);
    else{
        long long j=1;
        string kq="1";
        for(int i=1;i<=n;i++){
            kq=nhan(kq,j);
            j=j+2;
        }
        cout << kq;
    }
}

-9

NgJaBach 6:57 p.m. 9 Tháng 8, 2021

sad

Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.

-9

Lê_Gia_Khánh 7:46 p.m. 11 Tháng 8, 2021

sad

Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.

2 bình luận nữa