---
# System prepended metadata

title: 第十屆國中生程式設計營競賽翻譯

---

# A. 一塊蛋糕 Piece of Cake!

## 中文翻譯
:::success
今天是Greg的生日！為了慶祝，他的朋友Sam邀請Greg和其他兩位朋友參加一個小型派對。當然，每個生日派對都必須有蛋糕。

Sam訂了一個方形蛋糕。他橫向切了一刀，縱向又切了一刀。在吃蛋糕的興奮中，Sam忘記這兩刀要切在蛋糕的中央。

當然，最大塊的蛋糕應該給Greg，因為今天是他的生日。幫助Sam計算這兩刀切割所形成的最大塊蛋糕的體積。

:::
![](https://hackmd.io/_uploads/rJpZ43Vq2.png)
## 輸入說明
:::info
輸入的第一行包含三個整數 $n(2\le n \le 10,000)$ 方形蛋糕的邊長(以公分為單位)，
$h(0\lt h\lt n)$ 橫向切割距蛋糕邊緣的距離(公分)，和 $v(0\lt v\lt n)$ 縱向切割距蛋糕邊緣的距離(公分)。如圖所示。

每個蛋糕都是$4$公分厚。
:::
## 輸出說明
:::info
輸出在進行橫向和縱向切割後，四塊蛋糕中最大那塊的體積（以立方公分表示）。
:::

## 範例
:::warning
### 範例輸入1
    10 4 7
### 範例輸出1
    168
:::
:::warning
### 範例輸入2
    5 2 2
### 範例輸出2
    36
:::
:::warning
### 範例輸入3
    4 2 1
### 範例輸出3
    24
:::

---
# B. 免費食物 Free Food
## 中文翻譯
:::success
你知道什麼可以吸引多數大學生參加活動嗎？沒錯，免費的食物。無論這個活動是不是一場漫長（有時候無聊）的講座，只要有免費的食物提供，學生們一定會來的。

假設今年有 $N$ 個活動要舉行。第 $i^{th}$ 個活動從第 $s_i$ 天到第 $t_i$ 天進行，並且該活動進行的每一天（包含活動開始和結束兩天）都提供免費食物。你的任務是找出至少有一個活動提供免費食物的天數。

舉個例子，假設有 $N = 3$ 個活動。第一個活動從第$10$天到第$14$天，第二個活動從第$13$天到第
$17$天，第三個活動從第$25$天到第$26$天。至少有一個活動提供免費食物的日期包括
第$10,11,12,13,14,15,16,17,25,26$等天，總共有$10$天。需要注意的是，第一個和第二個活動都在第$13$天和第$14$天提供免費食物。
:::
## 輸入說明
:::info
第一行包含一個整數 $N(1\le N \le 100)$，表示活動的數量。接下來的 $N$ 行中，每行包含兩個整數 $s_i$ 和 $t_i$  $(1\le s_i \le t_i \le 365)$，表示第 $i^{th}$ 個活動將在第 $s_i$ 天到第 $t_i$ 天舉行（包含活動開始和結束兩天），並且在這些天裡提供免費食物。
:::
## 輸出說明
:::info
輸出中包含一個整數，表示有幾天至少有一個活動提供免費食物。
:::



## 範例
:::warning
### 範例輸入1
    3
    10 14
    13 17
    25 26

### 範例輸出1
    10
:::
:::warning
### 範例輸入2
    2
    1 365
    20 28

### 範例輸出2
    365
:::
:::warning
### 範例輸入3
    4
    29 29
    48 48
    102 102
    94 94

### 範例輸出3
    4
::: 
---



# C. 排隊 Line Them Up


## 中文翻譯

:::success

一位古怪的教練在練習開始時要求球隊的球員們按字典序排隊。但教練並未告訴球員們需要按照遞增還是遞減的順序排列，所以他們只能猜測。若猜測錯誤，教練會讓他們在練習前先跑幾圈。給定一個名字的列表，您需要判斷這個列表是按照遞增的字典序排列、遞減的字典序排列，還是兩者都不是。



:::
## 輸入說明
:::info
輸入包含一組測試資料。第一行包含一個整數 $N(2 \le N \le 20)$ 代表球隊的人數。其後是 $N$ 行，每行包含一個人的名字。每個名字至少包含兩個字符，最多$12$個字符，並且只會由大寫字母組成，且不包含任何空格（抱歉，BILLY BOB和MARY JOE）。同一個球隊中不會有重複的名字。
:::
## 輸出說明
:::info
請輸出一個單字作為結果：若這個列表是按照遞增的字典序排列，則輸出"INCREASING"；若是按照遞減的字典序排列，則輸出"DECREASING"；若不符合上述兩種順序，則輸出"NEITHER"。
:::

## 範例
:::warning
### 範例輸入1
    5
    JOE
    BOB
    ANDY
    AL
    ADAM


### 範例輸出1
    DECREASING

:::
:::warning
### 範例輸入2
    11
    HOPE
    ALI
    BECKY
    JULIE
    MEGHAN
    LAUREN
    MORGAN
    CARLI
    MEGAN
    ALEX
    TOBIN


### 範例輸出2
    NEITHER

:::
:::warning
### 範例輸入3
    4
    GEORGE
    JOHN
    PAUL
    RINGO


### 範例輸出3
    INCREASING

::: 

---

# D. 選舉 Popular Vote
## 中文翻譯
:::success

在超過兩名候選人參與的選舉中，經常出現的情況是獲勝者（得到最多選票的候選人）所獲得的選票數未超過過半數。根據選舉結果，我們能否確定獲勝者，以及該獲勝者是否獲得了超過一半的選票呢？
:::
![](https://hackmd.io/_uploads/B1ckU0Vch.png)

## 輸入說明
:::info
輸入的第一行包含一個正整數 $T \le 500$ ，表示測試案例的數量。每個測試案例的第一行也包含一個正整數 $n$，表示選舉中候選人的數量。接下來是 $n$ 行，其中第 $i^{th}$ 行包含一個非負整數，表示候選人 $i$ 的選票數。

每個測試案例中的候選人數至少為$2$，但不會超過$10$。每位候選人的選票數不會超過$50,000$。每場選舉中至少會有一張選票被投出。
:::
## 輸出說明 
:::info
對於每個測試案例，請提供一行輸出。如果獲勝者獲得的選票數超過一半，請輸出 "majority winner"，後跟獲勝者的候選人編號。如果獲勝者未獲得超過一半的選票，請輸出 "minority winner"，後跟獲勝者的候選人編號。如果無法確定獲勝者，就是沒有一位候選人的選票數超過其他所有候選人，請輸出 "no winner"。每個測試案例中的候選人編號為$1,2,...,n$。
:::

## 範例
:::warning
### 範例輸入
    4
    3
    10
    21
    10
    3
    20
    10
    10
    3
    10
    10
    10
    4
    15
    15
    15
    45


### 範例輸出
    majority winner 2
    minority winner 1
    no winner
    minority winner 4


:::
---

# E. 怪獸卡車 Cudoviste
> 
## **中文翻譯**
:::success

Mirko拿到了駕照！為了慶祝這個喜悅的時刻，他的父母為他買了第一輛車：一輛怪獸卡車！Mirko發現，儘管擁有一輛能夠壓扁其他所有車輛的車在塞車時很好用，但停放一輛大小是普通車$4$倍的車有點棘手。

他的朋友Slavko在城市停車公司兼職。他定期向Mirko發送一張標有已佔用停車位的城市地圖。地圖可以表示為一個表格，有 $R$ 行、$C$ 列。每個單元格（空間）可以是一座建築（符號 '#'）、一輛已停放的車（符號 'X'）或一個空停車位（符號 '.'）。怪獸卡車相當巨大，它佔據了$2$x$2$（兩行又兩列）的空間。

幫助Mirko計算按照壓扁的車輛數量分組的停車方法數。我們只關心Mirko在停車位上需要壓扁的車輛數量，而不是他在前往停車位的路上壓扁的車輛數量。注意，Mirko不能停在建築物上。即使是怪獸卡車也不夠大到可以壓扁建築物！
:::
## 輸入說明
:::info
輸入的第一行包含兩個整數 $R$ 和 $C(2 \le R,C \le 50)$，分別代表地圖的行數和列數。接下來的 $R$ 行包含 $C$ 個字符。輸入中只會出現字符'#','X'和 '.'。請注意，'X' 字符永遠是大寫。
:::
## 輸出說明
:::info
輸出結果包含五行，分別為Mirko在壓扁$0$輛車時可以停放的總停車位數（第一行）、壓扁$1$輛車時的可停車位數（第二行）、壓扁$2$輛車時的可停車位數（第三行）、壓扁$3$輛車時的可停車位數（第四行）和壓扁$4$輛車時的可停車位數（第五行）。



:::

## 範例
:::warning
### 範例輸入1
    4 4
    #..#
    ..X.
    ..X.
    #XX#

### 範例輸出1
    1
    1
    2
    1
    0


:::
:::warning
### 範例輸入2
    4 4
    ....
    ....
    ....
    ....



### 範例輸出2
    9
    0
    0
    0
    0


:::
:::warning


### 範例輸入3
    4 5
    ..XX.
    .#XX.
    ..#..
    .....




### 範例輸出3
    2
    1
    1
    0
    1
:::

---


# F. 圖像處理 Image Processing


## 中文翻譯
:::success
像Photoshop這樣的圖像編輯軟體提供許多圖像效果，例如模糊、銳化和邊緣檢測。這些效果通常是通過核心（kernel）來實現的，核心是描述某種圖像效果的矩陣。將核心應用於圖像時使用卷積：先將核心的行和列都進行翻轉，然後對應位置的元素進行乘法並相加。

例如，假設我們有一張 $4$x$4$ 的圖像：

$\begin{bmatrix} a & b & c & d\\ e & f & g & h \\ i & j & k & l \\ m & n & o & p \end{bmatrix}$

以及以下 $2$x$2$ 的核心：

$\begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix}$

經過卷積後，結果圖像如下：

$\begin{bmatrix} 4a+3b+2e+1f & 4b+3c+2f+1g & 4c+3d+2g+1h \\ 4e+3f+2i+1j & 4f+3g+2j+1k & 4g+3h+2k+1l \\ 4i+3j+2m+1n & 4j+3k+2n+1o & 4k+3l+2o+1p \end{bmatrix}$

這在現實世界中的一個例子是模糊效果：
![](https://hackmd.io/_uploads/rJdxAAVq3.png) => ${1\over9}\begin{bmatrix} a & b \\ c & d \end{bmatrix}$ => ![](https://hackmd.io/_uploads/S13QR0Nc3.png)
:::
## 輸入說明
:::info
輸入的第一行包含四個整數：$H,W,N,M$，分別表示圖像的高度、寬度，核心的高度和寬度 $（1 \le H \le 20, 1 \le W \le 20, 1 \le N \le H, 1 \le M \le W）$ 。

接下來的 $H$ 行中，每行包含 $W$ 個整數，範圍從 $0$ 到 $100$ ，表示圖像的像素值。

接下來的 $N$ 行中，每行包含 $M$ 個整數，範圍從 $0$ 到 $100$ ，表示核心矩陣的元素值。
:::
## 輸出說明
:::info
請輸出卷積後的結果圖像，包含 $H-N+1$ 行，每行有 $W-M+1$ 個整數。
:::
## 範例
:::warning
### 範例輸入
    4 4 2 2
    1 2 3 4
    5 6 7 8
    9 10 11 12
    13 14 15 16
    1 2
    3 4
### 輸出
    26 36 46
    66 76 86
    106 116 126
:::

---

# G. 故障機器人 Malfunctioning Robot
## 中文翻譯
:::success
Arthur參加了$2020$越南機器人奧林匹克比賽。在第一輪比賽中，參賽者必須建造一個尋徑機器人。更確切地說，主辦單位準備了一個無限大、無障礙物的方格網。一個參賽者的機器人被放置在起始位置 $(x_1,y_1)$，必須找到一條到達目標位置 $(x_2,y_2)$ 的路徑。

Arthur的機器人相當簡單：它只能在四個方向上移動：上、下、左和右，即從位置 $(x,y)$，它可以移動到 $(x,y+1),( x,y-1),(x-1,y)\ 和\ (x+1,y)$。

第一輪比賽即將開始。然而，Arthur剛剛意識到機器人的某些元件損壞了，因此機器人不能在連續兩步中以相同的方向移動（換句話說，它每次移動後都會改變方向）。例如，如果機器人需要從 $(1,1)$ 移動到 $(3,3)$ ，機器人可以使用右圖所示的路徑，但不能使用左圖所示的路徑。
:::
![](https://open.kattis.com/problems/malfunctioningrobot/file/statement/en/img-0001.png)
## 輸入說明
:::info
輸入以一個整數 $T$ 開始，表示測試案例的數量 $(1 \le T \le 1,000)$ ，然後是 $T$ 個測試案例。每個測試案例都以一行表示，包含$4$個整數，分別為$x_1, y_1,x_2\ 和\ y_2$，分別表示機器人的起始位置和目標位置。

輸入中所有整數的絕對值均不超過$10^9$。
:::
## 輸出說明
:::info
對於每個測試案例，請輸出Arthur的機器人從 $(x_1,y_1)$ 到達  $(x_2,y_2)$ 所需的最小移動次數。
:::
## 範例
:::warning
### 範例輸入
    2
    1 1 3 3
    0 1 1 1
### 範例輸出
    4
    1
:::
# H. 聯合攻擊 Joint Attack

## 中文翻譯
:::success
將軍Torstein已經發送了下一次聯合攻擊的座標給你，並希望你遵從他的指示，以避免災難的發生。不幸的是，Torstein將軍討厭超過$2$位數的數字，並且喜歡水平線段，因此他將座標以連分數的形式發送，即：
$$x= x_0+{1\over {x_1+{1\over...}}}$$
由於您的火箭發射器只接受普通分數形式$（a/b）$（不須化簡）的座標，所以您需要迅速計算正確的數字，以便開始攻擊。請加快速度！失敗可能會帶來嚴重後果！
:::
![](https://hackmd.io/_uploads/BJIZ8A45h.jpg)

## 輸入說明
:::info
輸出的第一行是一個整數 $n\ (1\le n \lt 40)$ ，表示連分數中的係數數量，接下來是一行包含 $n$ 個整數 $(1 \le x_0,x_1,x_2... \lt 100)$ 。
:::
## 輸出說明
:::info
將座標 $x$ 轉換為簡化分數形式。保證分子和分母都小於 $10^{18}$。
:::
## 範例
:::warning
### 範例輸入
    2
    2 3
### 範例輸出
    7/3
範例解釋:
$x={2+{1\over 3}}={7\over 3}$
### 補充範例輸入
    4
    5 3 2 7
### 補充範例輸出
    275/52
補充範例解釋:
$x=5+{1\over 3+{1\over 2+{1\over 7}}}={275\over 52}$
:::

