| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 58 | 29 | 22 | 51.163% |
Dvyniai Antanas ir Bronius gimtadienio proga gavo didelę dėžę sausainių. Iš viso joje yra N skirtingų sausainių, sunumeruotų nuo 1 iki N.
Dvyniams ne visi sausainiai patinka vienodai: i-ąjį sausainį Antanas vertintų ai balų, o Bronius jį vertintų bi balų. Kuo įvertis didesnis, tuo labiau sausainis patinka. Abu dvyniai žino, kiek balų kiekvienas iš jų skirtų kiekvienam sausainiui.
Mama pasiūlė dvyniams saldumynus pasidalinti šitaip: pirmasis vieną sausainį pasirinktų Antanas, paskui iš likusių sausainių vieną pasirinktų Bronius ir taip toliau, iki dėžė ištuštėtų.
Broliai nėra labai draugiški, todėl kiekvienas stengsis rinktis sausainius taip, kad pasibaigus dalyboms jo pasirinktų sausainių įverčių suma būtų kaip įmanoma didesnė už kito brolio pasirinktų sausainių įverčių sumą.
Kitaip tariant, jei dalybų metu Antanas pasirenka sausainius, kuriuos jis įvertina A balų, o Bronius pasirenka sausainius, vertus B balų, tai Antano tikslas yra pasiekti, kad dalybų pabaigoje skirtumas A − B būtų kaip galima didesnis, o Broniaus – kad skirtumas B − A būtų kuo didesnis.
Apskaičiuokite, kam bus lygus skirtumas A−B, jei abu dvyniai sausainius rinksis optimaliai.
Pirmoje eilutėje pateiktas sausainių skaičius N. Toliau eina N eilučių, kurių kiekvienoje pateikta po du sveikuosius skaičius:
Išveskite vieną sveikąjį skaičių – skirtumo A−B reikšmę, jei dvyniai sausainius dalinsis pagal optimalią strategiją.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 8 | 1 ≤ N ≤ 10, 0 ≤ ai, bi ≤ 1 000 |
| 2 | 18 | 1 ≤ N ≤ 22, 0 ≤ ai, bi ≤ 1 000 |
| 3 | 23 | 1 ≤ N ≤ 1 000, 0 ≤ ai, bi ≤ 1 000 |
| 4 | 7 | 1 ≤ N ≤ 200 000, 0 ≤ ai, bi ≤ 1 |
| 5 | 14 | 1 ≤ N ≤ 200 000, 0 ≤ ai, bi ≤ 1 000, ai = bi |
| 6 | 30 | 1 ≤ N ≤ 200 000, 0 ≤ ai, bi ≤ 1 000 |
4 100 1 200 2 400 4 300 3
596
Antanas pasirinktų trečią sausainį, Bronius – ketvirtą, tada Antanas – antrą, ir galiausiai Broniui atitektų pirmas.
A = a3 + a2 = 400 + 200 = 600
B = b4 + b1 = 3 + 1 = 4
2 10 100 11 50
-40
Šiuo atveju Antanas pasirinktų pirmą sausainį, o Broniui atitektų antras.
A = a1 = 10
B = b2 = 50
Jei Antanas būtų pasirinkęs antrą sausainį, A−B būtų lygus a2−b1 = 11−100 = −89, todėl tai nebūtų optimalus Antano pasirinkimas.
Olympiad > Lithuanian Olympiad in Informatics > Lithuanian Olympiad in Informatics 2015/2016 > National Round (1) > 10-12 Classes 1번