% Idee: Rocco Liiva
% Tekst: Rocco Liiva, Sandra Schumann

\documentclass[a4paper,11pt]{article}
\usepackage[et]{../../eio}

\begin{document}
\begin{ol}{\eio}{\ev 4.12.2025}{\yle}{}
    \begin{yl}{3}{Kummalised kapivargad}{kapp}{1 sek / 3 sek}{40 punkti}
        Sul on kapp, mille ukse avamiseks tuleb sisestada õige PIN-kood. Lukk on aga veidi katki ja reageerib nupuvajutustele ainult mõnikord. Kui kapp nupuvajutuse registreerib, kõlab piiks. Kapi avamiseks vajutad sa PIN-koodi iga numbri jaoks õiget nuppu niikaua, kuni see häält teeb.

        Kaks varast, Teedu ja Piibu, proovivad kappi sisse murda. Vargad luurasid kapi juures ning kogusid andmeid, kui sa viimati koodi sisestasid.
        Sinu õnneks pole Teedu ja Piibu tavalised vargad.
        Teedu on pime, kuigi kuuleb hästi, ning Piibu on kurt, kuigi näeb hästi.
        Seega mõtlesid nad kahe peale välja plaani.
        Teedu pani kirja, mitut piiksu ta kuulis. Piibu pani kirja kõik nupud, mida nägi sind vajutavat.

        Leia, mitu võimalikku uksekoodi peavad vargad kogutud andmete põhjal läbi proovima, et kindla peale kapp lahti saada.

        \sis Sisendi esimesel real on kaks täisarvu: Teedu kuuldud piiksude arv $N$ ja Piibu nähtud nupuvajutuste arv $M$ ($1 \le N \le 1\,000$, $1 \le M \le 10\,000$).

        Teisel real on Piibu kirja pandud nupuvajutuste jada, mis koosneb $M$ numbrist, igaüks $0$ kuni $9$.

        \val Väljundisse väljastada üks täisarv $K$: erinevate võimalike kogutud andmetele vastavate PIN-koodide arv. Kui võimalike PIN-koodide arv on suurem kui $2^{31}$, siis võib tegeliku vastuse asemel väljastada mistahes arvu, mis annab $2^{31}$-ga jagamisel vastusega sama jäägi (teisisõnu, võib väljastada $K$ mooduli $2^{31}$ järgi).

        \nde[0]{9cm}{3cm}

        Võimalikud õiged koodid on ``\texttt{12665}'', ``\texttt{12265}'' ja ``\texttt{11265}''.

        \nde[1]{9cm}{3cm}

        Ainus võimalik 10-kohaline kood on ``\texttt{1859382758}''.

        \nde[2]{9cm}{3cm}

        Võimalikke õigeid koode on $2\,333\,606\,220$, mis arvuga $2^{31}$ jagamisel annab jäägi $186\,122\,572$.

        Selles näites on sisendi teine rida lehele mahtumiseks poolitatud, aga seda on tehtud ainult ülesande tekstis. Testimiskeskkonas antakse nupuvajutuste jada programmi sisendisse alati ühel real. Ka testimiskeskkonnast alla laetavas näidete arhiivis on poolitamata reaga sisend.

        \nde[3]{9cm}{3cm}

        Ei ole võimalik, et sellele nupuvajutuste jadale vastab 7-kohaline PIN-kood.

        \clearpage
        \hnd \testidgrupis
        \begin{xenum0}
            \item (0 punkti) \naitedlyhem
            \item (3 punkti) Vastus on alati kas $0$ või $1$.
            \item (5 punkti) PIN-kood koosneb ainult numbritest $0$ ja $1$ ning kõik nullid on enne ühtesid.
            \item (10 punkti) $N, M \le 20$.
            \item (15 punkti) Vastus on väiksem kui $2^{31}$.
            \item (7 punkti) \piiranguteta
        \end{xenum0}
        \alamylkaupa
    \end{yl}
\end{ol}
\end{document}
