\documentclass[12pt]{article}
\input{structure.tex}
\fancyhead[R]{
	\begin{minipage}{\textwidth}
		\raggedleft
		\includegraphics[width=2cm]{./logo2.png}
	\end{minipage}
}
\renewcommand{\bottomtitlespace}{2cm}

\begin{document}
	
\renewcommand{\tl}{$2$ сек.}
\renewcommand{\ml}{$256$ MB}
\problem{Задача T82. ПЕЩЕРА}
\addauthor{Автор: Иван Лупов}{2026}{08}{28}
\renewcommand{\header}{
	НАЦИОНАЛНА ШКОЛА ПО ИНФОРМАТИКА\\
	КОНТРОЛНО СЪСТЕЗАНИЕ\\
	Габрово, 28 август 2026 г.\\
	8 клас
}

Будите се облени от студена пот. Сънували сте сън, не, кошмар. В пещера сте. Изходът навън е защитен от $N$ последователни стоманени врати, всяка разположена зад предходната, и $N$ ключа, всеки свързан с една различна врата.

Вратите са номерирани от $0$ до $N-1$, като врата $0$ е най-близо до Вас. Има и $N$ ключа, също номерирани от $0$ до $N-1$, но не знаете кой ключ коя врата управлява.

Всеки ключ може да бъде в едно от две положения -- нагоре (стойност $0$) или надолу (стойност $1$). Само едно от тези положения е правилно за даден ключ. Ако ключът е в правилното положение, съответната врата ще бъде отворена. Ако е в грешното -- вратата ще бъде затворена. Правилните положения могат да са различни за различните ключове, и в началото Вие нямате никаква информация за тях.

Можете да избирате произволна комбинация от положения на ключовете, след което да влезете в пещерата, за да видите коя е първата затворена врата. Вратите не са прозрачни -- щом срещнете първата затворена врата, не може да продължите нататък, както и да видите какво има зад тази врата. Имате право да изпробвате най-много $70~000$ комбинации. Целта Ви е да определите както правилното положение за всеки ключ, така и коя врата управлява.

\subsection{Детайли по имплементацията}
Напишете програма \texttt{cave}, имплементираща функцията:
\begin{lstlisting}
 void explore(int N)
\end{lstlisting}

Функцията ще бъде извикана веднъж и трябва да използва предоставените функции на журито, за да определи:

\begin{itemize}[label={--}]
	\item правилното положение (нагоре/надолу) за всеки ключ;
	\item номера на вратата, която управлява всеки ключ.
\end{itemize}

За тази задача са предоставени следните функции от журито:
\begin{lstlisting}
 int attempt(const std::vector<int>& Q)
 void answer(const std::vector<int>& S, const std::vector<int>& D)
\end{lstlisting}

Функцията \verb|attempt| получава като аргумент вектор с дължина $N$, съдържащ положението ($0$ или $1$) на всеки ключ и връща номера на първата затворена врата след задаване на тази комбинация и влизане в пещерата. Ако всички врати са отворени, функцията връща $N$. Функцията работи за $O(N)$ време.

Функцията \verb|answer| получава като аргумент два вектора \verb|S| и \verb|D| с дължина $N$. \verb|S| съдържа положението ($0$ или $1$) на всеки ключ. \verb|D| съдържа информация за това коя врата кой ключ отваря -- \verb|D[i]| е индексът на вратата, която се отваря при правилно зададен $i$-ти ключ.

Вашата програма \texttt{cave} трябва да имплементира функцията \texttt{explore}. Тя може да съдържа и друг код, и функции, необходими за работата Ви, но не трябва да съдържа главната функция \texttt{main}. Също така, не трябва да четете от стандартния вход или да отпечатвате на стандартния изход. Програмата Ви трябва да включва хедър файла \texttt{cave.h} чрез указание към предпроцесора:
\begin{lstlisting}
 #include "cave.h"
\end{lstlisting}

\subsection{Ограничения}
\begin{itemize}
\item $1 \leq N \leq 5~000$
\end{itemize}

\subsection{Подзадачи}
\begin{table}[H]
\begin{tblr}{|Q[c,m]|Q[c,m]|Q[c,m]|Q[c,m]|Q[c,m]|}
\hline
\textbf{№} & \textbf{Точки} & \textbf{Необходими подзадачи} & $N$ & \textbf{Други ограничения} \\
\hline
$0$ & $0$ & $-$ & $-$ & Примерът. \\
\hline
$1$ & $12$ & $-$ & $\leq 5~000$ & Ключ $i$ управлява врата $i$. \\
\hline
$2$ & $13$ & $-$ & $\leq 5~000$ & Винаги вярна комбинация: $[0,0,\dots,0]$. \\
\hline
$3$ & $21$ & $0$ & $\leq 100$ & \SetCell[r=3]{}{--} \\
\hline
$4$ & $30$ & $0,3$ & $\leq 2~000$ & \\
\hline
$5$ & $24$ & $0-4$ & $\leq 5~000$ & \\
\hline
\end{tblr}
\caption*{Точките за дадена подзадача се получават само ако се преминат успешно всички тестове, предвидени за нея.}
\end{table}
\FloatBarrier

\subsection{Примерна комуникация}
\begin{table}[H]
\begin{tblr}{|Q[c,m]|X[j,m]|}
\hline
\textbf{Извикване на функция} & \textbf{Обяснение} \\
\hline
\texttt{attempt([1, 0, 1, 1])} & Функцията връща $1$. Врата $0$ е отворена, врата $1$ е първата затворена. \\
\hline
\texttt{attempt([0, 1, 1, 0])} & Функцията връща $3$. Врати $0$, $1$, $2$ са отворени, врата $3$ е затворена. \\
\hline
\texttt{attempt([1, 1, 1, 0])} & Функцията връща $4$. Всички врати са отворени. \\
\hline
\texttt{answer([1, 1, 1, 0], [3, 1, 0, 2])} & Подаване на решението; програмата приключва. \\
\hline
\end{tblr}
\end{table}

\subsection{Локално тестване}
Може да използвате предоставения локален грейдър. Той очаква вход със следния формат:

\begin{itemize}
	\item ред $1$: \verb|N|
	\item ред $2$: Правилните положения на ключовете \verb|S[0]| до \verb|S[N-1]|
	\item ред $3$: Съответствията \verb|D[0]| до \verb|D[N-1]|
\end{itemize}

Примерната комуникация би била въведена по следния начин:
\begin{itemize}[label={}]
	\item \texttt{4}
	\item \texttt{1 1 1 0}
	\item \texttt{3 1 0 2}
\end{itemize}
\FloatBarrier

\end{document}
