\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}{$0.3$ сек.}
\renewcommand{\ml}{$256$ MB}
\problem{Задача OJ10. ИГРА С ПЛОЧКИ}
\addauthor{Илиян Йорданов (заета)}{2026}{08}{29}
\renewcommand{\header}{
	НАЦИОНАЛНА ШКОЛА ПО ИНФОРМАТИКА\\
	ОТБОРНО СЪСТЕЗАНИЕ\\
	Габрово, 29 август 2026 г.\\
	6 – 7 клас
}

Иван и Илиян играят игра на таблица от $2N \times 2M$ единични квадратни клетки. Редовете са номерирани от $0$ до $2N-1$ от горе надолу, а колоните -- от $0$ до $2M-1$ от ляво надясно. За $0 \le i < 2N$ и $0 \le j < 2M$ клетката в ред $i$ и колона $j$ ще бележим с $(i, j)$.

Иван дава на Илиян $N \cdot M$ \textbf{блокчета}, едно по едно. Всяко блокче е квадрат $2 \times 2$ от четири $1 \times 1$ \textbf{плочки}. Иван е оцветил всяка плочка от блокчето в черно или бяло, като гарантира, че \textbf{поне една плочка от блокчето е бяла}.

Илиян трябва да постави всяко блокче върху таблицата \textbf{веднага след получаването му}, без да знае какви блокчета ще получи по-късно. Блокчетата не могат да бъдат завъртани. Всяко блокче трябва да бъде поставено изцяло в таблицата, покривайки точно четири клетки от нея. Освен това, горната лява плочка на всяко блокче трябва да покрива клетка, чиито ред и колона са четни числа. Всяка клетка от таблицата може да бъде покрита от най-много едно блокче.

Иван печели играта, ако след поставянето на някое блокче съществува квадрат $2 \times 2$, покрит с четири черни плочки. Формално, ако клетките $(a, b)$, $(a+1, b)$, $(a, b+1)$, $(a+1, b+1)$ са покрити с черни плочки за някои $0 \le a < 2N-1$ и $0 \le b < 2M-1$, тогава Иван печели. Индексите $a$ и $b$ не е необходимо да са четни.

Илиян печели, ако постави всичките $N \cdot M$ блокчета, без Иван да спечели. Обърнете внимание, че поставянето на $N \cdot M$ блокчета ще покрие изцяло таблицата.

Вашата задача е да напишете програма \textbf{\texttt{tiling}}, която имплементира стратегия за Илиян, така че да спечели играта. Може да се докаже, че при дадените ограничения Илиян винаги може да разположи блокчетата така, че да си гарантира победа, независимо от оцветяването на блокчетата, които получава по-късно.

\subsection{Детайли по реализацията}
Тази задача е от специален вид -- интерактивна задача (не може да прочетете целия вход наведнъж). Затова всъщност вашата програма (в ролята на Илиян) ще комуникира с програма на журито (в ролята на Иван). Комуникацията се извършва задължително в следните стъпки:

\begin{enumerate}
	\item От стандартния вход въвеждате целите числа $N$ и $M$ -- половината от броя редове и колони на таблицата.
	\item След това започвате да получавате блокчета от Иван.
	\item За да научите цветовете на плочките на текущото блокче, трябва да въведете четири цели числа $TL \ TR \ BL \ BR$ -- цветовете, съответно на горния ляв, горния десен, долния ляв и долния десен ъгъл на текущото блокче, както е показано на картинката по-долу. Всяка стойност е или $0$ (бяло), или $1$ (черно).
	\item За да поставите блокчето, трябва да отпечатате на стандартния изход две цели числа $i \ j$, които задават позицията $(i, j)$ на горния ляв ъгъл на поставеното блокче. Както $i$, така и $j$ трябва да бъдат четни числа, а квадрата $2 \times 2$, покрит от блокчето, не трябва да се припокрива с никое от преди това поставените блокчета.
	\item Ако таблицата не е запълнена (не са поставени всички $N \cdot M$ блокчета), то отново изпълнявате 3.
\end{enumerate}

\begin{center}
	\includegraphics[width=0.1\textwidth]{img/quadrant-labels.png}
\end{center}

\textbf{Задължително след всяко отпечатване на стандартния изход трябва да отпечатвате:} \begin{lstlisting}
 cout << endl ;
\end{lstlisting}

Всяко неспазване на изискванията в тази секция ще доведе до грешен резултат на съответния тест!

\subsection{Ограничения}
\vspace{0.1em}
\begin{itemize}
	\item $1 \le N, M \le 100$
	\item $0 \le S \le 3$ за всяко блокче, където $S = TL + TR + BL + BR$ е броят на черните му плочки.
\end{itemize}

\subsection{Подзадачи}
\begin{table}[H]
	\begin{tblr}{|Q[c,m]|Q[c,m]|Q[c,m]|X[c,m]|}
		\hline
		\textbf{Подзадача} & \textbf{Точки} & \textbf{Необходими подзадачи} & \textbf{Допълнителни ограничения}\\
		\hline
		$0$ & $0$ & $-$ & Примерният тест. \\
		\hline
		$1$ & $6$ & $-$ & $S=1$ за всяко блокче и $N=2$. \\
		\hline
		$2$ & $16$ & $-$ & $S=3$ за всяко блокче. $N=M$, $N$ е четно число и всяко от четирите възможни оцветявания на блокчета се появява точно $\frac{N^2}{4}$ пъти. \\
		\hline
		$3$ & $10$ & $1$ & $S=1$ за всяко блокче. \\
		\hline
		$4$ & $29$ & $1, 3$ & $S \le 2$ за всяко блокче. \\
		\hline
		$5$ & $39$ & $0-4$ & -- \\
		\hline
	\end{tblr}
	\caption*{Точките за дадена подзадача се получават само ако се преминат успешно всички тестове, предвидени за нея и необходимите подзадачи.}
\end{table}
\FloatBarrier

\subsection{Примерна комуникация}
Да разгледаме игра с $N=1$ и $M=2$, така че таблицата има $2$ реда и $4$ колони. Първоначално всички клетки са празни и таблицата изглежда по следния начин:
\begin{center}
	\includegraphics[width=0.3\textwidth]{img/example-initial.png}
\end{center}

Има $N \cdot M = 2$ блокчета за поставяне.

\begin{table}[H]
	\begin{tblr}{|Q[c,m]|Q[c,m]|X[j,m]|}
		\hline
		\textbf{Вход на програмата} & \textbf{Изход на програмата} & \textbf{Обяснение} \\
		\hline
		\texttt{1 2} & & Прочитате стойностите на $N$ и $M$. \\
		\hline
		\texttt{1 0 1 1} & & Научавате, че първото блокче на Иван е с три черни плочки и бяла плочка в горния десен ъгъл. \\
		\hline
		& \texttt{0 0} & {Илиян решава да постави това блокче от лявата страна на таблицата, така че програмата ви извежда \texttt{0 0}.\\
		Това е изобразено на първата картинка по-долу.} \\
		\hline
		\texttt{0 1 1 1} & & {Научавате, че следващото блокче на Иван е с три черни плочки и бяла плочка в горния ляв ъгъл.\\
		Забележете, че можете да прочетете тези входни данни само след като сте отпечатали къде ще поставите предходното блокче.} \\
		\hline
		& \texttt{0 2} & {Програмата ви извежда \texttt{0 2}, понеже това е единствената останала клетка с четен ред и четна колона, която може да бъде горен ляв ъгъл на блокче $2 \times 2$.\\
		Това е изобразено на втората картинка по-долу.} \\
		\hline
	\end{tblr}
\end{table}

\begin{center}
	\includegraphics[width=0.3\textwidth]{img/example-step1.png}
\end{center}

\begin{center}
	\includegraphics[width=0.3\textwidth]{img/example-final.png}
\end{center}

Никой квадрат $2 \times 2$ не е изцяло покрит с черни плочки, така че Илиян е поставил успешно
всички блокчета, без Иван да спечели. Илиян печели играта.

\end{document}
