\section{Задача C. <<Взлом шифра>>}

\begin{frame}[t]{Задача C. <<Взлом шифра>>}

  \begin{center}
    \LARGE Задача C. <<Взлом шифра>>
  \end{center}

  $$\includegraphics[width=4cm]{pics/cipher2.jpg}$$
\end{frame}

\begin{frame}[t]{}
  \vspace{3cm}
  \begin{itemize}
    \item Идея задачи --- Артём Васильев
    \item Подготовка тестов --- Артём Васильев
    \item Разбор задачи --- Виталик Аксёнов
  \end{itemize}
\end{frame}

\subsection{Постановка задачи}

\begin{frame}[t]{Постановка задачи}
Нужно выписать последовательность чисел от $1$ до $n$ длиной не больше $2n!$,
в которой будет встречаться любая перестановка чисел от $1$ до $n$, как подстрока.	
\end{frame}

\subsection{Решение}

\begin{frame}[t]{Генерация}
\begin{itemize}
	\uncover<1->%
	{%
	\item Сгенерируем все перестановки чисел от $2$ до $n$. \\
	}%
	\uncover<2->%
	{%
	\item Будем брать сгенерированные перестановки последовательно.
    \item Пусть взяли перестановку $p$. Добавим к ответу: $ans = ans + 1 + p + 1 + p$. \\
	}%
\end{itemize}
\end{frame}

\begin{frame}[t]{Объяснение}%
\begin{itemize}
    \uncover<1->{
    \item Пусть $s$~--- любая перестановка от $1$ до $n$.
    \item Пусть $t$~--- перестановка с 1 на первом месте, получившаяся с помощью циклического сдвига $s$.
    \item Тогда перестановка $s$ была добавлена на шаге добавления перестановки $t$ к ответу.   
    }
    \uncover<2->{
    \item Каждая добавленная перестановка $p$ добавила к длине ответа $2n$.
    \item Тогда длина ответа равна $2n \cdot (n-1)! = 2n!$.
    }
\end{itemize}
\end{frame}

