2. Aha, psíky! vzorové riešenie

4 2 10 3
1 3 5 7

3

3 1 1 47
0 2 4

2

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.

n, s, x, k = [int(x) for x in input().split()]
ksps = [int(x) for x in input().split()]

pos = s
direction = 1

for step in range(k):
    npos = pos + direction
    if 0 <= npos < len(ksps) and abs(ksps[npos] - ksps[pos]) <= x:
        pos = npos
    else:
        direction *= -1
        npos = pos + direction
        if 0 <= npos < len(ksps) and abs(ksps[npos] - ksps[pos]) <= x:
            pos = npos

print(ksps[pos])

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, s, x, k;
    cin >> n >> s >> x >> k;

    vector<int> ksps(n);
    for (int i = 0; i < n; i++) {
        cin >> ksps[i];
    }

    int pos = s;
    int direction = 1;

    for (int s = 0; s < k; s++) {
        int npos = pos + direction;

        if (0 <= npos && npos < n && abs(ksps[npos] - ksps[pos]) <= x) {
            pos = npos;
        } else {
            direction *= -1;
            npos = pos + direction;
            if (0 <= npos && npos < n && abs(ksps[npos] - ksps[pos]) <= x) {
                pos = npos;
            }
        }
    }

    cout << ksps[pos] << '\n';
    return 0;
}

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

n, s, x, k = [int(x) for x in input().split()]
ksps = [int(x) for x in input().split()]
pos = s

while k > 0 and pos+1 < n and abs(ksps[pos] - ksps[pos+1]) <= x:
    pos += 1
    k -= 1
right = pos

while k > 0 and pos-1 >= 0 and abs(ksps[pos] - ksps[pos-1]) <= x:
    pos -= 1
    k -= 1
left = pos

length = right - left

if k == 0 or length == 0:
    print(ksps[pos])
    exit()

k = k % (2*length)
if k > length:
    pos = right - k + length
else:
    pos = left + k

print(ksps[pos])

#include <iostream>
#include <vector>
using namespace std;

typedef long long int lli;

int main() {
    lli n, s, x, k;
    cin >> n >> s >> x >> k;

    vector<lli> ksps(n);
    for (lli i = 0; i < n; i++) {
        cin >> ksps[i];
    }

    lli pos = s;

    while (k > 0 && pos+1 < n && abs(ksps[pos] - ksps[pos+1]) <= x) {
        pos++;
        k--;
    }
    lli right = pos;

     while (k > 0 && pos-1 >= 0 && abs(ksps[pos] - ksps[pos-1]) <= x) {
        pos--;
        k--;
    }
    lli left = pos;
    lli length = right - left;

    if (k == 0 || length == 0) {
        cout << ksps[pos] << '\n';
        return 0;
    }

    k %= 2*length;
    
    if (k > length) {
        pos = right - k + length;
    } else {
        pos = left + k;
    }

    cout << ksps[pos] << '\n';
    return 0;
}