| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 49 | 25 | 18 | 43.902% |
Jõuluvana on koostanud nimekirja kinkidest, mida sellel aastal lastele viia. Iga kingi kohta on teada selle hind poes. Poemüüja, oletades, et jõuluvana pole kõige nupukam, pakub järgmist allahindlust: jõuluvana võib kahe poes müügil oleva kaubaartikli hinnad omavahel ära vahetada. Aita jõuluvanal välja mõelda, millised hinnad tuleks omavahel vahetada, et kingitustele kuluv summa oleks vähim võimalik.
Sisendi esimesel real on poes olevate kaubaartiklite arv $N$ (1ドル \le N \le 1,000円$).
Järgmisel 2ドル \cdot N$ real on $N$ kaherealist plokki. Iga ploki esimesel real on ühe kaubaartikli nimetus (1 kuni 20 väikest ladina tähte) ja teisel real selle täisarvuline hind $P$ (1ドル \le P \le 1,000円$). Võib eeldada, et kaupade nimetused poes on unikaalsed.
Järgmisel real on jõuluvana nimekirjas olevate kinkide arv $M$ (1ドル \le M \le 1,000円$).
Järgmisel $M$ real on igaühel ühe nimekirjas oleva kingi nimetus. Võib eeldada, et neid kõiki on poes piisavas koguses olemas.
Väljastada üks arv: vähim võimalik summa, mille eest saab kõik nimekirjas olevad kingid osta, kui enne arve kokkulöömist võib (aga ei pea) omavahel vahetada kahe artikli hinnad.
3 mudelauto 10 legokomplekt 20 raamat 30 4 mudelauto raamat legokomplekt raamat
70
Algsete hindade järgi oleks kinginimekirja kogumaksumus 10ドル+30+20+30=90$. Kui aga vahetada raamatu ja mudelauto hinnad, saame nimekirja kogumaksumuseks 30ドル+10+20+10=70$.
3 mudelauto 10 legokomplekt 20 raamat 30 2 mudelauto mudelauto
20
Algsete hindade järgi oleks kogumaksumus 10ドル+10=20$ ja iga vahetus teeks ostu ainult kallimaks. Seega on selles näites optimaalne hindu mitte vahetada.