\documentclass[12pt]{article}
\input{structure.tex}

\begin{document}

\renewcommand{\tl}{$7$ сек.}
\renewcommand{\ml}{$256$ MB}
\problem{Анализ. ПЪТУВАНЕ ВЪВ ВРЕМЕТО}
\renewcommand{\header}{
	ЛАГЕР ШКОЛА ЗА\\
	ПОДГОТОВКА НА РАЗШИРЕНИТЕ ОТБОРИ\\
	София, 27 юни 2026 г.\\
	Анализ на задачите
}
~\\

Сашка знае двойката $(x, y)$ и трябва да предаде на Звезденчо едно число $h$, така че Звезденчо, виждайки само въпроса $q \in \{x, y\}$ и числото $h$, да отговори вярно („да“ при $q = x$, „не“ при $q = y$). Резултатът зависи от \emph{най-голямото} извикано $h$, затова целта е то да е възможно най-малко.

\section*{Кодови думи като множества}
Съпоставяме на всяко число $1, \dots, N$ различна \emph{кодова дума} -- подмножество на $\{1, \dots, K\}$ (записано като $K$-битово число). Стратегията на Звезденчо при число $h$ е проста:
\begin{center}
	\emph{отговаря „да“ точно когато бит $h$ на кодовата дума на $q$ е $1$.}
\end{center}
За да е верен отговорът и при $q=x$, и при $q=y$, Сашка трябва да избере позиция $h$, на която кодът на $x$ има $1$, а кодът на $y$ има $0$:
\[
	h \in \mathrm{code}(x) \setminus \mathrm{code}(y).
\]
Такава позиция съществува за всяка двойка тогава и само тогава, когато никоя кодова дума не е подмножество на друга -- т.е.\ кодовете образуват \textbf{антиверига}.

\section*{Минимизиране на $K$}
Най-голямата антиверига от подмножества на $\{1,\dots,K\}$ (теорема на Спернер) се състои от всички подмножества с размер $\lfloor K/2 \rfloor$ и има $\binom{K}{\lfloor K/2\rfloor}$ елемента. Затова взимаме всички кодови думи с \emph{еднакъв} брой единици -- тогава са две по две несравними и за всяка двойка $h \in \mathrm{code}(x)\setminus \mathrm{code}(y)$ съществува.

Търсим най-малкото $K$ с $\binom{K}{\lfloor K/2\rfloor} \geq N$. За $N \leq 920$ имаме $\binom{12}{6} = 924 \geq 920$, така че $K = 12$ стига: даваме на числата различни $12$-битови думи с точно шест единици. Тогава винаги $h \leq 12$ -- пълен резултат.

\section*{Реализация}
\texttt{encode}$(N,x,y)$ намира най-ниската позиция, на която $\mathrm{code}(x)$ има $1$, а $\mathrm{code}(y)$ -- $0$ (т.е.\ $\mathrm{code}(x)\ \&\ {\sim}\mathrm{code}(y)$), и връща нейния индекс $+1$. \texttt{answer}$(N,q,h)$ връща бит $h$ на $\mathrm{code}(q)$.

\section*{Частични решения}
По-наивно кодиране (например с различаващ бит без условие за еднакъв брой единици) дава по-голямо $K$, а оттам и по-голямо максимално $h$. Избор на $K = 13$ (думи с шест или седем единици) дава $h \leq 13$ и около $75\%$; обикновено двоично различаване дава още по-голямо $h$ и съответно по-нисък резултат. Точките се определят от таблицата „максимално $h$ $\to$ точки“ от условието.

\end{document}
