Zadanie

Ísť na rodinnú oslavu asi nebol až taký dobrý nápad ako by sa mohlo zdať. Nie že by koláče neboli fajn, alebo by si nemal rád svojich čudných príbuzných, ale tá tvoja rozvetvená rodina… Teda, aj tá by bola v pohode, ak by ste nemali v rodine toľko dvojičiek.

Našťastie, nikdy si nemusel vedieť mená tvojich príbuzných, ich vek, a ani to, či sú dvojičky… Až doteraz… Prikývol si sestre tety vnučky krstnej tvojej starej mamy z druhého kolena, že jej pomôžeš s jej nečakaným nápadom, odovzdávaním ceny pre najstaršie dvojičky z minulej oslavy.

Sestra tety vnučky krstnej tvojej starej mamy z druhého kolena cenu odovzdala, nechala ti fotku z predošlej oslavy a išla sa najesť koláčov a kapustnice. Aj ty by si sa rád najedol, no po chvíli ťa, ako jej asistenta, začali prenasledovať nespokojné dvojičky, ktoré cenu nedostali s tým, aby si im dokázal, že cena bola odovzdaná správnemu páru dvojičiek.

Chcú teda, aby si im povedal, koľko párov dvojičiek bolo na oslave, a aké staré boli najstaršie dvojičky… Na tvojom mieste by som im rýchlo, ale najmä správne, odpovedal. Chceš od nich predsa dostať na Vianoce nejaké darčeky…

Úloha

Dostanete veky ľudí, ktorí sú zachytení na fotke. Týchto ľudí je \(n\). Na oslave sa nachádzalo \(n+1\) ľudí. Človek, ktorý fotku fotil, nebol na fotke. Ľubovolní dvaja ľudia, okrem dvojice tvoriacej dvojičku, sú rozdielne starí.

Vypíšte, koľko najviac párov dvojičiek mohlo byť na oslave, a vek najstaršieho možného páru dvojičiek, ktorý bol na oslave, pričom môžete predpokladať, že na oslave sa nachádzal aspoň jeden pár dvojičiek.

Formát vstupu

Vstup tvorí dvojica riadkov, ktorá popisuje fotku z oslavy.

V prvom riadku sa nachádza číslo \(1\leq n \leq 100\,000\) , počet ľudí na fotke.

Na druhom riadku sa nachádza \(n\) čísel \(a_i\) oddelených medzerami, \(1\leq a_i \leq 200\,000\)1, ktoré označujú veky ľudí na fotke.

Formát výstupu

Vypíšte dve, medzerou oddelené čísla. Koľko najviac párov dvojičiek mohlo byť na oslave, a najväčší možný vek páru dvojičiek, ktorý bol na oslave.

Príklad

Input:

8
12 12 16 102 47 16 102 47

Output:

4 102

  1. Okrem dvojičiek nie je vo vašej rodine výnimočná ani dlhovekosť.↩︎

Vašou úlohou bolo zistiť vek najstaršieho možného páru dvojičiek, a najväčší možný počet dvojičiek na oslave. K správnemu vyriešeniu úlohy si bolo potrebné uvedomiť, že aj fotograf môže byť dvojička, a dokonca môže byť aj súčasťou najstaršieho páru dvojičiek.

Pri hľadaní maximálneho veku páru dvojičiek, sa môže stať buď, že najstarší pár dvojičiek je na fotke, alebo ho tvorí najstarší jednotlivec z fotky a fotograf. Z tohto nám teda vyplýva, že vek najstaršieho možného páru dvojičiek bude maximum z vekov na fotke, bez ohľadu na to, či je tam tento vek dvakrát, alebo len raz.

Celkový počet dvojičiek na oslave ale nemusí byť rovný počtu dvojičiek na fotke. Môže byť o jedna väčší. Tento prípad nastane vždy, keď je na fotke aspoň jeden jednotlivec. Potom fotograf a tento jednotlivec tvoria spoločne dvojičky.

Keď už vieme, čo máme urobiť, pozrime sa na to, ako to urobiť.

Riešenie v čase \(O(n)\) a pamäti \(O(maximalny\_vek)\)

Chceli by sme vedieť zistiť počet ľudí daného veku. To vieme urobiť tak, že si najprv vytvoríme pole dĺžky \(maximalny\_vek\), ktoré celé vynulujeme. Jednotlivé hodnoty na indexoch tohoto poľa budú predstavovať počty ľudí daného veku. Následne prechádzame veky na fotke a zväčšujeme hodnotu na indexe daného veku o jedna. Na konci v celom poli spočítame počet indexov (počet vekov) s hodnotou \(2\) (počet dvojičiek), a zistíme, či existuje index s hodnotou \(1\)(nejaký jednotlivec na zdvojičkovanie s fotografom). Takto zistíme najväčší možný počet dvojičiek. Maximálny vek dvojičiek nájdeme ako najväčší index v poli s nenulovou hodnotou. Úlohu sme teda vyriešili v časovej zložitosti \(O(n + maximalny\_vek)\), a pamäťovej zložitosti \(O(maximalny\_vek)\).

Riešenie v čase \(O(n log(n))\) a pamäti \(O(n)\)

Najprv si veky z fotografie utriedime1. Následne si prejdeme pole a hľadáme miesta, kde majú dva za sebou nasledujúce prvky v poli rovnakú hodnotu (dvojičky). Ak existuje nejaký jednotlivec, teda \(pocet\_dvojiciek \cdot 2 \neq n\), môže tento človek urobiť dvojičku s fotografom, čiže zvýšime počet dvojičiek o \(1\). Maximálny možný vek dvojičiek je posledný prvok v poli, keďže pole máme utriedené od najmenšieho po najväčšie.

  1. funkcia sort vo väčšine programovacích jazykov↩︎

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ť.