% !TeX program=lualatex

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

\begin{document}
	
\renewcommand{\tl}{$0.2$ сек.}
\renewcommand{\ml}{$256$ MB}
\problem{Задача CT3. УВЕСЕЛИТЕЛНО ВЛАКЧЕ}
\renewcommand{\header}{
	ТРЕНИРОВКА\\
	Група C – 7, 8 клас
}

Мария наскоро започна първата си работа като контрольор на светлините в един увеселителен парк.

Тя ще управлява светлините на влакче на ужасите, което преминава през $n$ стаи подредени в редица от $0$ до $(n-1)$-ва стая. За да променя светлините, Мария има налични $n$ ключа, също номерирани от $0$ до $n-1$. Поради нескопосаната работа на инженерния отдел обаче не е ясно кой ключ светлината в коя стая управлява.

Маркетинговият отдел на увеселителния парк са решили, че влакчето ще създаде най-голяма сензация, ако единствените стаи, в които осветлението е пуснато са $0$ и $n-1$. Мария обаче все още е нова на работата и не знае кои ключове да активира, за да изпълни тази поръчка.

За да опознае системата, с която работи Мария ще извърши следния тип експерименти с посетителите на влакчето: първо ще изключи осветлението във всички стаи и ще включи някакво подмножество от ключовете. След това ще се пусне следващата група хора. Те ще крещят от вълнение всеки път, когато преминат от осветена стая в неосветена такава или обратно -- от неосветена в осветена. Понеже всичко се случва твърде бързо, накрая на експеримента Мария ще знае единствено броя писъци, които е чула.

За да не се усъмнят от маркетинговия отдел, Мария трябва да открие бързо кои ключове управляват осветлението в стаи $0$ и $n-1$. Тя ще си позволи да проведе не повече от $30$ експеримента.

Напишете програма \textbf{\texttt{train.cpp}}, която помага на Мария да определи какви експерименти трябва да проведе, за да извлече нужната информация.

\subsection{Детайли по имплементацията}

Вие трябва да импелементирате функция със следния прототип:
\begin{lstlisting}
std::vector<int> find_switches(int n);
\end{lstlisting}

\begin{itemize}
	\item Функцията се извиква веднъж на тест;
	\item Функцията получава като аргумент броя стаи, през които ще премине увеселителното влакче;
	\item Функцията връща вектор с два елемента, съответно индексите на ключовете, управляващи светлината в $0$-та и $(n-1)$-та стая, в произволен ред;
	\item Ако функцията върне вектор с дължина различна от $2$ или елементите във вектора не сочат към правилните ключове, съответният тест ще бъде оценен с \texttt{Wrong answer}.
\end{itemize}

Функцията \texttt{findSwitches()} може да извиква следната функция:
\begin{lstlisting}
int experiment(std::string switches);
\end{lstlisting}

\begin{itemize}
	\item Може да извикате функцията най-много $30$ пъти, в противен случай съответният тест ще бъде оценен \texttt{Wrong answer};
	\item Функцията трябва да получава като аргумент низ с дължина $n$, състоящ се от символите $0$ и $1$, така че ако Мария иска да включи осветлението в $i$-тата стая, трябва $i$-тия символ в низа да е $1$, в противен случай да е $0$;
	\item Ако функцията получи низ с дължина различна от $n$ или получи низ, който съдържа символи различни от $0$ и $1$, съответния тест ще бъде оценен с \texttt{Wrong answer};
	\item Функцията връща броя писъци, които са били чути по време на експеримента.
\end{itemize}


Трябва да предадете към системата файл \texttt{train.cpp}, който съдържа функцията \texttt{find\_switches()}. Той може да съдържа и друг код и функции, необходими за работата на програмата Ви, но не трябва да съдържа главната функция \texttt{main()}. В началото си Вашият файл трябва да съдържа указание към предпроцесора:

\begin{lstlisting}
#include "train.h"
\end{lstlisting}


\subsection{Ограничения}
\begin{itemize}
	\item $3 \le n \le 30~000$
	\item Имате право на най-много $30$ извиквания на функцията \texttt{experiment}.
\end{itemize}

\subsection{Подзадачи}
\begin{table}[H]
	\begin{tblr}{|Q[c,m]|Q[c,m]|Q[c,m]|}
		\hline
		\textbf{Подзадача} & \textbf{Точки} & \textbf{Други ограничения} \\
        \hline
        	$0$ & $ 0$ & Примерните тестове.\\ 
        \hline
        	$1$ & $ 9$ & $n = 3$\\ 
		\hline
			$2$ & $15$ & $n \le 30$\\ 
		\hline
			$3$ & $17$ & Ключ $0$ отговаря за стая $0$.\\ 
		\hline
			$4$ & $16$ & \makecell{$n$ е четно и ключът за една от стаите с индекс $0$ или $n-1$\\ е в първата половита ($<\frac{n}{2}$), а другият е във втората половина ($\ge\frac{n}{2}$).}\\ 
		\hline
			$5$ & $14$ & $n \le 1000$ \\ 
		\hline
			$6$ & $29$ & Няма.\\ 
		\hline
    \end{tblr}
	\caption*{Точките за дадена подзадача се получават само ако се преминат успешно всички тестове, предвидени за нея.}
\end{table}

\subsection{Пример 1}
\begin{table}[H]
	\begin{tblr}{|Q[l]|Q[l]|}
		\hline
		\textbf{Жури} & \textbf{Мария} \\
		\hline
		\texttt{findSwitches(5)} &  \\
		\hline 
		 &  \texttt{experiment("10001")} \\
		\hline
		\texttt{return 3;} &  \\
		\hline 
		&  \texttt{experiment("10110")} \\
		\hline
		\texttt{return 3;} &  \\
		\hline 
		&  \texttt{return {2, 4};} \\
		\hline
	\end{tblr}
\end{table}

\subsection{Пример 3}
\begin{table}[H]
	\begin{tblr}{|Q[l]|Q[l]|}
		\hline
		\textbf{Жури} & \textbf{Мария} \\
		\hline
		\texttt{findSwitches(4)} &  \\
		\hline 
		&  \texttt{experiment("1010")} \\
		\hline
		\texttt{return 3;} &  \\
		\hline
		&  \texttt{return {0, 3};} \\
		\hline
	\end{tblr}
\end{table}

\newpage
\subsection{Пример 2}
\begin{table}[H]
	\begin{tblr}{|Q[l]|Q[l]|}
		\hline
		\textbf{Жури} & \textbf{Мария} \\
		\hline
		\texttt{findSwitches(3)} &  \\
		\hline 
		&  \texttt{experiment("111")} \\
		\hline
		\texttt{return 0;} &  \\
		\hline 
		&  \texttt{experiment("110")} \\
		\hline
		\texttt{return 2;} &  \\
		\hline 
		&  \texttt{experiment("000")} \\
		\hline
		\texttt{return 0;} &  \\
		\hline
		& \texttt{return {1, 0};} \\
		\hline
	\end{tblr}
\end{table}

\subsection{Обяснение на примерите}
В първия примерен тест следния масив описва кой ключ коя стая осветява: $[2, 1, 0, 3, 4]$. Това удовлетворява ограниченията на подзадачи $2, 5$ и $6$. Първият експеримент включва ключове $0$ и $4$, които включват осветлението в стаи $2$ и $4$ съответно (вижте илюстрацията по-долу). Така Мария ще чуе $3$ писъка -- когато увесилителното влакче преминава от стая $1$ в стая $2$, после отново от стая $2$ в стая $3$ и за последен път от стая $3$ в $4$. Забележете, че накрая програмата връща $\{2, 4\}$, но също за коректен отговор би се приело $\{4, 2\}$.

Вторият примерен тест отговаря на ограниченията на подзадачи $1, 2, 5$ и $6$.

\begin{center}
	\includegraphics[scale=0.5]{example.png}
\end{center}

\subsection{Локално тестване}
В системата ви е предоставен грейдър за локално тестване -- той чете броя на стаите и за всеки ключ лампата в коя стая контролира. Накрая извежда редица от числата, които Вашата програма е върнала като отговор. 

\end{document}
