網頁

2013年5月23日 星期四

Xelatex, beamer for persentation of UVA 846 Steps

%\documentclass{beamer}
%\documentclass[slidestop,compress,mathserif]{beamer}
\documentclass[slidestop,compress,mathserif,xcolor=dvipsnames]{beamer}
\usetheme{Berlin}
\usecolortheme{seahorse}
%\usecolortheme[named=black]{structure}
\setbeamercolor{section in head/foot}{fg=white,bg=gray!20!black}
\setbeamertemplate{items}[ball]
%\setbeamertemplate{blocks}[rounded][shadow=true] 
\setbeamertemplate{navigation symbols}{}
%\setbeamertemplate{headline}{} %<= to suppress the headline otherwise section and subsection will be displayed in the navigation bar
\setbeamertemplate{footline}{}
%\beamersetuncovermixins{\opaqueness<1>{25}}{\opaqueness<2->{15}} 
\let\Tiny=\tiny
\usepackage{fontspec}
   \setmainfont{WenQuanYi Micro Hei}
    \setsansfont{WenQuanYi Micro Hei Mono}
    \setmonofont{WenQuanYi Micro Hei Mono}
    \XeTeXlinebreaklocale "zh"
    \XeTeXlinebreakskip = 0pt plus 1pt
\begin{document}
\setbeamerfont{subsection in sidebar}{size=\tiny}
\setbeamerfont{title in sidebar}{size=\tiny}

\title{\fontsize{28}{35}\selectfont UVA 846\\ \fontsize{14pt}{20pt}\selectfont Steps}
%\author{Author Name}
\institute{}

\frame{\titlepage}

\section*{題意}
\begin{frame}
  \frametitle{題意}
  \uncover<1-> {給你兩個點X、Y\\}
  \uncover<2-> {從X走到Y \\}
  \uncover<3-> {利用下列走法規則 \\}
  \begin{itemize}
        \uncover<4-> {\item 第一步和最後一步的距離一定是1\\}
        \uncover<5-> {\item 下一步走的距離與上一步走的距離相同\\}
        \uncover<6-> {\item 下一步走的距離與上一步走的距離多或少1單位\\}
  \end{itemize}
  \uncover<7-> {找出從X走到Y的最小步數即可\\}
\end{frame}

\section*{Input and Output}
\begin{frame}
  \frametitle{Input and Output}
    Input \\
    3     //The number of test cases \\
    45 48 // 1 1 1 \\
    45 49 // 1 2 1 \\
    45 50 // 1 2 1 1 \\
    Output \\
    3       \\
    3       \\
    4       \\
\end{frame}

\section{思考路線}
\subsection{}
\begin{frame}
  \frametitle{怎樣才可以做到最少步數?}
  \begin{itemize}
    \uncover<1->{\item{一次能走越大的距離越好}}
    \uncover<2->{\item{單邊一直加1?}}
    \uncover<3->{\item{左右邊一直加1?}}
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{$n^2$ trick}
  1 + $\cdots$ + n-1 + n + n-1 + $\cdots$ + 1 = n$^{2}$
\end{frame}

\section{解題方法}
\subsection{}
\begin{frame}
  \frametitle{演算法}
  \uncover<1->{d = X-Y  // d 表示X到Y的距離 \\}
  \uncover<2->{n = $\lfloor\sqrt{d}\rfloor$  // n 表示取$\sqrt{d}$的整數部份\\ }
  \vspace{\baselineskip}
  \uncover<3->{if d == n$^2$ \\ \qquad return 2n-1 \\ \vspace{\baselineskip}}
  \uncover<4->{if 0 < d-n$^2$ <= n \\  \qquad return 2n \\ \vspace{\baselineskip}}
    \uncover<5->{if n < d-n$^2$ < 2n+1 \\ \qquad return 2n+1  \\ \vspace{\baselineskip}}
\end{frame}

\begin{frame}
  \frametitle{說明}
    \uncover<1->{第一種情況,當 d == n$^2$ \\
                 \qquad 最短的步數走法必然是1+$\cdots$+(n-1)+n+(n-1)+$\cdots$+1\\
                 \qquad $\therefore$ 最短步數為 2n-1 步\\
                 \vspace{\baselineskip}}
  \uncover<2->{第二種情況,當 d-n$^2$ <= n  \\
               \qquad 先利用第一種情況的解法,走n$^2$單位\\
               \qquad 剩下還有一個小於等於n的值,插入可放置的位置即可\\
               \qquad $\therefore$ 最短步數為 2n 步\\
               \vspace{\baselineskip}}
  \uncover<3->{第三種情況,n < d-n$^2$ < 2n+1 \\
               \qquad 先利用第一種情況的解法,走n$^2$單位,再插入n\\
               \qquad 最後在插入小於等於n的值\\
               \qquad $\therefore$ 最短步數為 2n+1 步\\}
\end{frame}
\subsection{}
\begin{frame}
  \frametitle{小證明}
  \uncover<1->{proof: d-n$^2$ < 2n+1\\}
  \uncover<2->{\qquad    \qquad $0  < n < \sqrt{d} < n+1$\\}
  \uncover<3->{\qquad    \qquad $n^2 < d < n^2+2n+1$ \\ }
    \uncover<4->{\qquad  \qquad $0 < d-n^2 < 2n+1$ \\}
\end{frame}
\end{document}

PDF:UVA 846 Steps(Result)

沒有留言:

張貼留言