Zadanie

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.

Úloha

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.

Formát vstupu

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++).

Formát výstupu

Vypíšte jediné číslo – číslo políčka, na ktorom sa bude KSPs nachádzať po tom, čo urobí \(k\) krokov.

Hodnotenie

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}\)

Príklad

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.


  1. Ak ešte KSPsa nepoznáte, nezúfajte. Stačí sledovať náš Instagram, kde sa čoskoro objaví!↩︎

Už na prvý pohľad je asi celkom zrejmé, že pohyb KSPsa môžeme pomerne jednoducho odsimulovať. Stačí si pamätať pole s pozíciami KSPsíkov, našu aktuálnu pozíciu a smer. Následne sa v každom kroku posunieme v poli o jeden index doprava/doľava (podľa aktuálneho smeru KSPsa) a overíme, či vzdialenosť od pôvodnej pozície KSPsa ku KSPsíkovi, ku ktorému sme práve došli, je najviac \(x\). V opačnom prípade sa vrátime na predchádzajúci index, zmeníme aktuálny smer KSPsa a skúsime sa posunúť sa v opačnom smere.

Ako vidíme, potrebujeme odsimulovať všetkých \(k\) krokov, teda časová zložitosť bude \(O(k)\). Pamäťová zložitosť je zase \(O(n)\), keďže si pamätáme celé pole s pozíciami KSPsíkov. Takéto riešenie mohlo (v závislosti od implementácie) získať na testovači približne polovicu bodov.

Vzorák

Aby sme z priamočiarej simulácie dostali vzorové riešenie nám stačí jednoduchý trik. Mohli sme si všimnuť, že pri simulácii sa KSPes vždy otočí pri tých istých dvoch KSPsíkoch. Pri veľkom počte krokov teda KSPes strávi väčšinu času behaním medzi týmito dvomi pozíciami.

Našu simuláciu upravíme nasledovne: Najskôr necháme KSPsa ísť doprava, až kým nenavštívi posledného dosiahnuteľného KSPsíka a jeho index si zapamätáme. Podobne si zistíme index najľavejšieho dosiahnuteľného KSPsíka.

Nech je rozdiel najpravejšieho a najľavšieho dosiahnuteľného indexu \(l\), potom KSPsovi bude trvať \(2l\) krokov, kým prejde všetkých KSPsíkov. Keďže sa po takomto “kolečku” KSPes vždy vráti na pôvodnú pozíciu, môžeme túto časť simulácie jednoducho preskočiť tým, že počet zostávajúcich krokov zmodulujeme \(2l\).

Nakoniec nám ostane niekoľko krokov, ktoré by sme mohli znova odsimulovať. V skutočnosti to ale ani nie je potrebné. Predpokladajme, že KSPs sa momentálne nachádza pri najľavejšom dosiahnuteľnom KSPsíkovi (tam sme ho totiž pri hľadaní najľavejšieho dosiahnuteľného KSPsíka presunuli). Teraz môže nastať jeden z dvoch prípadov: Ak je zostávajúci počet krokov \(k\) menší ako \(l\), stačí nám posunúť KSPsa v poli s pozíciami KSPsíkov o \(k\) indexov doprava. Naopak, ak je \(k > l\), finálny index KSPsa vypočítame ak od indexu napravejšieho dosiahnuteľného KSPsíka odčítame \(k - l\).

Na nájdenie najpravšieho a najľavšieho dosiahnuteľného KSPsíka budeme musieť prejsť najviac \(n\) psíkov. Následne iba vypočítame zvyšok po delení a finálnu pozíciu KSPsa v \(O(1)\), čiže celková časová zložitosť bude \(O(n)\). Pamäťová zložitosť ostáva stále rovnaká.

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