Zadanie

Bol obyčajný pondelkový večer. Ralbo sa spokojne pozeral na hviezdne kravy ako sa pomaličky šinuli do svojho chlieva. Keď vtom počul z rozhlasu:

“VYHLASUJEM POPLACH! VYHLASUJEM POPLACH! ASTEROIDNÉ T-REXY ÚTOČIA!”

“Do kelu!” vykĺzlo Ralbovi z úst. “Cvalom do chlieva!” zakričal Ralbo. Kravy, keď to začuli, tak sa plnou rýchlosťou rozbehli do chlieva. Keďže sú to veľmi velké zvieratá, tak doňho museli chodiť za sebou a nemohli sa predbiehať. Bohužial, nie všetky bežia rovnako rýchlo a Ralbovi bolo na prvý pohľad jasné, že niektoré to nezvládnu. “Musím ich zachrániť aspoň toľko, aby bolo dosť jedla pre stanicu na ďalší mesiac.” Ralbo teda hneď dobehol do žeriavu, ktorý bol nachystaný hneď vedľa a dal sa do dvíhania pomalých kráv.

Ten žeriav je ale veľmi starý, takže ho Ralbo chce používať čo najmenej.

Koľkokrát musí použiť ten starý žeriav, aby zachránil dosť kráv?

Úloha

Vieme počet kráv, ktoré treba stanici na mesiac, koľko času zostáva do príchodu asteroidných t-rexov, akou rýchlosťou bežia kravy a ako ďaleko sú od chlieva. Vašou úlohou je zistiť, najmenej koľkokrát treba použiť žeriav, aby prešlo dosť kráv, aby mala stanica jedlo na mesiac.

Žeriav sa používa tak, že Ralbo na chvíľu zoberie jednu kravu do vzduchu, nechá práve jednu kravu, aby pod ňou prebehla a potom ju znova položí. Žeriav pracuje a presúva sa instantne (trvá to 0 času).

Kravy sú veľmi veľké a nevedia prejsť okolo seba na ceste do chlieva a musia bežať za sebou. Ak rýchlejšia krava narazí na pomalšiu cestou do chlieva, tak bude bežať jej rýchlosťou a dorazia do chlieva naraz. Ak krava príde do chlieva presne vtedy, keď prídu asteroidné t-rexy, tak sa jej podarí ujsť.

Formát vstupu

Na vstupe najskôr dostaneme 3 čísla - počet kráv \(n\), čas do príchodu t-rexov \(t\) a počet kráv, ktoré potrebuje základňa na prežitie \(p\).

Potom dostaneme \(n\) riadkov s dvomi číslami. Na \(i\)-tom riadku budú čísla \(s_i, v_i\) - vzdialenosť \(i\)-tej kravy a jej rýchlosť. Vzdialenosti kráv od chlieva sú rastúce.

Platia nasledovné obmedzenia:

Sada 1 2 3 4
\(1 \leq n, p \leq\) \(100\) \(1\,000\) \(10^5\) \(10^5\)
\(1 \leq t \leq\) \(1\,000\) \(10^5\) \(2*10^9\) \(2*10^9\)
\(1 \leq \max v_i, \max s_i \leq\) \(1\,000\) \(10^5\) \(2*10^9\) \(2*10^9\)

Formát výstupu

Na výstup vypíšte jedno číslo - počet zdvihnutí, alebo -1, ak nie je možné dvíhať kravy tak, aby bolo dosť jedla pre základňu

Príklad

Input:

4 3 3
1 5
2 1
4 1
10 10

Output:

1

Stačí, aby Ralbo zodvihol predposlednú kravu, keď ju dobehne posledná krava

Input:

5 1 1
2 1
3 2
5 3
6 1
9 8

Output:

-1

Žiadna krava nestihne dobehnúť do chlieva, nech ich Ralbo zdvíha ľubovoľne

Input:

5 1 1
2 1
3 1
4 1
5 1
6 9

Output:

4

Iba posledná krava stihne dôjsť do cieľa. Ralbo musí zodvihnúť všetky pred ňou

Začiatočné pozorovania

Rozdeľme si kravy na dva druhy: 1) pomalé - tie, ktoré nestihnú dobehnúť do chlieva ani keby ich neblokovala žiadna iná krava 2) rýchle - tie, ktoré stihnú dobehnúť do chlieva ak ich nebude blokovať žiadna iná krava

Ak je nejaká krava za pomalou, tak sa nemá šancu dostať do chlieva bez toho, aby Ralbo zodvihol tú pomalú. Ak nejaká rýchla krava narazí na pomalú, tak v ten moment Ralbo určite nespraví zodvihnutie naviac, ak zdvihne tú pomalú. Ak by tú pomalú nezdvihol hneď, tak by sa tá rýchla nemusela dostať do chlieva.

Ak nejaká rýchla krava narazí na pomalšiu rýchlu, tak sa obe stihnú dostať do cieľa, takže ich výmena by bola zbytočná.

To znamená, že na vyriešenie úlohy potrebujeme nájsť \(p\) rýchlych kráv, ktoré sú najbližšie k chlievu. Potom pre každú rýchlu kravu potrebujeme zistiť, koľko pomalých je pred ňou.

Bruteforce

Spravíme si pole boolov, ktoré si označíme napríklad \(A\). V tomto poli si pre každú kravu budeme pamätať, či je pomalá alebo rýchla. To, či je krava rýchla spočítame tak, že vydelíme jej vzdialenosť od chlieva jej rýchlosťou a zistíme, či je menší ako čas príchodu t-rexov (dá sa to zvládnuť aj bez delenia, to nechám na vás :)). Keď nájdeme rýchlu kravu na indexe \(i\) a nemáme ešte \(p\) kráv Tak prejdeme poľom od \(0\)-tého indexu po \(i-1\) a za každú pomalú pripočítame k odpovedi 1. Nakoniec už iba vypíšeme odpoveď. Toto riešenie má časovú zložitosť \(O(n^2)\) keďže pre každú kravu potrebujeme skontrolovať všetky pred ňou. Pamäťovú má \(O(n)\), pretože si pamätáme pole kráv.

Zaujímavá myšlienka

Nás nezaujíma, kedy sme narazili na pomalú kravu. Pre každú rýchlu kravu potrebujeme vedieť iba koľko pomalých kráv je pred ňou. Na to nepotrebujeme pole, stačí nám na to iba jedna premenná.

Optimálne riešenie

Označme si premmenú \(slow\), kde si budeme pamätať počet pomalých kráv, ktoré sme už videli. Vždy, keď príde krava, skontrolujeme, či je pomalá. Ak je pomalá, inkrementujeme \(slow\). Ak je rýchla, tak k odpovedi pripočítame aktuálnu hodnotu \(slow\). Toto riešenie má časovú zložitosť \(O(n)\), pretože každú kravu spracujeme v konštantnonm čase. Pamäťovú má \(O(1)\), pretože si potrebujeme pamätať len konštante veľa premenných.

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