Zadanie
Jožko Číž už dlhé roky prebýva na istej planétke. Zo začiatku sa mu všetko zdalo zaujímavé a bol celý nadšený. Časom však nadšenie opadlo a začínal sa trochu nudiť. Planétka má slabú gravitáciu a dobre sa tu skáče. To však Číž už dobre pozná. Tentoraz však uvidel čížmy. Nie obyčajné čížmy. Vesmírne skákacie čížmy! Pozrel sa ďalej a uvdiel ďalšie. A ďalšie. A ďalšie! Videl celú cestu, na ktorej bolo veľa rôznych skákacích čížiem.
Rozhodol sa, že sa vydá na túru na koniec tejto cesty. Samozrejme sa mu nechce chodiť a prezúvať čížmy po tom, čo sa vybijú, je pre energeticky úsporného Číža neprípustné. S každými čížmami dokáže preskákať inú vzdialenosť dokedy sa vybijú. Zaujímalo by ho, koľko najmenejkrát sa musí prezuť na to, aby sa dostal na koniec cesty.
Úloha
Máme cestu danej dĺžky na ktorej začiatku sa nachádza Číž. Na niektorých pozíciách cesty sú čížmy, do ktorých sa môže Číž prezuť, ak je na ich pozícii. Každé čížmy majú inú vzdialenosť, ktorú je nimi možné preskákať. Vašou úlohou je zistiť, koľko najmenej krát musí čížmy prezuť aby sa dostal na koniec cesty, bez toho aby chodil, alebo zistiť, že to možné nie je.
Formát vstupu
V prvom riadku sú tri celé čísla \(n, d, b\). Číslo \(n (1 \leq n \leq 500\,000)\) udáva počet čížiem na ceste. Číslo \(d (2 \leq d \leq 10^9)\) udáva dĺžku cesty a \(b (1 \leq b \leq 10^9)\) udáva vzdialenosť ktorú je možné prejsť s čížmami, ktoré má Číž už obuté.
Následuje \(n\) riadkov popisujúcich čížmy na ceste. Na i-tom riadku, sú celé čísla \(A_i (1 \leq A_i < d)\) a \(B_i (1 \leq B_i \leq 10^9)\) popisujúce pozíciu čížiem na ceste a vzdialenosť ktorú je s nimi možné prejsť.
Je zaručené, že hodnoty \(A_i\) sú zoradené vzostupne. Teda čížmy sú vypísané postupne v poradí, ako sa nachádzajú na ceste. Na jednej pozícii sa tiež nachádzajú vždy najviac jedny čízmy.
V jednotlivých sadách platia aj následujúce obmedzenia pre \(n\):
Sada | 1 | 2 | 3 | 4 |
---|---|---|---|---|
\(1 \leq n \leq\) | \(15\) | \(2\,000\) | \(100\,000\) | \(500\,000\) |
Formát výstupu
Vypíš jeden riadok a v ňom jedno celé číslo. Najmenší možný počet prezutí čížiem potrebný na prejdenie na koniec cesty. Ak cestu nie je možné prejsť pomocou čížiem, vypíšte \(-1\).
Príklady
Input:
5 20 1
1 2
2 4
3 1
5 16
7 20
Output:
3
Musíme zobrať prvé čížmy a následne sa najviac oplatia druhé. Potom vieme zobrať štvrté (na pozícii 5), s ktorými sa vieme dostať až na koniec cesty.
Input:
4 10 2
1 2
2 2
6 4
8 1
Output:
-1
Síce vieme zobrať prvé, alebo druhé čížmy, ale potom sa už k ďalším nevieme dostať a ani dôjsť na koniec cesty. Odpoveď je teda \(-1\).
Ak sa nachádzame na pozícii \(x\) a vieme prejsť ešte \(d\), vieme sa dostať na všetky pozície až do \(x + d\). Spomedzi čižiem na týchto pozíciách si tak chceme vybrať nejaké čižmy, ktoré nás dovedú k optimálnej odpovedi.
Intuitívne dáva zmysel, že to budú také čižmy \(i\), že ich \(A_i + B_i\) je najväčšie spomedzi všetkých dostupných čižiem. Uvažujme ale, že by sme tieto čižmy nezobrali a zobrali nejaké iné čižmy \(j\). V následujúcom kroku by sme mali na výber z čižiem z nejakej podmnožiny tých, ku ktorým sme sa vedeli dostať pomocou čižiem \(i\), pretože by sme sa mohli dostať na všetky čižmy, okrem tých, ktoré sú na ceste na pozíciách \(x + A_j + B_j + 1\) až \(x + A_i + B_i\). (pre každé \(j\) musí platiť, že \(A_j + B_j \leq A_i + B_i\), keďže \(A_i + B_i\) je maximálne).
Keďže teraz vieme, že máme na výber stále iba z podmnožiny čižiem dosiahnuteľných z \(i\), ak zoberieme čižmy \(i\), vieme, že výber čižiem v ďalšom kroku bude najväčší možný. Z toho vyplíva, že po \(k\) krokoch budeme vždy najďalej ako sa dá, pretože stále robíme najväčší krok, ktorý nám aj ako sme si ukázali, najviac zväčší výber. To nám zaručí, že dôjdeme na koniec cesty v najmenšom počte krokov, ak je to možné. Ak to možné nie je, zistíme to tak, že z aktuálnych čižiem sa už nie je možné dostať do iných čižiem, ktorými vieme dôjsť ďalej a nie je možné sa s nimi dostať ani do cieľa.
Prvé riešenie
Popísaný postup môžeme simulovať a dostaneme sa k nejakému riešeniu. Z každej pozície, kde sme si obuli nové čižmy sa pozrieme na čižmy v dosiahnuteľnej vzdialenosti vpravo. Spomedzi týchto čižiem následne vyberieme také, ktorými sa dostaneme najďalej a tento proces opakujeme, až dokým nedôjdeme na koniec cesty.
Časová zložitosť
Aj keď tento algoritmus možno na prvý pohľad vyzerá, ako \(O(n^2)\), vieme dokázať, že na žiadne čižmy sa nepozrieme viac ako dvakrát. Ak sa pozeráme na čižmy \(i\), prezrieme všetky čižmy na úseku \(A_i\) až po \(A_i + B_i\). Z týchto vyberieme najlepšie čižmy \(j\). Následne sa pozrieme na všetky čižmy na úseku od \(A_j\) až po \(A_j + B_j\). Druhýkrát sa počas toho pozrieme na čižmy na úseku od \(A_j\) po \(A_i + B_i\). Nikdy sa ale nepozrieme na tieto čižmy tretíkrát, pretože na tomto úsek už nemôžu byť žiadne lepšie čižmy (s ktorými by sme sa dostali ďalej ako \(A_j + B_j\)), pretože inak by sme ich zobrali namiesto \(j\). Teda nutne vyberieme nejaké, čo sa nachádzajú až za \(A_i + B_i\). Toto platí pre každú dvojicu po sebe idúcich vybratých čižiem a teda na všetky úseky na ktoré sa pozrieme druhýkrát sa nepozrieme už tretíkrát.
Z toho už vyplýva, že časová zložitosť je \(O(2n) = O(n)\), keďže čižmy sú už na vstupe zoradené. Pamäťová zložitosť je tiež \(O(n)\).
Druhé riešenie
Existuje aj iné, rovnako efektívne riešenie s ľahšou analýzou časovej zložitosti. Môžeme si všimnúť, že zaujímajú nás iba také čižmy \(i\), že \(A_i + B_i > A_j + B_j\) pre všetky \(i > j\). Čižmy tak stačí postupne prejsť a zapamätať si iba tie pre ktoré platí spomenutá podmienka. Overovať všetky \(j\) nie je treba, pretože posledné zapamätané čižmy budú stále tie s najväčším dosahom a tak stačí podmienku skontrolovať pre nich.
Následne postupne prejdeme novo vytvorený zoznam a stále keď máme čižmy \(i\), zoberieme posledné zapamätané čižmy \(j\), ktore sú za \(i\), a ktorých \(A_j < A_i + B_i\). Tými sa už dostaneme najďalej ako je to možné zo všetkých dosiahnuteľných čižiem od čižiem \(i\). Toto opakujeme podobne ako v prvom riešení. Druhé riešenie je teda veľmi podobné tomu prvému, akurát odstránime nejaké čižmy, aby sme sa v druhom cykle pozreli na všetky ostávajúce čižmy iba raz. Časová aj pamäťová zložitosť je rovnaká ako pri prvom riešení.
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ť.