5139. Nieosiągalna liczba [WZP09_2C]

Zadanie:
https://pl.spoj.com/problems/WZP09_2C

Skrócony opis problemu:

Mając dane $n$ oraz $n$ liczb posortowanych rosnąco i mamy wypisać najmniejszą liczbę, której nie da się otrzymać poprzez zsumowanie dowolnej ilości danych liczb.

Rozwiązanie naiwne:

Generujemy wszystkie podciągi danego ciągu, a następnie każdy sumujemy i zapisujemy w tablicy $tab[suma] = 1$ (na początku tablica jest wyzerowana). Następnie idziemy od początku tablicy (indeksu 1) i jeśli natrafimy na wartość 0, to wypisujemy indeks i kończymy przeszukiwanie.

Złożoność: $O(2^n)$. Bo podciągów ciągu o długości $n$ jest $\sum_{i=1}^n \binom{n}{i} = 2^n-1$.

Rozwiązanie sprytniejsze:

Możemy skorzystać z faktu, że ciąg jest posortowany. Idziemy zatem od najmniejszego elementu ciągu i porównujemy go z tymczasową zmienną $a$, w której jest najmniejsza liczba, której nie umiemy zbudować. Na początku $a=1$. Jeżeli otrzymamy liczbę $x$, która jest większa od naszego $a$ w danym momencie, to znaczy, że $a$ jest naszym ostatecznym wynikiem. Czemu? W danym momencie w $a$ jest wartość, której nie możemy osiągnąć. Do zbudowania $a$ potrzebny nam więc element mniejszy lub równy $a$ - jeśli otrzymamy element większy, to (przy założeniu, że wszystkie liczby z wejścia są dodatnie) co byśmy do niego nie dodali nie otrzymamy $a$. A jeśli $x$ będzie mniejsze lub równe $a$ to zwiększamy nasze $a$ o $x$. Oznacza to, że umiemy osiągnąć $a+x-1$, jako że wcześniej umieliśmy osiągnąć $a-1$. Ale czy na pewno umiemy osiągnąć każdą liczbę od $a$ do $a+x-1$? Tak, bo wtedy umieliśmy osiągnąć każdą od 1 do $a-1$. Więc jeśli chcemy np. osiągnąć $a$ to bierzemy $x$ i pozostaje nam dodać do niego $a-x$, a to zawiera się w przedziale $\left<1;a-1\right>$.

Złożoność: $O(n)$. Bo wczytujemy $n$ elementów i dla każdego z nich wykonujemy stałą liczbę operacji.

Ostateczny algorytm:

int main()
{
    int n, x, a, b;
    
    get(n);
    a = 1; // najmniejsza liczba, której w danym momencie nie możemy osiągnąć
    b = 0; // flaga, że jeszcze nie znaleźliśmy liczby, której nie możemy zbudować; jeśli będzie niezerowe, to znaleźliśmy
    while(n--)
    {
        get(x);
        if(!b) // jeśli do tej pory wszystko mogliśmy zbudować
        {
            if(x > a)b = a; // jeśli x>a to zapisz, że nie możemy zbudować a
            a ;+= x;
        }
    }
    printf(b ? b : a); // jeśli b > 0 to nie możemy zbudować b, a jeśli b=0 to wynikiem jest suma wszystkich liczb powiększona o 1, czyli a
}