# 2024/2/24 APCS 第二場模擬賽 題解
## 氧化還原滴定 (Redox titration)
> 出題者：Cheng
> 難度：p1
> 考點：if 條件式、加減乘除、基本資料型態
### statement
正在準備科學班的 Cheng 進到了實驗室做氧化還原滴定的實驗，
在實驗室中拿了過錳酸鉀($KMnO_4$)、硫酸溶液($H_2SO_4$)、草酸鈉溶液($Na_2C_2O_4$)與蒸餾水($H_2O$)
Cheng 將草酸鈉、硫酸混和後使用蒸餾水稀釋，並將他們加熱至 70℃，
以過錳酸鉀滴定草酸鈉溶液，當滴定至再加入一滴而紫色不消失時，即為滴定終點
反應式如下：
$2MnO_4^- + 5C_2O_4^{2-} + 16H^+ \longrightarrow 2Mn^{2+} + 10CO + 8 H_2O$
當反應式達到當量點時：
* 氧化劑當量數 = 還原劑當量數
* 氧化劑莫耳數 $\times$ $n_1$ = 氧化劑莫耳數 $\times$ $n_2$
($n_1$：氧化劑氧化數變化、$n_2$：還原劑氧化數變化)
* $C_1 \times V_1 \times n_1 = C_2 \times V_2 \times n_2$
($C_1$：氧化劑濃度、$C_2$：還原劑濃度、$V_1$：氧化劑體積、$V_2$：還原劑體積)
在 Cheng 做的實驗當中已知以下內容：
* $Na_2C_2O_4$ 的氧化數變化 ($n_1$) = 2
* $KMnO_4$ 的氧化數變化 ($n_2$) = 5
如果 Cheng 拿的過錳酸鉀為 $C_1$ 體積莫耳濃度
草酸鈉為 $C_2$ 體積莫耳濃度
錐形瓶內有 $V_2$ ml 的草酸鈉
當 Cheng 滴了 $V_1$ ml 的過錳酸鉀時是否剛好達到當量點？
因為 Cheng 太笨了，請你幫幫他吧！
### Input
測資範圍：
* $1 \leq C_1, C_2, V_1, V_2 \leq 10^4$
輸入只有一行，
有四個整數，分別為 $C_1$、$C_2$、$V_1$、$V_2$
### Output
輸出 Yes 或 No
代表是否剛好達到當量點
如果是，請輸出當量數
### Testcase
- Input 1 (Sample)
```
2 2 5 2
```
- Output 1 (Sample)
```
Yes
20
```
### Subtask
- Subtask 1 (50%) - 必定剛好達到當量數
- Subtask 2 (50%) - 無其他限制
### Note
範例 1 解釋：
$2 \times 5 \times 2$ = 20
$2 \times 2 \times 5$ = 20
所以答案為 Yes
### Solution
用 if 條件式判斷 $C_1 \times V_1 \times 2 = C_2 \times V_2 \times 5$
### Code
```cpp=
#include <iostream>
using namespace std;
int main()
{
int C1, C2, V1, V2;
cin >> C1 >> C2 >> V1 >> V2;
int n1 = 2, n2 = 5;
if(C1 * V1 * n1 == C2 * V2 * n2) cout << "Yes\n" << C1 * V1 * n1 << '\n';
else cout << "No\n";
return 0;
}
```
- Python by 橘子
```python=
c1,c2,v1,v2 = map(int,input().split())
if c1*v1*2==c2*v2*5:
print("Yes")
print(c1*v1*2)
else:
print("No")
```
```python!
print((lambda a,b,c,d:"Yes\n"+str(a*c*2) if a*c*2==b*d*5 else "No")(*map(int,input().split())))
```
## Charles 的頂級球隊 (Soccer-Team)
> 出題者：Howard
> 難度：p2
> 考點：二維陣列
### statement
2026 年世足賽馬上就要到了，相信大家對 2022 的世足賽肯定是意猶未盡，Charles便是如此，在 2022 的世界盃足球賽進行時間，Charles 沒日沒夜看世足，尤其愛法國隊，但是下次世界盃是由美洲國家所舉辦，時差幾乎差了 12 小時，難道 Charles 要繼續熬夜下去了嗎？
這時他的天兵好友Howard跟他說，欸欸我想到一個辦法，若是你能當上法國隊總教練，不就不會有這個問題了嗎？而且還可以享受最接近球員現場比賽的福利，可說是一舉兩得。
Charles經過三思熟慮後，決定要嘗試看看當上法國隊總教練，而很慶幸的是，因為法國隊球員Antoine Griezmann被Charles熬夜為他們加油的心所打動，讓Charles當上下一屆世足總教練。
經過了長時間的練習，終於到了 2026 世界盃足球賽當天。
身為住在台灣的 Howard，當然要為好友所在的隊伍加油打氣，但是 Howard 是一位賽後分析師專家，他希望能夠有一套系統，能夠幫助他在賽後好好分析整場比賽的球員更換狀況，以及在某個時間點場上所有的球員為何，所以想要請你寫一個程式幫助他。
首先會給定你 $11$ 個數字，這些數字為當天先發上場的球員背號，接下來會有一些換人事件，每次都會給你被換下來的人的背號和接替此球員的背號以及此次換人的時間，最後會有一些詢問，每個詢問為在某個時間點場上 $11$ 人的背號(需照順序排隊，不可改變順序)。
### Input
第一行有兩個數字 $n(0\leq n\leq 150)$ 和 $q(1\leq q\leq 1000)$，分別代表換人次數和 Howard 想詢問的次數，中間以空白間隔開。
第二行會有 $11$ 個數字 $a_1,a_2,a_3,...,a_{11}(1\leq a_1,a_2,a_3,...,a_{11}\leq 100)$，分別代表當天先發 $11$ 人的背號，保證數字不會重複，中間以空白間隔開。
接下來總共會有 $n$ 行，每行有四個數字分別為此次替補球員上場時間 $M$(分) $0\leq M\leq 90$ 、次替補球員上場時間 $S$ (秒) $0\leq S\leq 59$、換下來的背號$C$ (保證他在場上)、換上去的背號$D$ (保證他不在場上)，中間以空白間隔開，輸入時間點皆已經排序。
最後會有 $q$ 行，為Howard想知道目前場上球員的時間點，每行有兩個數字分別代表分鐘 $L(0\leq L\leq 90)$、秒鐘 $R(0\leq R\leq 59)$，中間以空白間隔開。
若在某個時間點同時有球員交換且 Howard 也想要知道當前場上狀況，請輸出球員交換後的場上 $11$ 人。
### Output
輸出共 $q$ 行，每行有 $11$ 個數字，分別代表在當前詢問中，場上 $11$ 人為何，不可改變背號順序。
### Testcase
- Input 1
```
1 6
1 2 54 64 73 8 29 40 45 82 21
20 18 21 99
11 40
9 45
49 3
72 16
50 23
82 1
```
- Output 1
```
1 2 54 64 73 8 29 40 45 82 21
1 2 54 64 73 8 29 40 45 82 21
1 2 54 64 73 8 29 40 45 82 99
1 2 54 64 73 8 29 40 45 82 99
1 2 54 64 73 8 29 40 45 82 99
1 2 54 64 73 8 29 40 45 82 99
```
- Input 2
```
4 2
95 62 54 98 17 43 91 8 83 44 85
20 18 8 48
25 9 62 21
50 59 48 82
67 39 54 12
20 31
55 34
```
- Output 2
```
95 62 54 98 17 43 91 48 83 44 85
95 21 54 98 17 43 91 82 83 44 85
```
### Subtask
- Subtask 1 (50%) - $n=1$
- Subtask 2 (50%) - 無其他限制
### Solution
- Subtask 1
直接判斷目前詢問時間在這唯一一次換人時間的前後，進行輸出，故場上球員只會有兩種情況
- Subtask 2
在每次詢問中，模擬場上交換球員，直到目前詢問時間，再將此時間點場上球員輸出
### Code
- Subtask 1
```cpp=
#include <iostream>
using namespace std;
struct INPUT_DATA {
int M;
int S;
int down;
int up;
int time;
};
int main()
{
int n, q;
cin >> n >> q;
int now[11];
int change[11];
for(int i = 0; i < 11; i++) {
cin >> now[i];
change[i] = now[i];
}
INPUT_DATA input;
for(int i = 0; i < n; i++) {
cin >> input.M >> input.S >> input.down >> input.up;
input.time = input.M * 60 + input.S;
}
for(int i = 0; i < 11; i++) {
if(change[i] == input.down) {
change[i] = input.up;
break;
}
}
int ans[q][11];
for(int i = 0; i < q; i++) {
int L, R;
cin >> L >> R;
int time = L * 60 + R;
if(time >= input.time) {
for(int j = 0; j < 11; j++) ans[i][j] = change[j];
}
else {
for(int j = 0; j < 11; j++) ans[i][j] = now[j];
}
}
for(int i = 0; i < q; i++) {
for(int j = 0; j < 11; j++) {
cout << ans[i][j] << ' ';
}
cout << '\n';
}
return 0;
}
```
- Subtask 2
```cpp=
#include <iostream>
using namespace std;
struct INPUT_DATA {
int M;
int S;
int down;
int up;
int time;
};
int main()
{
int n, q;
cin >> n >> q;
int now[11];
for(int i = 0; i < 11; i++) {
cin >> now[i];
}
INPUT_DATA input[n];
for(int i = 0; i < n; i++) {
cin >> input[i].M >> input[i].S >> input[i].down >> input[i].up;
input[i].time = input[i].M * 60 + input[i].S;
}
int ans[q][11];
for(int i = 0; i < q; i++) {
int L, R;
cin >> L >> R;
int time = L * 60 + R;
int tmp[11];
for(int j = 0; j < 11; j++) tmp[j] = now[j];
for(int j = 0; j < n; j++) {
if(input[j].time <= time) {
int on_index;
for(int k = 0; k < 11; k++) {
if(tmp[k] == input[j].down) {
on_index = k;
break;
}
}
tmp[on_index] = input[j].up;
}
else break;
}
for(int j = 0; j < 11; j++) ans[i][j] = tmp[j];
}
for(int i = 0; i < q; i++) {
for(int j = 0; j < 11; j++) {
cout << ans[i][j] << (j == 10 ? '\n' : ' ');
}
}
return 0;
}
```
- Python by 橘子
```python=
n,q = map(int,input().split())
a = list(map(int,input().split()))
o = {a[i]:i for i in range(11)}
l = []
for i in range(n):
m,s,c,d = map(int,input().split())
l.append((m*60+s,0,c,d))
for i in range(q):
m,s = map(int,input().split())
l.append((m*60+s,1,i,0))
ans = [""]*q
l.sort()
for skip,t,c,d in l:
if t:
ans[c] = " ".join(str(i) for i in a)
else:
idx = o[c]
a[idx] = d
o[d] = idx
print("\n".join(ans))
```
```python!
print("\n".join((lambda n,q,a:(lambda o,l,ans:l.sort() or sum(bool(ans.__setitem__(c," ".join(str(i) for i in a)) if t else a.__setitem__(o[c],d) or o.__setitem__(d,o[c])) for skip,t,c,d in l) or ans)({a[i]:i for i in range(11)},[(m*60+s,0,c,d) for m,s,c,d in (map(int,input().split()) for _ in range(n))]+[(m*60+s,1,i,0) for m,s,i in ((*map(int,input().split()),i) for i in range(q))],[""]*q))(*map(int,input().split()),list(map(int,input().split())))))
```
## S 盒模擬 (S-BOX-Simulate)
> 出題者：小麥
> 難度：p3
> 考點：位元運算、二維陣列
### statement
在密碼學裡面有一種盒子叫 S 盒，其功能是用來模糊金鑰與密文之間的關係，對於一個大小為 $n$ 的 S 盒，其格子數為 $2^n$，以下是一個大小為 $3$ 的 S 盒，可以發現欄和列相乘剛好有 $2^3$ 個元素。
| | 0 | 1 |
| :-----:| :------: | :------: |
| 00 | 7 | 0 |
| 01 | 5 | 5 |
| 10 | 4 | 10 |
| 11 | 6 | 0 |
其作用為將一筆固定 bit 數的資料（以上方 S 盒為例為 $3$ bit）的**最高位**和**最低位**取出來做為列，將中間的部分（除了**最高位**和**最低位**）做為欄。透過觀察可以發現，列會固定為 $00, 01, 10, 11$，而欄則會是 $0 \sim 2^{n-2}-1$ 的二進制表示法。
使用上述大小為 $n = 3$ 的 S 盒舉例，例如要將資料 "$2$" 使用 S 盒變換，則要先把 $2$ 拆成 $n = 3$ 位數的二進位 $010$，其列**最高位**和**最低位**為 $0,0$；欄為 $010$ 去掉**最高位**和**最低位**，因此只剩下 $1$，因此對應到 S 盒的第 $00$ 列，第 $1$ 欄的值，也就是 $0$。
本題的 S 盒大小至少（含） $3$ bit，也就是說本題的所有 S 盒都是 $4$ 列的。
### Input
第一行包含兩個正整數 $n$ 和 $m$。
- $n$ 為 S 盒的大小。
- $m$ 為要變換的資料數量。
接下來有 $4$ 行，每行包含 $2^{n-2}$ 個正整數。
- 第 $i$ 行的資料代表 S 盒的第 $i$ 行，由左而右填入。
接下來有 $m$ 個正整數，每個數字 $a$ 代表要變換的資料。
**範圍**
- $3 \leq n \leq 18$
- $1 \leq m \leq 5 \times 10^5$
- $1 \leq a \leq 2^n-1$
### Output
輸出每個變換過的數字。
### Testcase
- Input 1
```
3 6
7 0
5 5
4 10
6 0
2 3 6 2 4 5
```
- Output 1
```
0 5 10 0 4 6
```
### Subtask
- Subtask 1 (20%)：$n = 3$
- Subtask 2 (80%)：題目範圍限制
### Solution by Chung
- Subtask 1
- 可以直接打表
- 總時間複雜度：$O(m)$
- Subtask 2
- 目標其實就是以下三種
- 找出 $a$ 的二進制在 $n$ 位數的情況下的最高位
- 找出 $a$ 的二進制在 $n$ 位數的情況下的最低位
- 求出扣掉頭尾剩下的部分
- 第一個目標：找出 $a$ 的二進制在 $n$ 位數的情況下的最高位
- 使用 `(1 << (n-1))` 可以得出一個 $1 + (n-1\ 個\ 0)$ 的二進制數字
- 拿 `1 << (n-1)` 去和 $a$ 做 $AND$ 運算
- 因為 `1 << (n-1)` 除了最高位的 $1$ 以外其餘都是 $0$，所以 $AND$ 出來的結果只有 $0$ 或 `1 << (n-1)` 兩種，因此就可以透過檢查 $AND$ 出來的結果是不是 $0$ 來判斷最高位是 $0$ 還是 $1$
- 第二個目標：找出 $a$ 的二進制在 $n$ 位數的情況下的最低位
- 其實會發現就是 `x % 2` 的結果
- 因為所有奇數的二進制最低位必定是 $1$ (偶數則必是 $0$)，所以只需要使用 `x % 2` 即可判斷最低位
- 第三個目標：求出扣掉頭尾剩下的部分
- 筆者的作法是先讓 $a$ 減去最高位之後再將 $a$ 右移
- 求解過程圖
- 求出這三個東西之後，就可以查詢 S 盒了
- 因為 `high` 在非 $0$ 的情況下不一定是 $1$，可以用 `(bool)` 強制轉型
- `S[(bool)high * 2 + low][left]`
- 總時間複雜度：$O(m)$
### Code
- Subtask 1 by Chung
```cpp=
#include<bits/stdc++.h>
using namespace std;
int n,m,S[4][2];
// ans[i] = {high, low, left}
int ans[8][3] = {{0,0,0}, {0,1,0}, {0,0,1}, {0,1,1}, {1,0,0}, {1,1,0}, {1,0,1}, {1,1,1}};
int main(){
cin>>n>>m;
for(int i=0;i<4;i++) for(int j=0;j<2;j++) cin>>S[i][j];
while(m--){
int x; cin>>x;
int high = ans[x][0];
int low = ans[x][1];
int lft = ans[x][2];
cout<<S[high * 2 + low][lft]<<" \n"[m==0];
}
}
```
- Subtask 2
```cpp=
#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio; cin.tie(0); cout.tie(0);
// #define int long long
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
int n, m;
vvi table;
void solve()
{
cin >> n >> m;
table.resize(4, vi(1 << (n - 2)));
int count = 0;
int count2 = 0;
for (int i = 0; i < (1 << n); i++)
{
cin >> table[count2][count];
count++;
if (count == 1 << (n - 2))
{
count2++;
count = 0;
}
}
for (int i = 0; i < m; i++)
{
int a;
cin >> a;
int data = a;
int x = (((a & (1 << (n-1))) != 0) << 1) + (((a & 1) != 0));
for (int j = 0; j < 1 << (n - 2); j++)
{
if ((a & (((1 << n) - 1) ^ (1 << (n - 1))) & (((1 << n) - 1) ^ 1)) == (j << 1))
{
cout << table[x][j];
break;
}
}
if (i != m - 1) cout << ' ';
}
cout << '\n';
}
signed main()
{
fastio;
solve();
return 0;
}
```
- Subtask 2 by Chung
```cpp=
#include<bits/stdc++.h>
using namespace std;
int n,m,S[4][1<<19];
int main(){
cin>>n>>m;
for(int i=0;i<4;i++){
for(int j=0;j<(1<<(n-2));j++){
cin>>S[i][j];
}
}
while(m--){
int x; cin>>x;
int high = x & (1<<(n-1));
int low = (x % 2);
int lft = (x-high)>>1;
cout<<S[(bool)high*2+low][lft]<<" \n"[m==0];
}
}
```
```cpp=
#include<bits/stdc++.h>
using namespace std;
int n,m,S[4][1<<19];
int main(){
cin>>n>>m; for(int i=0;i<4;i++) for(int j=0;j<(1<<(n-2));j++) cin>>S[i][j];
while(m--){ int x; cin>>x; cout<<S[(bool)(x&(1<<(n-1)))*2+(x&1)][x-(x&(1<<(n-1)))>>1]<<" \n"[m==0];}
}
```
- 另解 by 橘子
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);cin.tie(0);
int n,m,x;
cin >> n >> m;
vector<vector<int>> a(4,vector<int>(1<<n>>2));
for(auto &o : a) for(int &i : o) cin >> i;
vector<int> b(1<<n);
for(int i=0;i<2;i++)
for(int j=0;j<1<<n>>2;j++)
for(int k=0;k<2;k++)
b[i<<n>>1|j<<1|k] = a[i<<1|k][j];
while(m--){
cin >> x;
cout << b[x] << "\n "[m>0];
}
}
```
- Python 位元運算
```python=
n,m = map(int,input().split())
S = [input().split() for _ in range(4)]
for i,s in enumerate(input().split()):
x = int(s)
high = x & (1<<(n-1));
low = (x % 2);
lft = (x-high)>>1;
print(S[bool(high)*2+low][lft],end=" \n"[i==m-1])
```
- Python bin()
```python=
n,m = map(int,input().split())
S = [input().split() for _ in range(4)]
for i,s in enumerate(input().split()):
b = bin(int(s))[2:]
b = "0"*(n-len(b))+b
x = int(b[0]+b[-1],2)
y = int(b[1:-1],2)
print(S[x][y],end=" \n"[i==m-1])
```
- Python by 橘子
```python=
n,m = map(int,input().split())
a = [input().split() for _ in range(4)]
b = [a[i*2+k][j] for i in range(2) for j in range(2**(n-2)) for k in range(2)]
for i,s in enumerate(input().split()):
print(b[int(s)],end=" \n"[i==m-1])
```
```python!
print(*(lambda n,m,a:(a[(x>>n-1)<<1|x&1][x>>1&((1<<n-2)-1)] for x in map(int,input().split())))(*map(int,input().split()),[input().split() for _ in range(4)]))
```
- Python 另解 ft. 皮皮
```python=
n,m = map(int,input().split())
a = [""]*(2**n)
a[:2**(n-1):2] = input().split()
a[1:2**(n-1):2] = input().split()
a[2**(n-1)::2] = input().split()
a[2**(n-1)+1::2] = input().split()
for i,s in enumerate(input().split()):
print(a[int(s)],end=" \n"[i==m-1])
```
## 逃脫遊戲 (Game)
> 出題者：binghua
> 難度：p4
> 考點：BFS、狀態紀錄
### statement
今天小明在玩一個逃脫遊戲，內容是要在一個 $N \times N$ 個密室中，由左上 $(1, 1)$ 的房間成功離開到右下角 $(N, N)$ 的房間，一次可以移動到上下左右的任一個房間，並要花費一單位時間。且因為小明是個重度玩家，他每次都要求自己要在越短的時間完成越好。然而，有 $K$ 個密室中有快速通道，可以在同樣花費一單位時間的情況下快速移動到另一個房間 (可以踏入房間但不選擇走通道)。但一旦通過通道就會被裡面的毒氣扣一滴血，而若到達零血量就會結束遊戲 (也就是小明整個過程的血量都要大於 $0$，假如在抵達右下角的瞬間時血量歸零，一樣不算是逃脫成功)。現在想請問你，小明在初始為 $T$ 滴血的情況下，最快多久可以破關 ?
### Input
第一行包含兩個正整數 $N$、$K$、$T$。
$N(1 ≤ N ≤ 250)$ 代表密室的大小，$K(1≤K≤N^2)$ 代表有幾個快速通道，$T(1 \le T \le 10)$ 代表初始的血量。
接下來有 $K$ 行，每行有 $4$ 個正整數 $X_1, Y_1, X_2, Y_2$ $(1 ≤ X_1, Y_1, X_2, Y_2 ≤ N)$，代表可以從 $(X_1, Y_1)$ 的點移動到 $(X_2, Y_2)$ 的點；$(a, b)$ 代表由上到下第 $a$ 個點，由左到右第 $b$ 個點。
### Output
輸出一行。
第一行輸出一個數字，代表到達左下角所花的最少時間。
### Testcase
- Input 1
```
50 1
13 22 39 50
```
- Output 1
```
45
```
- Input 2
```
50 4
3 1 2 10
2 11 15 16
20 24 46 50
15 16 18 20
```
- Output 2
```
30
```
### Subtask
- Subtask 1 (20%) - $T = 2$
- Subtask 2 (20%) - $T > K$
- Subtask 3 (60%) - 無任何限制
### Note
>測資一說明：
>直接走通道，12 + 21 + 1 + 11 = 45
>測資二說明：
>先從 (1, 1) 走到 (2, 11)，再走快速通道到 (15, 16)，再走到 (20, 24)，再走快速通道到 (46, 50)，再走到 (50, 50)，總共 (2 – 1) + (11 – 1) + 1 + (20 – 15) + (24 – 16) + 1 + (50 – 46) = 30
### Solution by Chung
- Subtask 1
- $T = 2$ 代表我們至多只能使用一條快速通道，因此我們可以枚舉所有的通道，然後對於每個通道利用數學計算 起點 -> 通道 -> 終點 的距離並取最小的作為答案。
- 總時間複雜度：$O(K)$
- Subtask 2
- $T > K$ 代表我們不需要去思考血量的問題 (因為就算走過所有通道血量還是不會歸零)，因此只要對上下左右以及通道建邊，實作 BFS 即可通過此題。
- 總時間複雜度：$O(N^2)$
- Subtask 2 (另解 by 橘子)
- 從 $K < T$ 推得 $K \le 9$，所以可以直接枚舉使用了哪幾個快速通道並利用類似 Subtask 1 的數學計算法
- 總時間複雜度：$O(K\cdot K!)$
- Subtask 3
- 因為還要考慮血量可能不足的問題，因此我們需要針對血量加開一個維度，定義 `step[i][j][k]` 代表從 $(1,1)$ 走到 $(i,j)$，且目前已經扣了 $k$ 條血量的情況下，走到 $(n,n)$ 的最短步數。
- 接著就實作 BFS，假如現在要走到的點是 $(x,y)$，若 $(x,y)$ 不是使用快速通道，則 `step[x][y][k] = step[i][j][k] + 1`，反之若是使用快速通道的話，血量會再被多扣 $1$，也就是 `step[x][y][k+1] = step[i][j][k] + 1`
- 最終答案：$\min_{0 \le i < T}\ step[n][n][i]$
- 總時間複雜度：$O(N^2T)$
### Code
- Subtask 1 by Chung
```cpp=
#include<bits/stdc++.h>
using namespace std;
int n,k,t;
int main(){
cin>>n>>k>>t;
int ans = 2*n-2;
for(int i=0;i<k;i++){
int x1,x2,y1,y2;
cin>>x1>>y1>>x2>>y2;
ans = min(ans, (x1+y1-2) + 1 + (n-x2+n-y2));
}
cout<<ans<<"\n";
}
```
- Subtask 2 by Chung
```cpp=
#include<bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
int n,k,t;
map<pii,vector<pii>> mp;
int step[255][255];
int dir[4][2] = {{0,1},{1,0},{-1,0},{0,-1}};
bool inrange(int x,int y){
return x>0 && y>0 && x<=n && y<=n;
}
void bfs(){
queue<pii> q;
q.push({1,1});
step[1][1] = 0;
while(q.size()){
auto [x,y] = q.front(); q.pop();
for(int i=0;i<4;i++){
int nx = x+dir[i][0], ny = y+dir[i][1];
if(!inrange(nx,ny)) continue;
if(step[nx][ny] != -1) continue;
step[nx][ny] = step[x][y] + 1;
q.push({nx,ny});
}
for(auto [nx,ny] : mp[{x,y}]){
if(step[nx][ny] != -1) continue;
step[nx][ny] = step[x][y] + 1;
q.push({nx,ny});
}
}
}
int main(){
cin>>n>>k>>t;
for(int i=0;i<k;i++){
int x1,x2,y1,y2;
cin>>x1>>y1>>x2>>y2;
mp[{x1,y1}].push_back({x2,y2});
}
memset(step,-1,sizeof(step));
bfs();
cout<<step[n][n]<<"\n";
}
```
- Subtask 2 另解 by 橘子
```cpp=
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
struct obj{
ll a,b,c,d;
};
int main(){
ios::sync_with_stdio(0);cin.tie(0);
ll n,k,t;
cin >> n >> k >> t;
vector<obj> a(k);
for(obj &o : a) cin >> o.a >> o.b >> o.c >> o.d;
ll ans = n*2-2;
vector<ll> p(k);
iota(p.begin(),p.end(),0);
do{
ll x = 1,y = 1, c = 0;
for(ll i = 0;i<k;i++){
c += 1+abs(a[p[i]].a-x)+abs(a[p[i]].b-y);
x = a[p[i]].c;
y = a[p[i]].d;
ans = min(ans,c+n*2-x-y);
}
}while(next_permutation(p.begin(),p.end()));
cout << ans << "\n";
}
```
+ Subtask 3 by Chung
```cpp=
#include<bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
int n,k,t;
map<pii,vector<pii>> mp;
int step[255][255][15];
int dir[4][2] = {{0,1},{1,0},{-1,0},{0,-1}};
bool inrange(int x,int y){
return x>0 && y>0 && x<=n && y<=n;
}
void bfs(){
queue<array<int,3>> q;
q.push({1,1,0});
for(int i=0;i<t;i++) step[1][1][i] = 0;
while(q.size()){
auto [x,y,k] = q.front(); q.pop();
if(k == t) continue;
for(int i=0;i<4;i++){
int nx = x+dir[i][0], ny = y+dir[i][1];
if(!inrange(nx,ny)) continue;
if(step[nx][ny][k] != -1) continue;
step[nx][ny][k] = step[x][y][k] + 1;
q.push({nx,ny,k});
}
for(auto [nx,ny] : mp[{x,y}]){
if(step[nx][ny][k+1] != -1) continue;
step[nx][ny][k+1] = step[x][y][k] + 1;
q.push({nx,ny,k+1});
}
}
}
int main(){
cin>>n>>k>>t;
for(int i=0;i<k;i++){
int x1,x2,y1,y2;
cin>>x1>>y1>>x2>>y2;
mp[{x1,y1}].push_back({x2,y2});
}
memset(step,-1,sizeof(step));
bfs();
int mn = 1e18;
for(int i=0;i<t;i++) mn = min(mn, step[n][n][i]);
cout<<mn<<"\n";
}
```
- Python (Subtask 3) by 橘子
```python=
n,k,t = map(int,input().split())
con = [[] for _ in range(n*n)]
for _ in range(k):
a,b,c,d = map(int,input().split())
con[a*n+b-n-1].append(c*n+d-n-1)
dis = [[10000000000]*(n*n) for _ in range(t)]
q = [(0,0,0)]
for o in q:
i,d,c = o
if dis[c][i]<=d:
continue
dis[c][i]=d
if i%n>0:
q.append((i-1,d+1,c))
if i>=n:
q.append((i-n,d+1,c))
if i%n<n-1:
q.append((i+1,d+1,c))
if i<n*n-n:
q.append((i+n,d+1,c))
if c<t-1:
for j in con[i]:
q.append((j,d+1,c+1))
print(min(o[n*n-1] for o in dis))
```
```python!
print((lambda n,k,t:(lambda con,dis,q:sum(con[a*n+b-n-1].append(c*n+d-n-1) or 0 for a,b,c,d in (map(int, input().split()) for _ in range(k))) or sum(dis[c][i]>d and (dis[c].__setitem__(i,d) or i%n and q.append((i-1,d+1,c)) or i>=n and q.append((i-n,d+1,c)) or i%n<n-1 and q.append((i+1,d+1,c)) or i<n*n-n and q.append((i+n,d+1,c)) or c<t-1 and sum(q.append((j,d+1,c+1)) or 0 for j in con[i])) for i,d,c in q) or min(o[n*n-1] for o in dis))([[] for _ in range(n*n)],[[10000000000]*(n*n) for _ in range(t)],[(0,0,0)]))(*map(int,input().split())))
```
Sign in with Wallet
Connect another wallet