\section{Задача H. <<Палиндромные числа>>}

\begin{frame}[t]{Задача H. <<Палиндромные числа>>}

  \begin{center}
    \LARGE Задача H. <<Палиндромные~числа>>
  \end{center}

  %$$\includegraphics[width=3cm]{pics/pnumbers.jpg}$$
  $$\includegraphics[width=6cm]{pics/palindrom.png}$$
\end{frame}

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

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

\begin{frame}[t]{Постановка задачи}
Определения:
\begin{itemize}
\item Число называется палиндромным, если читается одинаково
слева направо и справа налево.
\item Число $x$ называется межпалиндромным, если $x+1$ и $x-1$ --- 
палиндромные.
\end{itemize}
Задача:
\begin{itemize}
\item Найти количество межпалиндромных чисел в отрезке $[L,~R]$.
\end{itemize}
\end{frame}

\subsection{Решение}

\begin{frame}[t]{Решение: общие соображения}
\begin{itemize}
	\uncover<1->%
	{%
	\item Будем считать, что чисел не очень много. Найдем их все, после этого задача
	решается любым поиском, потому что таких чисел немного.
	}%
	\uncover<2->%
	{%
	\item Посмотрим на последнюю цифру межпалиндромного числа $x$. Если она не $0$ и не $9$, то ни при сложении,
	ни при вычитании никаких переносов не происходит. Тогда и у $x+1$ и $x-1$ последняя ненулевая
	цифра, совпадает с первой цифрой $x$. 
	}%
\end{itemize}
\end{frame}

\begin{frame}[t]{Решение: общие соображения}
\begin{itemize}
	\item Это бывает в двух случаях: либо $x$~--- однозначное, либо последняя цифра $1$.
	\item Однозначные сразу добавим в ответ. После этого можно считать, что число заканчивается
	на 0, 1 или 9.
\end{itemize}
\end{frame}

\begin{frame}[t]{Решение: числа, заканчивающиеся на 0}
\begin{itemize}
	\item Так как $x+1$ палиндромное, то первая цифра числа равна 1.
	\item Так как $x-1$ палиндромное, то первая цифра $x-1$ равна 9.
    \item Это возможно, только если все остальные цифры нули, то есть
          $x = 10^{k}$. Все такие числа подходят.
\end{itemize}
\end{frame}

\begin{frame}[t]{Решение: числа, заканчивающиеся на 1 или 9}
\begin{itemize}
	\uncover<1->%
	{%
    \item Пусть $x$ заканчивается на 1.
	\item Так как $x+1$ палиндромное, то первая цифра числа равна 2.
	}%
	\uncover<2->%
	{%
	\item Применяя по очереди условия на палиндромность $x-1$ и $x+1$,
	для каждой цифры можно доказать, что она равна или первой двойке,
	или последней единице, или одному из нулей, идущих сразу перед 1,
	если такие есть.
	}%
\end{itemize}
\end{frame}

\begin{frame}[t]{Решение: числа, заканчивающиеся на 1 или 9}
\begin{itemize}
	\uncover<1->%
	{%        
	\item Таким образом межпалиндромное число, заканчивающееся на 1,
	состоит из цифр 0,1,2.
	\item Аналогично, межпалиндромное число, заканчивающееся на 9,
	состоит из цифр 7,8,9.
	}%
\end{itemize}
\end{frame}

\begin{frame}[t]{Решение: перебор}
\begin{itemize}
    \item Переберём последние 9 цифр числа. Есть $3^{9} = 19683$ вариантов.
    \item Либо по $x+1$, либо по $x-1$ восстановим все число.
    \item Проверим что оно подошло. 
    \item Всего подходит 131 число. 
\end{itemize}
\end{frame}

%\begin{frame}[t]{Решение: явная конструкция}
%\begin{itemize}
%    \uncover<1->%
%    {
%    \item Всего есть не очень много различных конструкций межпалиндромных чисел.
%    }
%    \uncover<2->%
%    {
%    \item Числа вида $10^k$.
%    \item Однозначные числа.
%    }
%    \uncover<3->%
%    {
%    \item $\underbrace{2\underbrace{0...0}_{n}...2\underbrace{0...0}_{n}}_{m}1$
%    }
%    \uncover<4->%
%    {
%    \item $8\underbrace{\underbrace{9...9}_{n}7...\underbrace{9...9}_{n}7\underbrace{9...9}_{n}9}_{m}$
%    }
%    \uncover<5->%
%    {
%    \item При условии, что $m+1$ делит $n+1$.
%    \item Легко проверить, что все такие числа подходят. Отсутствие других доказывается аналогично тому,
%	что число состоит или из 0,1,2, или из 7,8,9.
%    }
%\end{itemize}
%\end{frame}
