sprout-exam1-statement.tex

\documentclass[11pt,a4paper]{article}

\usepackage{indentfirst}
\usepackage{amssymb}
\usepackage{subcaption}
\usepackage{graphicx}
\usepackage{longtable}
\usepackage{fancyhdr}
\usepackage{xeCJK}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{ulem}
\usepackage{xcolor}
\usepackage{fancyvrb}
\usepackage{listings}
\usepackage{soul}
\usepackage{hyperref}
    \lstdefinestyle{C}{
        language=C,
        basicstyle=\ttfamily\bfseries,
        numbers=left,
        numbersep=5pt,
        tabsize=4,
        frame=single,
        commentstyle=\itshape\color{brown},
        keywordstyle=\bfseries\color{blue},
        deletekeywords={define},
        morekeywords={NULL,bool}
    }

\setCJKmainfont{Noto Sans Mono CJK TC}

\voffset -20pt
\textwidth 410pt
\textheight 650pt
\oddsidemargin 20pt
\newcommand{\XOR}{\otimes}
\linespread{1.2}\selectfont

\pagestyle{fancy}
\lhead{2024 算法班第一階段要認真考}

\begin{document}

\begin{center}
\section*{A. 喵喵抓老鼠-Extreme}
\end{center}

\section*{Description}

"喵喵喵喵喵！"

"吱吱吱吱吱！"

家裡的老鼠又在肆虐了，喵喵一個人抓覺得太累，所以他呼叫了其他的貓一起來抓老鼠，已知每隻貓加入地圖的時間點和位置，你可以幫助喵喵找出最近的老鼠有多遠嗎？

\section*{Input}
輸入檔的開頭會有兩個正整數 $n,m$，表示這組資料有幾行，每行有多少個字元。
接下來 $n$ 行字會表示一個迷宮，每行有 $m$ 個字元、其中 '#' 代表不能走的路、'.' 代表可以走的路、'@' 代表老鼠的位置，'K' 代表喵喵的位置(初始老鼠跟喵喵皆恰有一隻！)，迷宮的四周一定會用 '#' 圍起來且一定是長方形。
接著有一個整數 $q$，代表要來幫助喵喵的貓咪數量，接下來有 $q$ 行，每行有三個整數 $t, x, y$，$t$ 代表貓加入地圖的時間點，$(x, y)$ 代表貓出現的位置。

\begin{itemize}
    \item $n,m \le 500$
    \item $q \le 10^5$
    \item $t \le n \times m$
    \item $1 \le x \le n,\ 1 \le y \le m$
\end{itemize}

\section*{Output}

對每組測試資料，請輸出離喵喵或其他貓咪最近的老鼠的位置 (也就是喵喵需要走幾格才能站到老鼠所在的位置？)，喵喵只能往上、往下、往右、往左走，如果沒有喵喵或其他貓咪能走到的老鼠請輸出 = ="(等號 + 空白 + 等號 + 雙引號)。

\section*{Sample 1}
\begin{longtable}[!h]{|p{0.5\textwidth}|p{0.5\textwidth}|}
\hline
\textbf {Input} & \textbf {Output} \\
\hline
\parbox[t]{0.5\textwidth}
{ \tt
% input
sample input 1
4 5
#####
#####
#K@##
#####
0
} &
\parbox[t]{0.5\textwidth}
{ \tt
%output
sample output 1
1
} \\
\hline
\end{longtable}

\section*{Sample 2}
\begin{longtable}[!h]{|p{0.5\textwidth}|p{0.5\textwidth}|}
\hline
\textbf {Input} & \textbf {Output} \\
\hline
\parbox[t]{0.5\textwidth}
{ \tt
% input
sample input 2
4 6
######
##.#.#
#@..K#
######
2
1 2 3
0 2 2
} &
\parbox[t]{0.5\textwidth}
{ \tt
%output
sample output 2
1
} \\
\hline
\end{longtable}

\section*{配分}

在一個子任務的「測試資料範圍」的敘述中，如果存在沒有提到範圍的變數，則此變數的範圍為 Input 所描述的範圍。

\begin{center}
 \begin{tabular}{||c c c||}
 \hline
 子任務編號 & 子任務配分 & 測試資料範圍 \\
 \hline\hline
 1 & 0\% & 範例測試資料 \\
 \hline
 2 & 10\% & $q = 0$ \\
 \hline
 3 & 20\% & $q \le 5$ \\
 \hline
 4 & 70\% & 無特別限制 \\
 \hline
\end{tabular}
\end{center}

\section*{Hint 1}
地圖是 0-base 的，左上角記做 (0, 0)

\end{document}