%\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)
2013年5月23日 星期四
Xelatex, beamer for persentation of UVA 846 Steps
訂閱:
張貼留言 (Atom)
沒有留言:
張貼留言