V každej správnej záhradke by mal byť strážny pes. Preto aj my máme na záhradke nášho KSPsa1, ktorý dáva pozor, aby nenastal žiadny nepríjemný incident. Záhradka je ale veľmi veľká a sám ju neustriehne. Preto má v záhradke aj pomocníkov – malých KSPsíkov! Keďže sú to ale ešte len malé šteniatka, musí na nich dávať dobrý pozor a preto teraz celé dni chodí od jedného k druhému a kontroluje ich.
KSPsíkovia sú, prirodzene, veľmi inteligentní, no trochu nedočkaví. Preto si začali v hlave počítať, pri ktorom z nich zastane KSPs niekedy v budúcnosti. Jednému z nich sa už ale počítať v hlave nechce, a preto by chcel, aby ste mu pomohli.
Naša záhradka má tvar jednodimenzionálneho (jednorozmerného) poľa, ktorého políčka sú buď prázdne, alebo je na nich KSPsík. Tí sa nehýbu a po celý čas zostávajú na svojich pôvodných políčkach. KSPs sa na začiatku nachádza na niektorom políčku s KSPsíkom a pozerá sa smerom doprava, potom sa v každom kroku správa nasledovne:
Ak vidí vo svojom smere nejakého KSPsíka vo vzdialenosti $\le x$, ide za ním.
Ak nie, tak zistí, že či je opačným smerom nejaký KSPsík vo vzdialenosti $\le x$. Ak je, tak sa otočí a ide za ním.
Inak ostáva na svojom mieste.
Vašou úlohou je zistiť, na ktorom políčku sa bude KSPs nachádzať po $k$ takýchto krokoch.
Na prvom riadku dostanete štyri čísla $n, s, x, k$, kde $n$ je počet KSPsíkov, $s$ označuje KSPsíka, na ktorého políčku KSPs začína, $x$ je vzdialenosť na ktorú KSPs dovidí a $k$ je počet krokov.
Nasleduje jeden riadok, ktorý obsahuje $n$ usporiadaných celých čísel $n_i$, kde $n_i$ označuje pozíciu $i$-tého KSPsíka. KSPs začina na políčku $n_s$.
Dajte si pozor, že niektoré čísla na vstupe sa nemusia zmestiť do obyčajnej 32-bitovej premennej. Odporúčame použiť 64-bitové premenné (long long v C/C++).
Vypíšte jediné číslo – číslo políčka, na ktorom sa bude KSPs nachádzať po tom, čo urobí $k$ krokov.
Je 8 sád vstupov. Platia v nich nasledovné obmedzenia:
| Sada | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| $0 < n \le$ | $10$ | $1000$ | $10^4$ | $10$ | $1000$ | $10^4$ | $10^6$ | $10^6$ |
| $0 \le n_i \le$ | $100$ | $1000$ | $10^7$ | $100$ | $10^5$ | $10^7$ | $10^{12}$ | $10^{12}$ |
| $0 \le k \le$ | $10$ | $1000$ | $10^5$ | $10^6$ | $10^8$ | $10^8$ | $10^{18}$ | $10^{18}$ |
Input:
4 2 10 3
1 3 5 7
Output:
3
KSPs začína na políčku s číslom $5$, v ďalšom kroku pôjde doprava k najbližšiemu KSPsíkovi na políčko $7$. Potom sa už ale musí otočiť a vrátiť na políčko $5$, keďže ďalej už nie je žiadny KSPsík. V poslednom kroku prejde na políčko $3$.
Input:
3 1 1 47
0 2 4
Output:
2
KSPs nevidí na žiadneho ďalšieho KSPsíka (keďže sú príliš ďaleko) a preto ostane na pôvodnom mieste.
Korešpondenčný seminár z programovania zastrešuje občianske združenie Trojsten.
Trojsten, o.z.
FMFI UK, Mlynská dolina
842 48 Bratislava
Programátorská súťaž pre základoškolákov
Materiály a úlohy na výučbu programovania
Intenzívny programátorský zážitok v lete