\documentclass[12pt]{article}
\input{structure.tex}
\renewcommand{\bottomtitlespace}{2cm}

\begin{document}

\renewcommand{\tl}{$7$ сек.}
\renewcommand{\ml}{$1024$ MB}
\problem{Задача AT23. ПЪТУВАНЕ ВЪВ ВРЕМЕТО}
\renewcommand{\header}{
	ТРЕНИРОВЪЧНО СЪСТЕЗАНИЕ\\
	НА РАЗШИРЕНИЯ НАЦИОНАЛЕН ОТБОР\\
	София, 27 юни 2026 г.\\
	Група A
}

\indent Сашка и Тестенчо са решили да се промъкнат в едно правителствено съоръжение, за да стигнат до скритата машина на времето и да поправят случилото се на IATI 2026. Достъпът до машината е заключен зад охранителна система. При опит за достъп до машината, на екрана се появява цяло число $q$ с $1 \leq q \leq N$, а операторът трябва да отговори с \emph{да} или \emph{не}, като при верен отговор достъпа се дава, а грешен отговор би включил алармата. Известно е, че показаното число $q$ винаги е или $x$ (чийто верен отговор е ``да''), или $y$ (чийто верен отговор е ``не''), при $x \neq y$.

За жалост, докато подготвят удара, двамата са забравили кои точно са $x$ и $y$. Затова Тестенчо отива сам пред машината, а Сашка остава по-далеч, за да пази. Точно когато въпросът светва, Сашка изведнъж си спомня и $x$, и $y$ -- но от разстояние може единствено да подвикне на Тестенчо едно цяло число $h$ ($h \geq 1$), в което трябва да предаде всичко необходимо, за да отговори Тестенчо вярно.

Напишете програма \textbf{\texttt{timetravel}}, която изпълнява и двете роли: по $N$, $x$ и $y$ да определи числото $h$, което Сашка подвиква, и по $N$, $q$ и $h$ -- отговора, който Тестенчо дава. При тестване решението се изпълнява като \textbf{два отделни процеса} без обща памет: в единия грейдърът извиква \texttt{encode} за всеки от $T$ случая, а в другия -- \texttt{answer} с върнатото за този случай $h$.

\subsection{Детайли по реализацията}
Трябва да предадете файла \texttt{timetravel.cpp}, който включва \texttt{timetravel.h} и реализира функциите \texttt{encode} и \texttt{answer}:

\begin{lstlisting}
int encode(int N, int x, int y)
\end{lstlisting}
където:
\begin{itemize}
	\item $N$ е броят възможни въпроси;
	\item $x$ и $y$ са две различни числа между $1$ и $N$;
	\item функцията връща числото $h$ ($h \geq 1$), което Сашка да извика.
\end{itemize}

\begin{lstlisting}
bool answer(int N, int q, int h)
\end{lstlisting}
където:
\begin{itemize}
	\item $N$ е броят възможни въпроси;
	\item $q$ е зададеният въпрос;
	\item $h$ е числото, подадено от функцията \texttt{encode};
	\item функцията връща отговора, който Е да избере: \texttt{true} за $q=x$ и \texttt{false} за $q=y$.
\end{itemize}

Двата процеса са напълно отделни: стойности, записани в глобални променливи от \texttt{encode}, не са достъпни за \texttt{answer}, и обратно.

\subsection{Ограничения}
\vspace{0.1em}
\begin{itemize}
	\item $N = 920$ ($N$ се подава във входа на функциите, но винаги е равно на $920$);
	\item $1 \leq T \leq 2\cdot10^6$.
\end{itemize}

\pagebreak
\subsection{Оценяване}
Задачата има две подзадачи -- нулевата се състои от примерния тест, първата се състои от единствен тест с всички $N\dot(N-1)$ двойки $(x,y)$, изброени по веднъж. Точките на решението се определят от най-голямото число $h$, което Сашка извиква за теста в първата подзадача:

\begin{table}[H]
	\begin{tblr}{|Q[c,m]|Q[c,m]|}
		\hline
		\textbf{Най-голямо} $h$ & \textbf{Точки}\\
		\hline
		$\geq 21$ & $0$ (отчита се като грешен изход) \\
		\hline
		$20$ & $27$ \\
		\hline
		$19$ & $30$ \\
		\hline
		$18$ & $33$ \\
		\hline
		$17$ & $37$ \\
		\hline
		$16$ & $42$ \\
		\hline
		$15$ & $50$ \\
		\hline
		$14$ & $60$ \\
		\hline
		$13$ & $75$ \\
		\hline
		$\leq 12$ & $100$ \\
		\hline
	\end{tblr}
	\caption*{Освен това всички отговори на функцията \texttt{answer} за всички тестове трябва да са верни; в противен случай решението получава $0$ точки. Ограниченията за време и памет важат за всеки от двата процеса поотделно.}
\end{table}
\FloatBarrier

\subsection{Локален грейдър}
Предоставени са ви хедър файлът \texttt{timetravel.h} и локален грейдър \texttt{grader.cpp}, които да компилирате заедно с програмата си. Локалният грейдър \textbf{не} използва отделни процеси, т.е. внимавайте да не споделяте глобална информация между \texttt{encode} и \texttt{answer}, без да искате -- това няма да работи на оценяващата система.

Формат на входа:
\begin{itemize}
	\item ред $1$: две цели числа $N\ T$ -- стойността $N$ и броят случаи;
	\item редове $2$ до $T + 1$: по три цели числа $x\ y\ q$ за съответния случай.
\end{itemize}

Формат на изхода:
\begin{itemize}
	\item ред $1$: \texttt{OK} и най-голямата получена стойност $h$ при верни отговори, или \texttt{ERR} и описание на грешката.
\end{itemize}

Форматът на примерите следва формата на локалния грейдър.

\pagebreak
\subsection{Примери}
\begin{table}[ht]
	\begin{tblr}{|l|l|l|}
		\hline
		\textbf{Тестов файл} & \textbf{Извиквания на \texttt{encode}} & \textbf{Извиквания на \texttt{answer}} \\
		\hline
		\texttt
		{\makecell[lt]{920 6\\1 2 1\\4 5 4\\1 2 2\\3 5 3\\4 5 5\\5 2 2}} & \texttt{\makecell[lt]{encode(920, 1, 2) = 12\\encode(920, 4, 5) = 2\\encode(920, 1, 2) = 12\\encode(920, 3, 5) = 4\\encode(920, 4, 5) = 2\\encode(920, 5, 2) = 1}} & \texttt{\makecell[lt]{answer(920, 1, 12) = true\\answer(920, 4, 2) = true\\answer(920, 2, 12) = false\\answer(920, 3, 4) = true\\answer(920, 5, 2) = false\\answer(920, 2, 1) = false}} \\
		\hline
	\end{tblr}
	\caption*{Много други стойности $h$ са валидни, но при показаните стойности на $h$ изведените отговори на \texttt{answer} са единствените верни. Най-голямото $h$ тук е $12$, което носи пълни точки.}
\end{table}

\FloatBarrier

\end{document}