magnify

Akmenų krūva

Pradinių duomenų failas:
akmenys.in  
Rezultatų failas:
akmenys.out  
Laiko apribojimas:
1 s.  
Atminties apribojimas:
16 Mb.  

Užduotis

Jums duoti n akmenų su žinomais svoriais \(W_{1}\), \(W_{2}\), …, \(W_{n}\). Parašykite programą, kuri rastų, kaip sudėlioti šiuos akmenis į dvi krūvas, kad krūvų svorių skirtumas būtų minimalus.

Pradiniai duomenys

Pirmoje pradinių duomenų eilutėje įrašytas akmenų skaičius n (1 <= n <= 25). Kitose n eilučių pateikiami akmenų svoriai – tai teigiami sveikieji skaičiai, neviršijantys 1000000.

Rezultatai

Į rezultatus programa turi įrašyti vienintelį sveiką skaičių – minimalų įmanomą krūvų svorių skirtumą. Nepamirškite eilutės pabaigos simbolio!

Pavyzdys

Pradiniai duomenys Rezultatai
5
5
8
13
27
14
3
© Bronė Narkevičienė