# APCS 20200105 非官方題目整理
### pA 猜拳
有一個機器人跟真人玩 $N$ 次猜拳，
真人在第$i$輪出的拳為 $y_i$，
機器人第一次會出的拳為 $F$，接下來出拳的方式如下：
如果前兩輪真人出的拳皆相同，則電腦這輪會出可以打敗前兩輪的拳；
否則，電腦會出與前一輪真人一樣的拳。
請輸出第 $k$ 輪時會分出勝負，或 $N$ 輪雙方都平手。
#### 輸入格式：
$F$
$N$
$y_1\ y_2\ ...\ y_N$
#### 輸出格式：
$c_1\ c_2\ ... \ c_k\ :$ ```Drew at round N```/```Won at round k```/```Lost at round k```
#### 範圍：
$F, y_i, c_i \in \{0, 2, 5\}$ （```0```指石頭，```2```指剪刀，```5```指布）
$N \leq 10$
#### 範例測資：
Input 1:
```
0
4
2 5 0 2
```
Output 1:
```
0 : Won at round 1
```
Input 2:
```
2
2
2 0
```
Output 2:
```
2 2 : Lost at round 2
```
Input 3:
```
5
4
5 5 0 0
```
Output 3:
```
5 5 2 : Lost at round 3
```
Input 4:
```
5
6
5 5 2 2 0 0
```
Output 4:
```
5 5 2 2 0 0 : Drew at round 6
```
#### 子題：
|子任務編號|分數|限制|
|:---:|:----:|:----------:|
| $1$ | $20$ |$N = 1$|
| $2$ | $20$ |$N = 2,~y_1 \ne y_2$|
| $3$ | $60$ |無額外限制|
---
### pB 矩陣
有一個高 $s$ 寬 $t$ 的小矩陣 $A$，和一個高 $n$ 寬 $m$ 的大矩陣 $B$，
第一行輸出大矩陣中有 $cnt$ 個高 $s$ 寬 $t$ 的子矩陣其「距離」與小矩陣不超過 $r$，
第二行輸出「距離」與小矩陣不超過 $r$ 的所有子矩陣中，元素總和差與小矩陣最小的值 $min$，
若找不到「距離」與小矩陣不超過 $r$ 的子矩陣，$min$ 請輸出```-1```。
距離的定義為兩矩陣中對應位置相同但值不相同的元素數量。
#### 輸入格式：
$s\ t\ n\ m\ r$
$A_{11}\ A_{12}\ ... \ A_{1t}$
$A_{21}\ A_{22}\ ... \ A_{2t}$
$\vdots$
$A_{s1}\ A_{s2}\ ... \ A_{st}$
$A_{11}\ A_{12}\ ... \ A_{1t}$
$A_{21}\ A_{22}\ ... \ A_{2t}$
$\vdots$
$A_{s1}\ A_{s2}\ ... \ A_{st}$
$B_{11}\ B_{12}\ ... \ B_{1m}$
$B_{21}\ B_{22}\ ... \ B_{2m}$
$\vdots$
$B_{n1}\ B_{s2}\ ... \ B_{nm}$
#### 輸出格式：
$cnt$
$min$
#### 範圍：
$1 \leq s, n \leq 10$
$1 \leq t, m \leq 100$
$1 \leq r \leq 100$
$0 \leq A_{ij}, B_{ij} \leq 9$
#### 範例測資：
Input 1:
```
1 3 1 10 1
7 4 7
6 7 7 7 4 5 0 4 4 7
```
Output 1:
```
3
2
```
Input 2:
```
3 3 5 5 2
1 2 1
2 4 2
2 4 5
1 2 1 2 3
2 4 2 4 2
2 4 2 3 5
3 2 4 2 0
3 2 4 5 5
```
Output 2:
```
3
1
```
#### 子題：
|子任務編號|分數|限制|
|:---:|:----:|:----------:|
| $1$ | $50$ |$s = m = 1$|
| $2$ | $50$ |無額外限制|
---
### pC 砍樹
有 $n$ 棵樹在一條長度為 $l$ 的林場上（林場為一條數線），
第 $i$ 棵樹的位置為 $c_i$，高度為 $h_i$，
一棵樹可以被砍倒若 $(c_i - h_i, c_i)$ （不含端點）這段區間都沒有還沒被砍倒的樹且 $h_i - c_i \geq 0$，
或$(c_i, c_i + h_i)$ （不含端點）這段區間都沒有還沒被砍倒的樹且 $h_i + c_i \leq l$，
輸出最多可以砍倒 $cnt$ 棵樹，以及被砍倒的樹中最高的一棵高度為 $max$。
若沒有樹可以被砍倒，$max$ 請輸出```0```。
#### 輸入格式：
$n\ l$
$c_1\ c_2\ ...\ c_n$
$h_1\ h_2\ ...\ h_n$
#### 輸出格式：
$cnt$
$max$
#### 範圍：
$1 \leq n \leq 10^5$
$1 \leq l < 10^9$
$0 \leq c_i \leq l$
$1 \leq h_i \leq 10^9$
#### 範例測資：
Input 1:
```
6 140
10 30 50 70 100 125
30 15 55 10 55 25
```
Output 1:
```
4
30
```
Input 2:
```
1 10
5
6
```
Output 2:
```
0
0
```
#### 子題：
|子任務編號|分數|限制|
|:---:|:----:|:----------:|
| $1$ | $20$ |$N \le 10$|
| $2$ | $40$ |$N \le 1000$|
| $3$ | $40$ |無額外限制|
---
### pD 貨物分配
有一顆 $2n - 1$ 節點的的二元樹，其中節點編號 $n$ 到 $2n - 1$ 是葉節點，為一個內容物重量為 $p_i$ 的紙箱，
節點編號 $1$ 到 $n-1$ 為轉接器，其中編號 $1$ 的轉接器是貨物的入口（根節點），
接下來有 $m$ 個貨物，每個貨物有自己的重量 $w_i$ ，
每個貨物會從根節點開始，往左右兩個轉換器/紙箱中權重較小的一邊移動，若權重相同，則會往左邊的轉換器/紙箱，
當第 $i$ 個貨物到達紙箱後，該紙箱的重量就會加上 $w_i$，
請輸出每個貨物到達的紙箱編號 $b_i$，以一個空白隔開。
一個轉換器/紙箱的權重為其子孫節點中所有紙箱的重量總和。
#### 輸入格式
$n\ m$
$p_n\ p_{n+1}\ ...\ p_{2n-1}$
$w_1\ w_2\ ...\ w_m$
$p_1\ s_1\ t_1$
$p_2\ s_2\ t_2$
$\vdots$
$p_{n-1}\ s_{n-1}\ t_{n-1}$
其中，$p_i\ s_i\ t_i$ 的意義為轉換器 $p_i$ 其左子節點編號為 $s_i$，右子節點編號為 $t_i$。
#### 輸出格式
$b_1\ b_2\ ...\ b_m$
#### 範圍
$1 \leq n \leq 10^5$
$1 \leq m \leq 100$
$(\Sigma_{i=n}^{2n-1} p_i) + (\Sigma_{j=1}^{n-1} w_i) \leq 10^9$
#### 範例測資
Input 1:
```
4 5
0 0 0 0
5 4 3 2 1
1 2 3
2 4 5
3 6 7
```
Output 1:
```
4 6 7 5 5
```
Input 2:
```
7 2
9 2 1 6 8 7 5
2 3
1 2 5
2 3 7
3 13 10
4 11 9
6 12 8
5 6 4
```
Output 2:
```
8 7
```
#### 子題：
|子任務編號|分數|限制|
|:---:|:----:|:----------:|
| $1$ | $20$ |$n \le 10,~s=2p,~t=2p+1$|
| $2$ | $30$ |$n \le 1000,~s=2p,~t=2p+1$|
| $3$ | $50$ |無額外限制|
###### tags: `APCS` `APCS 20200105`
Sign in with Wallet
Connect another wallet