% !TeX program=lualatex

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

Разглеждаме двоичен низ $s$ от $n$ бита -- $0$ или $1$. Допълнително, започваме с два празни низа $A$ и $B$. Прочитаме низа от ляво надясно и за поредния бит $s_i$ се извършва едно от три възможни действия:
\begin{enumerate}
	\item битът $s_i$ се долепя накрая на $A$;
	\item битът $s_i$ се долепя накрая на $B$;
	\item битът $s_i$ се игнорира.
\end{enumerate}

Независимо какво действие се изпълни, след бит $s_i$ се прочита бит $s_{i + 1}$ и се разглежда той, при условие че $i < n$. Когато преминем през всички символи на $s$, процесът приключва. Крайната цел е след края на процеса да е изпълнено, че $A=B$.

Низовете в тестовете са генерирани \textit{произволно} -- всеки бит може да бъде $0$ с $50\%$ вероятност. Решението Ви ще се оцени спрямо цел $g$ процента, което показва какъв най-малък процент от цифрите трябва да \textbf{не} игнорирате. Напишете програма \texttt{\textbf{stream}}, която намира подходяща поредица от действия.

\subsection{Вход}
От първия ред на стандартния вход се въвеждат $n$ и $g$. От следващия ред се въвежда самият низ $s$.

\subsection{Изход}
На първия ред на стандартния изход изведете едно число -- дължината на низовете $A$ и $B$. На втория ред на стандартния изход изведете във възходящ ред индексите на $s$, за които сте извършили действие от вид $1$. На третия ред на стандартния изход изведете във възходящ ред индексите на $s$, за които сте извършили действие от вид $2$.

\subsection{Ограничения}
\begin{itemize}
	\item $n \le 10^5$
\end{itemize}

\subsection{Подзадачи}
\begin{table}[H]
	\begin{tblr}{|Q[c,m]|Q[c,m]|Q[c,m]|Q[c,m]|}
		\hline
		\textbf{Подзадача} & \textbf{Точки} & $n$ & $g$ \\
        \hline
        	$1$ & $20$ & $=10^1$ & $80$\\ 
        \hline
        	$2$ & $20$ & $=10^2$ & $80$\\ 
		\hline
			$3$ & $20$ & $=10^3$ & $99$\\ 
		\hline
			$4$ & $20$ & $=10^4$ & $99$ \\ 
		\hline
			$5$ & $20$ & $=10^5$ & $99$ \\ 
		\hline
    \end{tblr}
	\caption*{Точките за дадена подзадача се получават само ако се преминат успешно всички тестове, предвидени за нея.}
\end{table}

\subsection{Оценяване}
Резултатът на подзадача е равен на минималната оценка на тест в нея, умножена по точките на подзадачата.

Ако низовете, които се получават при извършване на указаните действия, не са равни или числата, които сте извели не са във възходящ ред, ще получите \texttt{Wrong answer} и съответният тест ще има оценка $0$. В противен случай, ще получите следната оценка:

Нека $L$ е числото, което сте извели на първия ред на стандартния изход, и $C = \frac{2L}{n}$. Оценката на теста ще е $\min(\max(0, \frac{C \times 100}{g}), 1)$.

\textit{Журито има решение, което решава задачата за поне $98$ точки.}

\subsection{Пример}
\begin{table}[H]
	\begin{tblr}{|l|l|}
		\hline
		\textbf{Вход} & \textbf{Изход} \\
		\hline
		\texttt{\makecell[lt]{13 67\\0110101001011}} & 
		\texttt{\makecell[lt]{6\\5 6 8 9 10 12\\0 2 3 4 7 11}} \\
		\hline
	\end{tblr}
\end{table}

\end{document}
