17204. Winda [AL_12_01]

Zadanie:
http://spoj.com/ALGOLIGA/problems/AL_12_01
http://pl.spoj.com/problems/AL_12_01

Skrócony opis zadania:

Jest nam dany string (o długości $m$) opisujący historię operacji windy. Litera D oznacza, że winda pojechała jedno piętro w dół, a U oznacza, że pojechała do góry. Naszym zadaniem jest stwierdzić czy dana historia jest poprawna, czyli winda nie zjechała poniżej parteru (o numerze 1) lub nie wjechała powyżej najwyższego piętra (o numerze $n$).

Rozwiązanie naiwne:

Możemy dla każdego piętra od 1 do $n$ wykonać symulację ruchu windy przyjmując to piętro za początkowe. Jeśli któraś symulacja nie wyjdzie poza przedział pięter, to wypisujemy, że dana historia jest możliwa.

Złożoność: $O(n \cdot m)$, gdyż dla każdego z $n$ pięter przechodzimy $m$ operacji w historii.

Rozwiązanie sprytne:

Możemy zauważyć, że nie musimy sprawdzać historii dla każdego możliwego piętra. Możemy sobie założyć, że winda wystartowała sobie z jakiegoś piętra $x$. Dla prostoty weźmy $x=0$. A więc mamy sobie windę na jakimś początkowym (zerowym) piętrze. Nie wiemy więc, ile mamy pięter pod piętrem $x$ ani ile jest nad nim. Czy nam to przeszkadza? Nie. Wykonujemy bowiem operacje zapamiętując najniższe i najwyższe osiągnięte piętro. A więc powiedzmy, że zjechaliśmy najniżej 6 pięter poniżej $x$ oraz 3 piętra powyżej $x$. Jak można się domyślić, wystarczy przyjąć najniższe osiągnięte piętro za parter i sprawdzić czy najwyższe piętro mieści się w granicy budynku. W powyższym przykładzie odwiedziliśmy zatem 6+3+1=10 pięter. Jeśli $n \le 10$ to historia jest możliwa. W przeciwnym wypadku musimy wypisać NIE.

Złożoność: $O(m)$.

Algorytm:

int main()
{
    int n, min, max, x, i;
    char s[MAX_N];

    get(n, s);
    for(min = max = x = i = 0; s[i]; ++i)
    {
        x += s[i] == 'U' ? 1 : -1;
        if(x < min)
            min = x;
        if(x > max)
            max = x;
    }
    print(max-min+1 > n ? "NIE" : "TAK");
}

Optymalizacja:

Ów warunek $max-min+1 > n$ można również sprawdzać w pętli for. Jeśli bowiem w trakcie przeglądania historii zorientujemy się, że jest ona niemożliwa, to nie musimy weryfikować jej dalej.