Zadanie
Všetci vieme, že mimozemštania existujú. Dokonca už aj navštívili Zem. Presnejšie povedané, havarovali do nej. Toto miesto je bežne známe ako Area 51. Žiaľ, mimozemštanov sa zmocnilo americké letectvo. Oni si ale zaslúžia byť voľní! Poďme ich zachrániť!
Dvojičky Matty a Robrets pomocou eventu na Facebooku zohnali milióny ochotných ľudí. Ich tímu sa už podarilo preniknúť do tajnej americkej základne, stačí im už len odtiaľ vyniesť mimozemšťanov. Každý človek unesie maximálne dvoch mimozemštanov – jedného v každej ruke. Ale s mimozemšťanom pod pazuchou sa ťažšie beží. Mimozemštanov preto potrebujú rozdeliť tak, aby ten, čo bude niesť najväčšiu záťaž, toho niesol čo najmenej. Preniknutie do základne bolo veľmi náročné, a počítať sa im už nechce. Preto im musíte pomôcť vy!
Úloha
V Area 51 je \(m\) mimozemšťanov. Na to, aby sme ich zachránili, máme \(n\) ľudí. Každý človek unesie maximálne dvoch mimozemšťanov. Každý mimozemšťan má nejakú konkrétnu hmotnosť \(H_i\) udanú v miligramoch.
Mimozemšťanov musíme rozdeliť medzi jednotlivých ľuďí tak, aby maximálna hmotnosť ktorú má niektorý človek niesť, bola najmenšia možná.
Formát vstupu
V prvom riadku vstupu sú čísla \(n\) a \(m\) (\(1\leq m\leq 2n\leq 200\,000\)) udávajúce počet ľudí a mimozemšťanov.
V druhom riadku je \(m\) čísiel \(H_i\) (\(1\leq H_i\leq 1\,000\,000\,000\)) udávajúcich hmotnosti mimozemšťanov v miligramoch.
Formát výstupu
Pre každého z \(n\) ľudí vypíšte jeden riadok obsahujúci dve čísla – hmotnosti mimozemšťanov v jednotlivých rukách. Ak má človek niektorú ruku prázdnu, vypíšte hmotnosť 0.
Môžete vypísať ľubovoľné správne riešenie.
Príklady
Input:
3 4
5 1 6 7
Output:
7 0
0 6
1 5
Najťažší náklad nesie prvý človek, a to \(7mg\)
Input:
3 6
1 2 2 3 3 4
Output:
2 3
4 1
3 2
Všetci nesú rovnakú hmotnosť, a to \(5mg\).
Najprv sa zamyslime nad tým, ako vyriešiť prípad \(n=2\), \(m=4\), teda pre dvoch ľudí a štyroch mimozemšťanov. Označme si hmotnosti mimozemšťanov \(a \leq b \leq c \leq d\). Akými spôsobmi ich môžeme rozdeliť medzi dvoch ľudí? Sú iba tri rôzne možnosti: \(a+b\) a \(c+d\); \(a+c\) a \(b+d\); alebo \(a+d\) a \(b+c\). Všimnite si, že všetky ostatné rozdelenia sú zhodné s jedným z týchto rozdelení.
Rozdelenie \(a+b\) a \(c+d\) zjavne nie je najlepšie, keďže \(c+d\) je väčšie alebo rovné ako každý iný súčet. Stačí nám teda porovnať iba rozdelenie \(a+c\) a \(b+d\) s rozdelením \(a+d\) a \(b+c\). V prvej možnosti vidíme, že človek s \(b+d\) má najťažší náklad, keďže \(b+d \geq a+c\), lebo \(b \geq a\) a zároveň \(d \geq c\). Ak ale túto hmotnosť porovnáme s tretím rozdelením, zistíme, že tretie rozdelenie je výhodnejšie, keďže \(b+d \geq a+d\) (lebo \(b \geq a\)) a zároveň \(b+d \geq b+c\) (lebo \(d \geq c\)). Najvýhodnejšie rozdelenie týchto štyroch mimozemšťanov teda je \(a+d\) a \(b+c\).
Teraz skúsme vyriešiť prípad \(n=3, m=6\); označme si hmotnosti mimozemšťanov \(a \leq b \leq c \leq d \leq e \leq f\). Podobným uvažovaním ako vyššie vieme ukázať, že prvý človek musí niesť hmotnosť \(a+f\). Zvyšných mimozemšťanov potom musíme rozdeliť rovnakým postupom ako pre \(n=2, m=4\), teda na \(b+e\) a \(c+d\).
Takto vieme pokračovať a dokázať, že pre ľubovoľné zadanie \(m=2n\) musíme mimozemšťanov rozdeliť na najťažšieho s najľahším, druhého najťažšieho s druhým najťažším, tretieho najťažšieho s tretím najľahším, atď.
Ako môžeme toto riešenie zovšeobecniť na ľubovoľné \(m \leq 2n\)? Mohli by sme uvažovať nad tým, koľko ľudí bude mať koľko voľných rúk, a priradiť im najťažších mimozemšťanov, a zvyšok vyriešiť ako vyššie. Pri tomto riešení sa ale dá ľahko zabudnúť na prípad \(m<n\). A ako ste sa mnohí sami presvedčili, program ktorý správne rieši iba \(m \geq n\), mohol dostať len 2 body. Oveľa jednoduchšie je predstaviť si, že v každej voľnej ruke je mimozemšťan s hmotnosťou \(0\). Všimnite si, že celkovú hmotnosť, ktorú nesie daný človek to neovplyvní, a môžeme potom využiť vyššie popísané riešenie pre \(m=2n\).
Výsledný program teda najprv načíta hmotnosti \(m\) mimozemšťanov, doplní ich o \(2n-m\) mimozemšťanov s hmotnosťou \(0\), utriedi podľa hmotnosti, a vypíše pre každého človeka doteraz nepriradeného najťažšieho a najľahšieho mimozemšťana.
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.