Կշիռների բաժանում
Տրված է
n քանակով կշիռ (). Անհրաժեշտ է բաժանել այդ կշիռները երկու խմբի այնպես, որ նրանց քաշերի տարբերությունը լինի հնարավորինս փոքր։Մուտք
Մուտքի առաջին տողում տրված է
n ամբողջ թիվը (1 ≤ n ≤ 20)։Հաջորդ տողում տրված են
n ամբողջ թվեր (1 ≤ ≤ ), որոնք բաժանված են բացատներով:Ելք
Ծրագիրը պետք է տպի երկու խմբերի քաշերի նվազագույն տարբերությունը:
Օրինակներ
Մուտք | Ելք |
3
3 2 1 | 0 |
5
1 2 3 4 7 | 1 |
Բացատրություն
- Առաջին խումբ → 3, երկրորդ խումբ → 1 + 2 = 3
- Առաջին խումբ → 1 + 7 = 8, երկրորդ խումբ → 2 + 3 + 4 = 9
Հուշում
Կարող եք փորձել դիտարկել քաշերը բաժանելու բոլոր հնարավոր տարբերակները և ընտրել նվազագույն տարբերությունը:
Constraints
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB