Saldainių dalybos


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

Užduotis

Sesuo ir brolis visada dalijasi saldumynais. Turėdami lyginį skaičių vienodų saldainių, jie pasidalintų juos po lygiai. Jei vienodų saldainių būtų nelyginis skaičius – vienu saldainiu daugiau gautų sesuo. Jei saldainis būtų tik vienas, brolis elgtųsi kilniai ir atiduotų jį sesei.

Visos problemos prasideda tuomet, kai saldainiai yra skirtingi – vieni skanesni už kitus.

Tačiau vaikai turi savo sistemą. Būdami patyrę saldainių valgytojai, jie žino kiekvieno saldainio vertę, ir yra įvertinę kiekvieną saldainį sveiku skaičiumi nuo 1 iki 1000. Dalindamiesi saldainius, vaikai padalija juos į dvi krūveles taip, kad abiejų krūvelių saldainių verčių sumos būtų kuo panašesnės. Iš šių dviejų saldainių krūvelių „vertingesnė“ atitenka sesei.

Jūsų užduotis – žinant visų saldainių įvertinimus, suskaičiuoti, kokios vertės saldainių krūvelės atiteks sesei ir broliui.

Pradiniai duomenys

Pirmoje pradinių duomenų failo eilutėje įrašytas sveikas skaičius N (1 <= N <= 100) – saldainių skaičius. Sekančiose N eilučių įrašyta po vieną sveiką skaičių \(v_{k}\)  (1 <= \(v_{k}\) <= 1000) – k-ojo saldainio vertę (k = 1, 2, …, N).

Rezultatai

Pirmoje ir vienintelėje rezultatų failo eilutėje turi būti įrašyti tarpu atskirti du sveikieji skaičiai B ir S. B – tai broliui atiteksiančių saldainių verčių suma, o S – sesei atiteksiančių saldainių verčių suma.

Pavyzdžiai

Pradiniai duomenys Rezultatai Paaiškinimas
5
3
1
5
2
1
6 6
Šiuo atveju saldainius pavyks pasidalinti „po lygiai“. Pavyzdžiui, broliui gali atitekti 1-as, 2-as ir 4-as saldainiai, o sesei – 3-as ir 5-as saldainiai.
6
3
4
5
2
1
6
10 11
Saldainių lygiai pasidalinti nepavyks. Broliui gali atitekti 1-as, 2-as, 4-as ir 5-as saldainiai, o sesei – 3-as ir 6-as saldainiai.
3
1
9
2
3 9
Nieko nepadarysi… Sesei atiteks 2-as saldainis, o broliui – likę du.