% !TeX program=lualatex

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

\begin{document}
	
\renewcommand{\tl}{$5$ сек.}
\renewcommand{\ml}{$1024$ MB}
\problem{Задача GT24. КАЗИНО}
\renewcommand{\header}{
	ТРЕНИРОВЪЧНО СЪСТЕЗАНИЕ\\
	НА РАЗШИРЕНИЯ НАЦИОНАЛЕН ОТБОР\\
	София, 6 май 2026 г.\\
	Група G
}

Адзуро и Бордо, двойка, посещаваща казино в Италия, решиха да изиграят игра, предложена от крупието Киаро.

Играта представлява комуникация на низ, което Адзуро получава от Киаро, чрез двуизмерна таблица до Бордо. Таблицата представлява квадрат с $n \times n$ размерност, където редовет и колоните са индексирани от $0$ до $n-1$, а клетката на ред $r$ и колона $c$ е означена с $(r, c)$.

За да се подсигури канала на комуникация, Адзуро и Бордо са изолирани в две отделни стаи. Те ще изиграят следната игра $t$ на брой пъти. $i$-тата игра ще протече по следния начин:

\begin{itemize}
	\item Адзуро получава от Чиаро число $l_i$ и низ $s_i$. Низът $s_i$ е дълъг точно $l_i$ на брой символа и всеки от тях е или \texttt{A}, или \texttt{B}. Това е низът, който Адзуро иска да предаде на Бордо. За да извършат комуникацията обаче, Адзуро получава число $n$ и таблица с размери $n \times n$, в началото запълнена с нули. На Адзуро е позволено да презапише някои от позициите тази таблица с единици и да я върне на Чиаро.
	\item Чиаро получава таблицата, попълнена от Адзуро. Преди да я предаде на Бордо, той си избира път от клетка $(0, 0)$ до $(n - 1, n - 1)$, в който всеки следващ ход е надолу или надясно от предходния. За всяка клетка през която този път минава, Чиаро сменя символа записан в нея -- нулите става единици и обратно, единиците стават нули.
	\item Бордо получава таблицата след като тя е била модифицирана от Чиаро, както и същото число $l_i$, което Чиаро е дал на Адзуро в първата стъпка от играта. С тази информация Бордо трябва да възстанови низът, който Адзуро е опитал да му предаде.
\end{itemize}

Преди да започнат играта, Адзуро и Бордо са наясно с намеренията на Чиаро да опропасти тяхната игра. Те могат да създадат стратегия, която да изпълняват и да дешифрират правилно низа, дори след като Чиаро промени таблицата на Адзуро по описания начин.

Напишете програма \textbf{\texttt{casino.cpp}}, която да имплементира две функции, симулиращи печелившите стратегии на Адзуро и Бордо.

\subsection{Детайли по имплементацията}
Трябва да имплементирате две функции:

Първата функция ще симулира действията на Адзуро.
\begin{lstlisting}
std::vector<std::vector<int>> Azzurro(int n, int l, std::string s)
\end{lstlisting}

Тази функция ще бъде извикана $t$ на брой пъти -- по веднъж за всяка игра. $i$-тото извикване на функцията ще получи като параметри $n$ -- размерът на таблицата, с която Адзуро ще работи, $l$ -- дължината на низа, който Адзуро изпраща до Бордо и $s$ -- самия низ.

Като резултат от изпълнението си, функцията трябва да върне двумерна таблица с размери $n \times n$, за която е вярно, че всички нейни елементи са или $0$ или $1$.

Ако размерът на таблицата, върната от тази функция, не е $n \times n$ или някой от елементите, записани в нея не е $0$ или $1$, съответния тест ще бъде означен като грешен и ще получите грешка \textbf{\texttt{Wrong Answer [1]}}.

\pagebreak

Втората функция ще симулира действията на Бордо.
\begin{lstlisting}
std::string Bordeaux(int n, int l, std::vector<std::vector<int>> T)
\end{lstlisting}

Тази функция ще бъде извикана $t$ на брой пъти -- по веднъж за всяка игра. $i$-тото извикване на функцията ще получи като параметри $n$ -- размерът на таблицата, която Адзуро е предал и Чиаро е донесъл на Бордо, $l$ -- дължината на низа, която Бордо трябва да дешифрира от таблицата и $T$ -- съдържанието на таблицата, предадена от Адзуро, след като Чиаро я е модифицирал.

Като резултат от изпълнението си, функцията трябва да върне низ с дължина $l$, съдържащ единствено буквите \texttt{A} или \texttt{B}.

Ако дължината на низа не е правилна или низа съдържа символ, различен от \texttt{A} и \texttt{B}, съответния тест ще бъде означен като грешен и ще получите грешка \textbf{\texttt{Wrong Answer [2]}}.

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


\subsection{Ограничения}
\begin{itemize}
	\item $1 \le t \le 30~000$
	\item $n=8$
	\item $1 \le l_i \le 51$ за всяко $i = 1, 2, \dots t$
	\item Низът $s$ съдържа единствено символите \texttt{A} и \texttt{B} 
\end{itemize}

\subsection{Оценяване}
Ако решението ви е получило \textbf{\texttt{Wrong answer [1]}} или \textbf{\texttt{Wrong answer [2]}}, превишило е лимита по памет или време или е получило грешка по време на изпълнение, в който и да е тест, ще получите $0$ точки.

В противен случай, резултатът Ви се изчислява по следния алгоритъм:
\begin{itemize}
	\item За всеки тест се определя стойност $l^*$, такава че за всички игри в теста, за които дължината на низа $l$ е била по-малка или равна на $l^*$, Вашата стратегия за Адзуро и Бордо успешно е дешифрирала низа. В случай, че сте изиграли всички игри в теста успешно, полагаме $l^* = 51$.
	\item От изчислените стойности на $l^*$ за всички тестове се взима минималната и тя се обозначава като $l_{\min}$.
	\item Оценката на решението ви се изчислява по следната таблица:
	\renewcommand{\arraystretch}{1.2}
	\begin{table}[h!]
		\centering
		\begin{tabular}{|c|c|}
			\hline
			\textbf{Условие} & \textbf{Точки} \\
			\hline
			$1 \le l_{\min} \le 28$ & $2 \times l_{\min}$ \\
			\hline
			$29 \le l_{\min} \le 39$ & $l_{\min} + 28$ \\
			\hline
			$40 \le l_{\min} \le 50$ & $67 + 3 (l_{\min} - 40)$ \\
			\hline
			$l_{\min} = 51$ & $100$ \\
			\hline
		\end{tabular}
	\end{table}
\end{itemize}

\subsection{Локално тестване}

Предоставени са Ви файловете \texttt{Lgrader.cpp} и \texttt{casino.h}, които можете да компилирате заедно с Вашата програма, за да я тествате на работния Ви компютър. Забележете, че в локалния грейдър функциите на Адзуро и Бордо се извикват от един и същ процес. Това се различава от грейдъра на системата.

\subsection{Формат на локалния грейдър}
Формат на входа:
\begin{itemize}
	\item $t\ n$
	\item $l_1$
	\item $s_1$
	\item $r_1$
	\item \dots
	\item $l_t$
	\item $s_t$
	\item $r_t$
\end{itemize}

Тук $l_i$ е дължината на низа, върху който се играе $i$-тата игра, $s_i$ е самият низ, а $r_i$ е описание на движенията на пътеката, по която Чиаро ще смени стойностите в таблицата -- с \texttt{R} се означава движение надясно, а с \texttt{D} се означава движение надолу.

Формат на изхода:
\begin{itemize}
	\item $\mathtt{ans}_1$
	\item \dots
	\item $\mathtt{ans}_n$
\end{itemize}

Тук $\mathtt{ans}_i$ е низът, който Бордо ще разпознае при $i$-тата игра.

\subsection{Примерна комуникация}
\begin{table}[h]
	\centering
	\renewcommand{\arraystretch}{1.5} % Увеличава разстоянието между редовете за по-добра четимост
	\begin{tabular}{|l|l|l|}
		\hline
		\multirow{2}{*}{Примерен вход} & \multicolumn{2}{l|}{Примерни извиквавания на функция} \\ \cline{2-3} 
		& Извикване на функция & Върната стойност \\ \hline
		\texttt{2 2}                            & \texttt{Azzurro(2, 1, "B")} &  \\ \cline{2-3} 
		\texttt{1  }                            &  & \texttt{[[1, 0], [0, 1]]} \\ \cline{2-3} 
		\texttt{B  }                            & \texttt{Bordeaux(2, 1, [[0, 1], [0, 0]])} &  \\ \cline{2-3} 
		\texttt{RD }                            &  & \texttt{"B"} \\ \cline{2-3} 
		\texttt{3  }                            & \texttt{Azzurro(2, 3, "ABB")} &  \\ \cline{2-3} 
		\texttt{ABB}                            &  & \texttt{[[0, 0], [0, 0]]} \\ \cline{2-3} 
		\texttt{DR }                            & \texttt{Bordeaux(2, 3, [[1, 0], [1, 1]])} &  \\ \cline{2-3} 
		&  & \texttt{"ABB"} \\ \hline
	\end{tabular}
\end{table}
Предоставен Ви е файл \texttt{sample-01-in.txt}, който съдържа входа от примерната комуникация. Забележете, че този вход не отговаря на ограниченията на задачата, защото $n \neq 8$. Допълнително Ви е предоставен файл \texttt{sample-02-in.txt}, който отговаря на ограниченията на задачата.

\end{document}
