SHOW:
|
|
- or go back to the newest paste.
1 | \documentclass[11pt,a4paper]{article} | |
2 | ||
3 | \usepackage{indentfirst} | |
4 | \usepackage{amssymb} | |
5 | \usepackage{subcaption} | |
6 | \usepackage{graphicx} | |
7 | \usepackage{longtable} | |
8 | \usepackage{fancyhdr} | |
9 | \usepackage{xeCJK} | |
10 | \usepackage{amsmath} | |
11 | \usepackage{amssymb} | |
12 | \usepackage{ulem} | |
13 | \usepackage{xcolor} | |
14 | \usepackage{fancyvrb} | |
15 | \usepackage{listings} | |
16 | \usepackage{soul} | |
17 | \usepackage{hyperref} | |
18 | \lstdefinestyle{C}{ | |
19 | language=C, | |
20 | basicstyle=\ttfamily\bfseries, | |
21 | numbers=left, | |
22 | numbersep=5pt, | |
23 | tabsize=4, | |
24 | frame=single, | |
25 | commentstyle=\itshape\color{brown}, | |
26 | keywordstyle=\bfseries\color{blue}, | |
27 | deletekeywords={define}, | |
28 | morekeywords={NULL,bool} | |
29 | } | |
30 | ||
31 | \setCJKmainfont{Noto Sans Mono CJK TC} | |
32 | ||
33 | \voffset -20pt | |
34 | \textwidth 410pt | |
35 | \textheight 650pt | |
36 | \oddsidemargin 20pt | |
37 | \newcommand{\XOR}{\otimes} | |
38 | \linespread{1.2}\selectfont | |
39 | ||
40 | \pagestyle{fancy} | |
41 | - | \lhead{2023 算法班第二階段認證碳烤} |
41 | + | \lhead{2024 算法班第一階段要認真考} |
42 | ||
43 | \begin{document} | |
44 | ||
45 | \begin{center} | |
46 | - | \section*{A. 題目名稱(主題)} |
46 | + | \section*{A. 喵喵抓老鼠-Extreme} |
47 | \end{center} | |
48 | ||
49 | \section*{Description} | |
50 | ||
51 | - | 題目敘述 |
51 | + | "喵喵喵喵喵!" |
52 | ||
53 | "吱吱吱吱吱!" | |
54 | ||
55 | - | 輸入格式 |
55 | + | 家裡的老鼠又在肆虐了,喵喵一個人抓覺得太累,所以他呼叫了其他的貓一起來抓老鼠,已知每隻貓加入地圖的時間點和位置,你可以幫助喵喵找出最近的老鼠有多遠嗎? |
56 | ||
57 | \section*{Input} | |
58 | - | \item 輸入限制 |
58 | + | 輸入檔的開頭會有兩個正整數 $n,m$,表示這組資料有幾行,每行有多少個字元。 |
59 | 接下來 $n$ 行字會表示一個迷宮,每行有 $m$ 個字元、其中 '#' 代表不能走的路、'.' 代表可以走的路、'@' 代表老鼠的位置,'K' 代表喵喵的位置(初始老鼠跟喵喵皆恰有一隻!),迷宮的四周一定會用 '#' 圍起來且一定是長方形。 | |
60 | 接著有一個整數 $q$,代表要來幫助喵喵的貓咪數量,接下來有 $q$ 行,每行有三個整數 $t, x, y$,$t$ 代表貓加入地圖的時間點,$(x, y)$ 代表貓出現的位置。 | |
61 | ||
62 | \begin{itemize} | |
63 | - | 輸出格式 |
63 | + | \item $n,m \le 500$ |
64 | \item $q \le 10^5$ | |
65 | \item $t \le n \times m$ | |
66 | \item $1 \le x \le n,\ 1 \le y \le m$ | |
67 | \end{itemize} | |
68 | ||
69 | \section*{Output} | |
70 | ||
71 | 對每組測試資料,請輸出離喵喵或其他貓咪最近的老鼠的位置 (也就是喵喵需要走幾格才能站到老鼠所在的位置?),喵喵只能往上、往下、往右、往左走,如果沒有喵喵或其他貓咪能走到的老鼠請輸出 = ="(等號 + 空白 + 等號 + 雙引號)。 | |
72 | ||
73 | \section*{Sample 1} | |
74 | \begin{longtable}[!h]{|p{0.5\textwidth}|p{0.5\textwidth}|} | |
75 | \hline | |
76 | \textbf {Input} & \textbf {Output} \\ | |
77 | \hline | |
78 | \parbox[t]{0.5\textwidth} | |
79 | { \tt | |
80 | % input | |
81 | sample input 1 | |
82 | 4 5 | |
83 | ##### | |
84 | ##### | |
85 | #K@## | |
86 | ##### | |
87 | 0 | |
88 | } & | |
89 | \parbox[t]{0.5\textwidth} | |
90 | { \tt | |
91 | %output | |
92 | sample output 1 | |
93 | 1 | |
94 | } \\ | |
95 | \hline | |
96 | \end{longtable} | |
97 | ||
98 | \section*{Sample 2} | |
99 | \begin{longtable}[!h]{|p{0.5\textwidth}|p{0.5\textwidth}|} | |
100 | \hline | |
101 | \textbf {Input} & \textbf {Output} \\ | |
102 | \hline | |
103 | \parbox[t]{0.5\textwidth} | |
104 | { \tt | |
105 | % input | |
106 | sample input 2 | |
107 | 4 6 | |
108 | ###### | |
109 | ##.#.# | |
110 | #@..K# | |
111 | ###### | |
112 | 2 | |
113 | 1 2 3 | |
114 | 0 2 2 | |
115 | } & | |
116 | - | 2 & 30\% & 限制一 \\ |
116 | + | |
117 | { \tt | |
118 | - | 3 & 30\% & 限制二 \\ |
118 | + | |
119 | sample output 2 | |
120 | - | 4 & 40\% & 無特別限制 \\ |
120 | + | 1 |
121 | } \\ | |
122 | \hline | |
123 | \end{longtable} | |
124 | ||
125 | \section*{配分} | |
126 | - | 本題測試資料量大,建議使用 \tt{scanf} 進行輸入。 |
126 | + | |
127 | - | 若使用 \tt{std::cin} 輸入,請在 \tt{main} 函式第一行加上 \tt{ios\_base::sync\_with\_stdio(0);} \tt{cin.tie(0);},且請勿跟 \tt{scanf} 混用,以免造成 Time Limit Exceeded。 |
127 | + | |
128 | ||
129 | \begin{center} | |
130 | \begin{tabular}{||c c c||} | |
131 | \hline | |
132 | 子任務編號 & 子任務配分 & 測試資料範圍 \\ | |
133 | \hline\hline | |
134 | 1 & 0\% & 範例測試資料 \\ | |
135 | \hline | |
136 | 2 & 10\% & $q = 0$ \\ | |
137 | \hline | |
138 | 3 & 20\% & $q \le 5$ \\ | |
139 | \hline | |
140 | 4 & 70\% & 無特別限制 \\ | |
141 | \hline | |
142 | \end{tabular} | |
143 | \end{center} | |
144 | ||
145 | \section*{Hint 1} | |
146 | 地圖是 0-base 的,左上角記做 (0, 0) | |
147 | ||
148 | \end{document} |