Zadanie

Ak nevieš programovať, nezúfaj! Môžeš sa to naučiť a ešte za to získať body, ktoré sa ti budú počítať namiesto tejto úlohy.

Stačí, že pôjdeš na stránku Programátorskej Liahne (liahen.ksp.sk). Keď budeš riešiť sadu loops_cpp, bodmi, ktoré získaš, si môžeš nahradiť riešenie tejto úlohy. Stačí ak na spodku tejto stránky odovzdáš pdf-ko s prezývkou, ktorú používaš na Liahni.

Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Martinovi na [email protected]

Kde bolo tam bolo, išli si Maťko s Kubkom hádzať frisbee. Keďže už bol večer, ich starostlivá mamička im nedovolila ísť ďalej ako pred ich panelák. Pri hádzaní skúšali chalani rôzne triky a blbosti. Zrazu sa Maťkovi šmykla ruka a zhrozene pozeral, ako frisbee letí a pristáva na balkóne jedného z ich susedov.

Našťastie ešte nie je nič stratené. Ich dedo Jozef má totiž veľkú zbierku skladacích rebríkov, od úplne maličkých až po rebríky vyššie ako hora. Ale nie sú to len také hocijaké rebríky. Každý rebrík má špeciálnu prípojku, pomocou ktorej sa dokáže spojiť s ľubovoľným iným rebríkom. Dedo Jozef je taktiež veľmi poriadkumilovný, takže svoje rebríky má usporiadané podľa veľkosti.

Maťko a Kubko sa teda rozhodli, že sa spýtajú deda, či by im pár rebríkov nepožičal. Dedo Jozef súhlasil, ale dovolil im spojiť najviac dva rebríky. Ak by ich totiž spojili viac, spojené rebríky by mohli byť veľmi labilné. Výsledný rebrík nesmie byť primalý, lebo na frisbee nedosiahnu, ale ani príliš vysoký, pretože im bude zavadzať a k frisbee sa nedostanú. Mal by byť tak akurát, presne po ten nešťastný balkón.

Dedo Jozef požical Kubkovi a Maťkovi svoje rebríky, ale tí teraz potrebujú zistiť, či sa s nimi dostanú na balkón alebo nie.

Úloha

Vašou úlohou je napísať program, ktorý podľa dĺžok rebríkov a výšky balkóna zistí, či existuje jeden rebrík s výškou balkóna alebo či sa dá takýto rebrík zložiť z dvoch iných. Veľkosti rebríkov nemusia byť unikátne, čo znamená, že na vstupe sa môžu vyskytnúť dva rebríky rovnakej dĺžky.

Formát vstupu

Na prvom riadku sa nachádzajú dve medzerou oddelené čísla \(k\) a \(n\) (\(1 \leq k \leq 10^9\), \(1 \leq n \leq 300\,000\)), prvé z nich označuje výšku balkóna, na ktorý spadlo frisbee, a druhé počet dedových rebríkov.

Na nasledujúcom riadku je \(n\) čísel, ktoré udávajú výšky rebríkov. Tieto čísla sú zoradené od najmenšieho po najväčšie a ich veľkosti sú medzi \(1\) a \(q\) (\(1 \leq q \leq 10^9\)).

Formát výstupu

Vypíšte na jediný riadok výstupu ano, ak sa z najviac dvoch rebríkov dá posklať rebrík s výškou balkóna, inak nie.

Hodnotenie

Pripravili sme 3 sady vstupov. Platia pre ne nasledové horné obmedzenia pre hodnoty \(n\), \(k\) a \(q\).

Číslo sady 1 2 3
maximálne \(n\) \(1000\) \(300\,000\) \(300\,000\)
maximálne \(k\) a \(q\) \(1000\) \(1\,000\,000\) \(10^9\)

Príklady

Input:

6 5
1 2 3 3 4

Output:

ano

Výšku \(6\) vedia Maťko s Kubkom dosiahnuť buď pomocou dvoch rebríkov dĺžky \(3\) alebo rebríkov \(2\) a \(4\).

Input:

6 2
2 3

Output:

nie

Výška \(6\) by sa dala dosiahnuť napríklad dvoma rebríkmi dĺžky \(3\), ale k dispozícií máme iba jeden. Preto je odpoveď nie.

Input:

8 3
1 8 9

Output:

ano

Rebrík výšky \(8\) sa nachádza priamo medzi rebríkmi zo vstupu, takže odpoveď je ano.

Fungujúce, pomalé riešenie

Jedno z prvých riešení, čo by nám mohli napadnúť, je vyskúšať každú dvojicu a pozrieť sa, či má požadovanú výšku. Treba sa však aj pozrieť, či nie je samostatný rebrík, ktorý by mal správnu výšku. V najhoršom prípade overíme všetky dvojice rebríkov. Dvojíc je spolu \((n - 1) + (n - 2) + \ldots + 3 + 2 + 1\), pretože prvý rebrík môžeme spárovať s \((n - 1)\) zvyšnými, druhý s \((n - 2)\), atď. Ide teda o súčet čísel od \(1\) po \((n - 1)\)1

\[1 + 2 + 3 + \dots + N = \frac{N(N+1)}{2}\]

Takýto počet operácií potom zaokrúhlime na \(N^2\) a povieme, že časová zložitosť je \(O(N^2)\). Pamäťová zložitosť je \(O(N)\), pretože náš program si okrem konštantne veľa pomocných premenných pamätá iba vstupných \(N\) čísel.

ciel, pocet_rebrikov = list(map(int, input().split(" "))) # nacitame ciel a pocet rebrikov do premennych

rebriky = []
for vyska in input().split(): # nacitame vysky rebrikov
    rebriky.append(int(vyska))
je_riesenie = False # zacneme s predpokladom, ze riesenie neexistuje

if ciel in rebriky:
    je_riesenie = True # ak je rebrik spravnej vysky medzi rebrikmi, nic netreba skladat
else:
    for i in range(pocet_rebrikov): # prvy rebrik dvojice
        for j in range(i + 1, pocet_rebrikov): # druhy rebrik, zacneme rebrikom i+1, lebo vsetky predtym sme skusali
            if rebriky[i] + rebriky[j] == ciel:
                je_riesenie = True
                break
        if je_riesenie:
            break

if je_riesenie:
    print('ano')
else:
    print('nie')

Optimálne riešenie

Toto riešenie ťaží z faktu, že rebríky sú zoradené. Teraz môžeme implementovať takzvaných bežcov. Budú dvaja, nazvem ich ľavý a pravý. Každý bežec vždy stojí na jednom rebríku. Ľavý začne na prvom rebríku, pravý na poslednom. Predpokladáme, že rebríky sú zoradené vzostupne, teda najmenší je prvý. Postupne sa budú pohybovať smerom k sebe. Vždy sa pozrieme na súčet výšok rebríkov, na ktorých bežci práve stoja. Ak je to požadovaná výška, tak sme skončili a vypíšeme áno. Ak to tak nie je, tak musíme posunúť bežca. Ak je súčet výšok rebríkov viac, ako chceme, musíme tento súčet zmenšiť. Keďže bežci sa môžu pohybovať iba smerom k sebe, musí sa posunúť pravý bežec, pretože celkový súčet sa má zmenšiť, a najväčšie rebríky sú napravo. Naopak, ak je súčet malý, posunie sa ľavý bežec. Toto opakujeme, až kým sa bežci nestretnú, alebo kým nenájdeme správnu kombináciu.

V našom riešení pomocou bežcov pri jednom kroku while cyklu buď nájdeme riešenie, alebo posunieme jedného z bežčov. V najhoršom prípade sa tak bežci stretnú po \((n - 1)\) prechodoch while cyklu, takže časová zložitosť tohto riešenia je \(O(N)\). Pamäťová zložitosť je rovnako ako pri pomalšom riešení \(O(N)\) pretože si musíme zapamätať veľkosti rebríkov. Rýchlejšie riešenie ako \(O(N)\) nevymyslíme, pretože program musí aspoň načítať vstup, ktorý obsahuje \(N\) čísel, takže už samotné načítanie vstupu nám zaberie \(O(N)\) krokov.

  1. Pre súčet prvých \(N\) prirodzených čísel platí \(1 + 2 + ... + N = \frac{N(N + 1)}{2}\). Skúsme pre párne \(N\) sčítať prvé číslo s posledným, druhé s predposledným, atď. Výsledok bude zakaždým \(N+1\). Dvojíc s takýmto súčtom sme vytvorili \(N\), a preto je celkový výsledok \(\frac{N(N+1)}{2}\). Skúste si rozmyslieť podobnou úvahou, prečo vzorec platí aj pre nepárne \(N\).↩

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