# NPSC 高中
## 2022
https://contest.cc.ntu.edu.tw/npsc2022/teamclient/pre-sen.pdf
初賽
https://contest.cc.ntu.edu.tw/npsc2022/teamclient/final-sen.pdf
決賽
## 2021
https://contest.cc.ntu.edu.tw/npsc2021/teamclient/contest_senior.pdf
(2021沒有初賽只有決賽)
## 2020
https://contest.cc.ntu.edu.tw/npsc2020/teamclient/semi_senior.pdf
初賽
https://contest.cc.ntu.edu.tw/npsc2020/teamclient/final-senior.pdf
決賽
## 2019
https://contest.cc.ntu.edu.tw/npsc2019/teamclient/semi_senior.pdf
初賽
https://contest.cc.ntu.edu.tw/npsc2019/teamclient/final-senior.pdf
決賽
## 2018
https://contest.cc.ntu.edu.tw/npsc2018/teamclient/semi_senior.pdf
初賽
https://contest.cc.ntu.edu.tw/npsc2018/teamclient/final-senior.pdf
決賽
## 2017
https://contest.cc.ntu.edu.tw/npsc2017/teamclient/pre-senior.pdf
初賽
https://contest.cc.ntu.edu.tw/npsc2017/senior.pdf
決賽
## 2016
https://contest.cc.ntu.edu.tw/npsc2016/teamclient/pre-senior-statement.pdf
初賽
https://contest.cc.ntu.edu.tw/npsc2016/teamclient/final-senior.pdf
決賽
## 2015
https://contest.cc.ntu.edu.tw/npsc2015/teamclient/Preliminary/senior.pdf
初賽
https://contest.cc.ntu.edu.tw/npsc2015/schedule.asp
決賽( 決賽題目在檔案裡 )
## 2014
https://contest.cc.ntu.edu.tw/npsc2014/teamclient/Senior-Preliminary/problem.pdf
初賽
https://contest.cc.ntu.edu.tw/npsc2014/schedule.asp
決賽( 決賽題目在檔案裡 )
## 2013
https://contest.cc.ntu.edu.tw/npsc2013/teamclient/npsc2013senior.pdf
初賽
https://contest.cc.ntu.edu.tw/npsc2013/final/Senior-Final/npsc2013senior.pdf
決賽
## 2012
https://contest.cc.ntu.edu.tw/npsc2012/teamclient/npsc2012senior.pdf
初賽
https://contest.cc.ntu.edu.tw/npsc2012/teamclient/NPSC2012senFinal.pdf
決賽
## 2011
https://contest.cc.ntu.edu.tw/npsc2011/teamclient/2011_Senior_first.pdf
初賽
https://contest.cc.ntu.edu.tw/npsc2020/problem.html
決賽( 決賽題目在檔案裡，向下滑至2011年 )
## 2010
https://contest.cc.ntu.edu.tw/npsc2010/teamclient/2010sens.pdf
初賽
決賽( 找不到，好像只有比賽的人可以看 )
## 2009
https://contest.cc.ntu.edu.tw/npsc2009/2009sen.pdf
初賽
https://contest.cc.ntu.edu.tw/npsc2009/finalContest/senior_final.pdf
決賽
## 2008
https://contest.cc.ntu.edu.tw/npsc2008/2008sen.pdf
初賽
https://contest.cc.ntu.edu.tw/npsc2008/2008sen_final.pdf
決賽( 決賽題目在檔案裡，向下滑至2008年 )
## 2007
https://contest.cc.ntu.edu.tw/npsc2020/problem.html
初賽&決賽( 向下滑至2007，為word檔 )
## 2006
https://contest.cc.ntu.edu.tw/npsc2020/problem.html
初賽&決賽( 向下滑至2006，為word檔 )
## 2005
https://contest.cc.ntu.edu.tw/npsc2020/problem.html
初賽&決賽( 向下滑至2005，為word檔，決賽題目為檔案 )
## 2004
https://contest.cc.ntu.edu.tw/npsc2020/problem.html
初賽&決賽( 題目在檔案裡，向下滑至2004年 )
## 2003
https://contest.cc.ntu.edu.tw/npsc2020/problem.html
初賽&決賽( 題目在檔案裡，向下滑至2003年 )
## 2001
https://contest.cc.ntu.edu.tw/npsc2020/problem.html
初賽&決賽( 題目在檔案裡，向下滑至2001年 )

---

# 2022 網際網路程式設計全國大賽 初賽

## A.巫醫巫醫畫畫畫畫
Problem ID: paintex
巫醫巫醫是個傳奇人物，聽說他遇到很困難的問題的時候，都只要喊一聲咒語巫醫巫醫殿
殿殿，問題就會被解決！於是，小 Y 給了他一個挑戰。
有一個 N × N 的地圖，上面充滿了危險，在這個地圖上面有四種土地：
1. 劇毒之地，上面充滿了恐怖的毒氣，任何人只要一走到這塊地就會立刻死掉。
2. 人人之地，上面有一個無辜的人，想要趕快回家。
3. 超級傳送門，可憐的人只要走上來就會被傳送出這個危險的地圖。
4. 安全之地，原本是劇毒之地，經過巫醫巫醫的法術之後，變成可以行走的地方。
而這個地圖是四連通的，也就是說無辜的人可以從座標 (i, j) 走到以下四個座標：
1. (i + 1, j)
2. (i − 1, j)
3. (i, j + 1)
4. (i, j − 1)
而在地圖之外，全部都是可怕的無底洞，所以你只要走到一個超出範圍的座標 (x, y) 滿足
x /∈ [1, N] 或 y /∈ [1, N] 那你就會立刻掉下去摔死。註：n /∈ [1, N] 表示 n < 1 或 n > N。
為了拯救無辜的人，巫醫巫醫必須施展法術，每次施展法術都只能把一個劇毒之地的毒氣
消除，變成安全之地，讓人可以安全的走在這塊地上。巫醫巫醫希望在施展法術過後，每個無
辜的人，都可以不經過劇毒之地，走到超級傳送門。
但是巫醫巫醫的法術能量有限，他最多只能施展 2 · 106 次法術，請你幫他決定好要在哪些
地方施法術，才能夠讓所有無辜的人都能夠安全抵達超級傳送門。
以下為範測說明，深藍的格子是劇毒之地，天藍色的格子是人人之地，黃色的格子是超級
傳送門，紫色的格子是安全之地。


Input
輸入的第一行有一個正整數 N。
接下來 N 行，每行都有一個長度為 N 的字串 Si ，其中 Si,j 代表地圖上座標 (i, j) 的土地
類型。
• 1 ≤ N ≤ 4 × 103
• Si,j ∈ {., P, X}，其中 . P X 分別代表劇毒之地、人人之地和超級傳送門
• 保證只有 S1,1 = X，且 S1,1 = X
• 最多只會有 2 · 105 個人人之地

Output
請輸出 N 行，每一行一個長度為 N 的字串 S
′
i 代表施展過法術之後的地圖。字元 O 代表有
施展法術的土地，其他規則和輸入一樣。如果你的地圖上面有超過 2 · 106 個土地被施展法術、
有土地被不合法的施展法術、或是有一個未被施展法術的土地與原本不同，那你會得到 Wrong
Answer 的結果。注意到如果有多組解，任意一組都會得到 Accepted。


解答

---

## B.北極熊大接龍
Problem ID: chaingame
因為全球暖化的關係，北極各處的浮冰正在慢慢融化之中。部份北極熊所在的浮冰已經融
化到不堪居住的程度，於是這些北極熊興起遷徙的念頭。
為了拯救處境水深火熱的北極熊們，ㄅㄅ與ㄒㄒ，兩個喜歡收集世界各地的冷笑話的冒險
家，正在用越冷越好的冷笑話來減緩全球暖化。
所有笑話裡，ㄅㄅ與ㄒㄒ最喜歡的冷笑話就是所謂的接龍式笑話了。在這類的笑話當中，
ㄅㄅ或ㄒㄒ會在對話當中隨機說一個詞，而這個詞的開頭要剛好跟前一刻的詞結尾完全一樣，
或者至少有諧音。這種完全沒有上下文、只是說一個能夠接龍的詞的笑話讓ㄅㄅ和ㄒㄒ認為這
是最能有效減緩全球暖化的冷笑話。
由於對於接龍式笑話的專精，ㄅㄅ和ㄒㄒ以及其他愛好者制定了一種量化這種笑話厲不厲
害的標準。具體來說，假設ㄅㄅ講了一個字串 S，而ㄒㄒ以一個字串 T 作為回應。如果沒有任
何 T 的前綴同時也是 S 的後綴，即 suf(S) ∩ pre(T) = ∅，表示ㄒㄒ用 T 回應是完全沒有道理
的。否則，這個回應的分數就是


其中 suf(S) 表示 S 的一個後綴，即保留 S 中最後面連續非零個字元所形成的字串集合；而
pre(T) 代表 T 的一段前綴，即保留 T 中最前面連續非零個字元所形成的字串集合。
註：|Y | 表示一個字串 Y 的長度。
舉例而言，若 S = ababaaba、T = abaabac，那麼：
• suf(S) = {ababaaba, babaaba, abaaba, baaba, aaba, aba, ba, a}。
• pre(T) = {a, ab, aba, abaa, abaab, abaaba, abaabac}。
因此，他們的交集，也就是 suf(S) ∩ pre(T) = {a, aba, abaaba}，可得到該回應的分數
為 max{min(1, 7 − 1), min(3, 7 − 3), min(6, 7 − 6)} = max{1, 3, 1} = 3。
現在，ㄅㄅ剛剛在聊天時講到一個字串 S，而ㄒㄒ覺得這是一個說接龍式笑話的好機會，
於是ㄒㄒ想到了 N 個可能很好笑的詞 Ti，但他不知道，哪些詞會讓回應的分數最高，因此ㄒ
ㄒ想請教你，對於每個字串 Ti，Ti 是否是一個有道理的回應，以及用 Ti 回應 S 的分數是多少。
7
2022 — 網際網路程式設計全國大賽 高中組初賽
Input
輸入第一行有一個由小寫英文字母構成的字串 S，緊接著第二行有一個正整數 N。接下來
的 N 行，每行有一個由小寫字母構成的字串 Ti。

Output
輸出 N 行，如果用 Ti 回應 S 是沒有道理的，請你在第 i 行輸出一行 −1，否則第 i 行請輸
出一行非負整數表示 Ti 回應 S 的分數。


解答

---

## C.螢石眼之歌
Problem ID: vivy
Vivy 是一個歌姬 AI，她的原本的使命是用歌聲讓大家幸福，可是從未來回到現在的超級
AI——松本告訴 Vivy 如果現在不幫他處理某些事情，則一百年後的未來就一定爆發 AI 戰爭。
此時擺在 Vivy 眼前的是 N 顆石頭排成一直線，其中第 i 顆石頭上面寫著一個介於 1 到 N
的正整數 pi，而且兩兩不重複。松本告訴她，當這排石頭越美麗，百年後戰爭發生的機率就越
小。
對於長度都是 N 的兩排石頭 A, B，令 Ai
, Bi 分別代表 A 這排第 i 個石頭上的數字，和 B
這排第 i 個石頭上的數字。A 這排石頭比較美麗若且唯若存在一個 k 使得 Ak < Bk，而且所有k′
(1 ≤ k′ < k) 都滿足 Ak′ = Bk′。
見過未來的松本告訴 Vivy 他們總共有 N − K + 1 次機會改變石頭上的數字，其中 K 是一
個已知的正整數。
對於第 i 次機會，他們可以決定兩個正整數 X, Y (i ≤ X, Y < i + K) 並將第 X 個石頭和第
Y 個石頭上面的數字交換，特別的，如果 X = Y ，則可以視為沒有數字交換。
Vivy 不想要做白工，所以她希望能先知道最後這排石頭最美麗的樣子能夠是什麼？請你
幫 Vivy 推算出來。


解答

---

## D.社交能量
Problem ID: segments
德田館地下室是一個適合學生社交的場所，許多學生會在空堂時聚集在一起寫作業、玩遊
戲、膜拜或裝弱。然而，每個學生會出現在系館的時間並不一致，第 i 個學生會在第 li 單位時
間時抵達德田館地下室，並在第 ri 單位時間時離開。
身為一位數學家，AT7 觀察到如果兩個同學同時待在德田館地下室 k 單位時間的話，就會
產生 k 單位的社交能量。因此，N 位同學在德田館地下室所產生的總社交能量，就是把這 N
位同學兩兩取出來計算他們產生的社交能量，再加總起來。
為了假裝自己不會數學，AT7 委託你寫一個程式計算 N 位同學在德田館地下室所產生的
總社交能量。你能完成這項任務嗎？
解答

---

## E.蛋餅愛爬山
Problem ID: mountain
蛋餅是一個愛爬山的蛋餅，擅長爬山的蛋餅今年成功入選了全國爬山大賽（National Pa
Shan Contest，簡稱 NPSC）決賽。今年的 NPSC 決賽在象大山舉辦，參賽者必須沿著一條指
定的路線前進。
這條路線是一條直線前進的路線，包含 N 個路段，每個路段的水平長度都是 1 公尺，每
個路段的坡度剛好都是 45◦ 往上或往下。也就是說，如果第 i 個路段是一段往上的路段，那麼
它的左端點高度比右端點高度少 1，反之就多 1。路段的兩端點高度都是 0。
蛋餅可以花費一單位的力氣，移動到上一個路段或下一個路段（如果他不會移動到路線外
的話）。不過，長年連霸 NPSC 冠軍的蛋餅有一個特殊技能：他可以穿越一座山丘。也就是說，
他可以鑽進目前所在路段的地面，維持相同的高度，移動到山丘另一邊的路段去。使用一次技
能也要花費一單位的力氣。
聽起來蛋餅只要從路段的起點不斷使用技能，就可以到達路段的終點了。不過，NPSC 才
沒有那麼簡單！比賽開始時，參賽者會統一被送到起點路段，目標是移動到終點路段，起終點
路段則在比賽開始時才會公布。幸運的是，蛋餅有預知未來的能力：他知道起終點路段有 Q 種
可能性，第 i 種可能性的起點路段是 si、終點是 ti。蛋餅想要知道在每一種可能的狀況中，他
要花多少力氣才能完成比賽。
舉例來說，N = 12，而這 12 個路段分別是「上上下上上上下下上下下下」，而 Q = 3，這
3 種狀況的 (si
, ti) 分別是 (1, 11)、(9, 4)、(5, 5)，蛋餅的最佳路線如下圖：
三種狀況分別需要花費 2, 3, 0 的力氣。
解答

---
## F.取蜜柑
Problem ID: mikan
話說身為魔族的夏美子（シャミ子）為了打贏魔法少女千代田桃（ちよだもも，以下暱稱
小桃）來解除家裡的封印，每天都向魔法少女挑戰。在經過數場激烈的戰鬥後，她發現靠力氣
無法打贏怪力魔法少女，於是她今天準備了一堆箱子與蜜柑，向小桃提出一個遊戲作為今天挑
戰的內容。遊戲的內容如下：
• 一開始夏美子會準備 N 個箱子，並在第 i 個箱子內放入 ai 顆蜜柑，放完之後將所有箱子
關起來。
• 由夏美子開始，雙方輪流進行取蜜柑的動作。該動作會分為兩個步驟，第一步為挑選一
個箱子，第二步為將該箱子打開，取出任意正整數顆蜜柑後再將它關起來。若該箱子變
成空的就將此箱子從遊戲中移除。
• 若輪到的一方已經沒有箱子可以選了，則該玩家就是輸家。
聽完遊戲規則後，小桃覺得這樣的遊戲太無聊了。為了增加遊戲的有趣程度，她決定在每
次雙方取蜜柑前都召喚出強大的風將箱子的順序隨機吹散。因為每個關起來的箱子外表都一
樣，而且風的速度太快了，她們無法記得每個箱子移動到哪裡，因此她們每次操作的第一步只
能等機率隨機選擇一個箱子，再決定要取出多少蜜柑。
舉例來說，若目前場上還剩下 3 個箱子，分別有 1, 2, 4 顆蜜柑。那下一位玩家有 1
3 的機率
必須從有 1 顆蜜柑的箱子取蜜柑，有 1
3 的機率必須從有 2 顆蜜柑的箱子取蜜柑，有 1
3 的機率必
須從有 4 顆蜜柑的箱子取蜜柑。
突如其來的變化讓夏美子慌了，她想請你幫她計算如果她和小桃都使用最佳策略遊玩這遊
戲的情況下，她獲勝的機率是多少？
你可以假設她們的記性都很好，就算箱子是關起來的，她們也會隨時記得現在箱子內的蜜
柑數量所形成的多重集合。你也可以假設箱子被關得非常緊，風不會讓箱子變成打開的，更不
會把箱子內的蜜柑吹出來。
解答

---
## G.堆疊遊戲
Problem ID: stackgame
edison 只要看到網路上的手遊廣告就會載下來試玩看看，堆疊遊戲也不例外。堆疊遊戲
的規則非常簡單，那就是玩家會拿到若干個裝著一堆整數的堆疊，並且持有一個計數器從初始
值 0 開始，每次挑選一個堆疊將其頂端的數字拿出來加進計數器內，只要能夠完整將所有數字
拿出來，並滿足過程中計數器的值都非負，就算是完成一個關卡。
喜歡自我挑戰的 edison 覺得這款遊戲似乎有些容易，因此他決定給自己加上一個條件：
遊戲過程計數器值出現過的最大值必須最小。
在這個限制下，遊戲似乎就無法簡單的在 edison 腦海內模擬了，因此他希望能夠事先知
道這個「最小的最大值」可以多小，好讓自己能夠知道有沒有因為自己訂下的規則輸掉。
由於這個問題難度有點高，因此 edison 請你先幫忙處理兩個堆疊的情況就好，舉例而言，
假設兩個堆疊的大小分別是 3 和 4，並且第一個堆疊內的整數由上到下依序是 [3, 1, −4]，第二
個堆疊內的整數由上到下依序是 [1, −5, 9, 2]，edison 可以照著「一一二二二一二」的順序依序
從對應的堆疊拿出數字加進計數器內，這樣會滿足計數器的數字依序為「3, 4, 5, 0, 9, 5, 7」，過
程都非負，過程的最大值是 9；當然，edison 也可以照著「一一二二二二一」的順序拿數字，
但這樣計數器的數字依序會為「3, 4, 5, 0, 9, 11, 7」，儘管過程非負，但過程的最大值是 11，並不
符合 edison 給自己的限制。
請你撰寫一支程式在讀入兩個堆疊內的整數後，輸出計數器初始值從 0 開始後完整將所有
數字拿出來的過程中，在滿足計數器的數值總是非負的情況下，過程最大值最小可以是多小。


解答

---

# 2022 網際網路程式設計全國大賽 決賽
## A.雅量
Problem ID: generosity
朋友出了一場模擬比賽，沒用的範例帶冗長的敘述。當她拿給我們看時，一位對手速十分
感興趣的同學說：
「啊，好像 Codeforces 似的。」
「我看倒有點像唬爛大賽。」我說。
「真像一題題 IMO 。」一位外號叫「方格王」的同學緊接著說。
我們不禁哄堂大笑，同樣的一場比賽，每個人卻有不同的感覺。那位朋友連忙把題本用紙
袋裝好，她覺得模擬比賽就是模擬比賽，不是 Codeforces ，也不是唬爛大賽，更不是 IMO 。
現在，給你兩個正整數 N, M ，請求出 除以 M 的餘數。

解答

---
## B.選巫醫巫醫
Problem ID: absolute
你知道嘛，巫醫巫醫為了選繼承人，每四年就會舉辦一次巫醫巫醫爭奪戰，要讓最強衛冕
者拿到傳奇巫醫巫醫的頭銜。
總共有 N 名參賽者，編號從 1 到 N ，其中編號為 i 的參賽者的巫力為 ai，他們即將在象
大山的女神競技場打架。
比賽的方法如下：
每次由巫醫巫醫指定兩個尚未被打敗的參賽者去打架，並淘汰掉打輸的參賽者。
當兩名參賽者打架，擁有比較多巫力的參賽者獲勝（如果兩個參賽者巫力一樣，編號比較
小的參賽者獲勝）。令 x, y 分別是勝者及敗者的編號，在打架完畢後 x 的巫力會被 y 給消耗。
更精確的來說 ax 會變成 ax − ay。
經過 N − 1 場打架之後，沒有輸過的參賽者會成為新一代巫醫巫醫，但是因為經過很多
消耗，這位參賽者的巫力可能大不如前，現在巫醫巫醫希望新一代巫醫巫醫能夠擁有最大的巫
力，請你告訴巫醫巫醫怎麼樣安排比賽最好。
解答

---

## 後面慢慢自己做出來
## 把所有年度都這樣整理
## 你可以分不同年度各做一個hackMD
## 也可以都在一起之後做書籤之類的
## 這樣子答案放在下面你自己要複習要看也比較好看