Chia của

Submit solution
Points: 2
Time limit: 1.0s
Memory limit: 1000M
Author:
TICHPX
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Một ông bố có n tài sản có giá trị lần lượt là a1,a2,…,an. Ông chỉ có hai người con ông muốn đem chia n tài sản này cho 2 người con sao cho chênh lệch giữa 2 người là ít nhất có thể.

Input

Dòng thứ nhất số nguyên dương n là tài sản ( 1 ≤ n ≤ 20)

Dòng thứ hai chứa n số nguyên dương có giá trị tuyệt đối không quá 10^4

Output

Một số nguyên là độ chênh ít nhất có thể của hai người con

Example 1

Input

3
8 4 6

Output

2

Giải thích: Một người nhận 8 một người nhận 4+6=10 nên chênh lệch ít nhất 2

Example 2

Input

5
10 7 9 6 6

Output

0

Giải thích: Một người nhận 10+9 =19 một người nhận 7+6+6=19 nên chênh lệch ít nhất 0

tichpx

Comments


  • -1
    thien201206512CNTT4K61  commented on Dec. 2, 2021, 9:20 a.m. ← edited 
    #include<bits/stdc++.h>
using namespace std;

int a[100],h[100],n,s;
int d[100][10000],pre[100][10000];

void inp(int a[],int &n,int &s)
{
    scanf("%d",&n);
    s=0;
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        s+=a[i];
    }
}

void init()
{
    for (int i=1;i<=n;i++)
    {
        d[i][a[i]]=1;
        pre[i][a[i]]=i;
    }
}

void solve()
{
    for (int i=2;i<=n;i++)
    for (int j=0;j<=s;j++)
        if (d[i-1][j]==1)   d[i][j]=1;
        else
            if ((j-a[i]>=0) && (d[i-1][j-a[i]]==1))
            {
                d[i][j]=1;
                pre[i][j]=i;
            }
}

void truyhoi(int n,int s)
{
    if ((n!=0)&&(s!=0))
    {
        if (pre[n][s]!=0)
        {
            truyhoi(n-1,s-a[pre[n][s]]);
            h[n]=1;
        }
        else
        if (d[n-1][s]=1)
            truyhoi(n-1,s);
    }
}

void out(int s1)
{
    truyhoi(n,s1);
    printf("%d",s-s1*2);
}

int main()
{
    inp(a,n,s);
    init();
    solve();
    for (int s1=s/2;s1>0;s1--)
        if (d[n][s1]==1) 
        {
            out(s1);
            break;
        }
    return 0;   
}