# 校內初賽題目

## pA.蛋餅愛函數

### Description
蛋餅是個熱愛函數的建中學生，無論是多項式函數、三角函數、指對數函數，蛋餅都研究得十分透徹。而今天，他發現了一個十分有趣的函數，決定好好研究一番。

這個函數十分的特別，他的輸入只能是一個介於$1$到$N$之間的正整數，而他的輸出也會是一個介於$1$到$N$之間的正整數。更特別的是，任意兩個不一樣的數字代入函數當中，得到的輸出都不相同。

蛋餅最喜歡對函數做一件事，他把這件事稱作「函數的迭代」。具體來說，就是把剛從函數得到的值，再代入函數。一個數對某個函數的「$k$次迭代」就是指將一個數連續代入函數$k$次，所得到的值。舉例來說，蛋餅有個數字叫做$x$，那麼$x$的零次迭代就是$x$，$x$的一次迭代就是$f(x)$，$x$的二次迭代就是$f(f(x))$或記作$f^2(x)$，$x$的三次迭代就是$f(f(f(x)))$或記作$f^3(x)$...以此類推。

蛋餅覺得如果要分析如此複雜的函數，會需要程式的幫助。因此，他想請你幫忙解決以下的問題。蛋餅告訴了你將$1$到$N$依序代入這個函數後所得到的結果，而接下來蛋餅會詢問$Q$次，每次詢問兩個整數$a,b$。你必須回答他，$a$對這個函數迭代$b$次，也就是$f^b(a)$是多少。
### Input Format
輸入的第一行為一個正整數$N$，意義如題目所敘。
接下來一行有$N$個整數，分別代表$f(1),f(2),...,f(N)$。
接下來一行有一個正整數$Q$，表示詢問的次數。
接下來共$Q$行，其中第$i$行有兩個整數$a_i,b_i$，分別表示詢問的$a$與$b$。

對於所有測試資料，保證$N\leq 10^ 5$，$Q\leq 800$，$1\leq a_i\leq N$，$0\leq b_i<N$。
### Output Format
輸出共$Q$行，每一行代表一筆詢問的答案。
### Sample Input
4
2 4 1 3
2
3 2
4 1
### Sample Output
2
3
### Hints
對於範例測資，第一筆詢問$f^2(3)$，也就是$f(f(3))=f(1)=2$，所以輸出$2$。第二筆詢問$f^1(4)=f(4)=3$，所以輸出$3$。

這題輸入輸出量很大，建議在main函式開頭加入`ios_base::sync_with_stdio(0);cin.tie(0);`
或使用`scanf`/`printf`，並且記得在輸出換行時使用`'\n'`。
### Problem Source
110學年度建國中學校內資訊能力競賽初試pA
### Subtasks
1. $N\leq 100$，$Q\leq 40$。 (70%)
2. 無特別限制。 (30%)
### Notes
「蛋餅好軟。」—FHVirus

## pB.與眾不同

### Description
最近各種DIY的小型吊飾十分熱門，不只可以讓人享受手作的樂趣，還能自己挑選喜歡的款式，因而受到大眾的喜愛。而你與你的$k$個好朋友，也受到這股潮流的影響，想要一起製作屬於自己的裝飾品。經過一番挑選，你們選擇了一種有$N$個珠子排成一列的吊飾，來進行製作。

珠子一共有兩種型態，一種是圓形，而另一種是方形。將這些珠子以任意的順序排成一列，再把他們小心的串在一起，就完成屬於自己的吊飾了。

你的$k$個朋友們依序完成了自己的吊飾，而當你也準備開始製作時，突然想到：「我的吊飾必須『與眾不同』!」對於兩串吊飾$A$、$B$，定義他們的「相異度」為兩串吊飾有多少個位置的珠子種類不同。例如一個順序為「圓、圓、方、圓、方」的吊飾與一個順序為「圓、方、方、圓、圓」的吊飾，他們的「相異度」為$2$。

你希望你最後製作出的吊飾，與其他$k$個朋友的吊飾的「相異度」的最小值，可以越大越好。請輸出任意一個合法的吊飾，使它與其他$k$個吊飾的「相異度」最小值最大。
### Input Format
輸入的第一行有兩個整數$N,k$，表示吊飾的珠子個數與朋友的數目。
接下來共$k$行，第$i$行有一個長度為$N$的01字串$S_i$，表示第$i$位朋友製作的吊飾（0代表圓形的珠子，1代表方型的珠子）。

對於所有測試資料，保證$1\leq N\leq 10^5$，$1\leq k\leq 3$。
### Output Format
輸出一個長度為$N$的01字串$S$，表示滿足與其他$k$個吊飾的「相異度」最小值最大的吊飾。若有多組合法的解，輸出任意一組皆可。
### Sample Input
5 2
00101
01100
### Sample Output
10010
### Hints
以範測為例，字串"10010"與"00101"、"01100"的「相異度」皆為$4$，因此最小值為$4$，是所有可能性中最大的，符合要求。除此之外，字串"11011"也符合要求，其餘字串皆不符合要求。
### Problem Source
110學年度建國中學校內資訊能力競賽初試pB
### Subtasks
1. $n \leq 15$。 (15%)
2. $k \leq 2$。 (49%)
3. 無其他限制。 (36%)
### Notes
「競程是一句謊言、一種假象。」—8e7

> 總覺得49分比15分好拿XDD

## pC.走夜路小心遇到鬼，還有女高中生

### Description
你是一個任職於大型資訊科技公司的上班族，今年26歲。回想起高中時第一次參加資訊競賽，進而點亮了自己對資訊領域的興趣。如今擁有了一份穩定的工作，生活也還算優渥，可說是十年來努力不懈的成果。

不過這看似完美的人生也有不幸的時刻。前些時日，你向你單戀多年的女性上司告白，卻被狠狠地拒絕掉了。為了排遣這鬱悶的情緒，你在下班後約了你的同事出來喝酒，將積累的怨氣好好發洩一番。

而現在，你正走在回家的路上，然而醉意未消的你，看著平常再熟悉不過的街道，竟然出現了十分詭異的變化。許多類似鬼魅的生物憑空出現，對你露出猙獰的面孔。

你現在所位於的街區可以看做是一個$N\times M$的二維平面，你的初始位置是$(1,1)$，而你的家位於$(N,M)$。每一步你可以選擇往上、下、左、右移動，但因為你喝醉了，難以控制步伐，因此只能選擇一步前進$p$或$q$單位長的距離才能停下。你可以在街區內自由移動，但任何往街區外的移動都是不允許的。然而，街區內的某些格子點（即座標為整數的位置）已經被鬼佔領了，你可以在一步之內穿過鬼，但是你不能停留在有鬼的位置上，否則鬼會被驚動然後把你...（以下畫面請自行想像）。只要你停留在你家的位置上，就可以安全回到家。

不過故事還沒結束。你看到了街區位於$(x,y)$的位置，蹲坐著一位似乎是同樣看見可怕的鬼魂，而被嚇得六神無主的女高中生。你心想著一定要把這個女高中生帶回家，讓她免於鬼魅的驚嚇。之後她說不定會心存感激，然後之後你不管想跟她搞或是想讓她煮味噌湯給你喝都可以如願以償（咦）。不過想要把她帶回家，就一定要在與女高中生相同的位置停下才行。順帶一提，女高中生也是可以在一步之內穿過的，至於怎麼穿過就不好說了。

由於鬼實在是很可怕，你想要盡快的安全回到家，但又不能丟下女高中生不管。因此你想要知道，從目前位置出發，依照題目所述的行動方式，經過女高中生，最後安全回到家，所需的最少步數是多少，或是回報無法達成。
### Input Format
輸入的第一行有兩個正整數$N,M$，代表街區的長與寬。
接下來一行有兩個非負整數$p,q$，代表每次可以選擇的步數長度。
接下來一行兩個正整數$x,y$，表示女高中生的位置座標。
接下來共$N$行，每行有$M$個整數，對於第$i$行第$j$個整數$a_{ij}$，
* 若$a_{ij}=0$，表示位置$(i,j)$是安全的，可以停留。
* 若$a_{ij}=1$，表示位置$(i,j)$被鬼佔領，不可停留。

保證起始位置、終點位置、女高中生的位置都是安全的。

對於所有測試資料，保證$N,M\leq 1000$，$p,q< min(N,M)$，$1\leq x\leq N$，$1\leq y\leq M$，$a_{ij}\in \{0,1\}$對於所有$1\leq i\leq N,1\leq j\leq M$。
### Output Format
輸出一個整數，表示與女高中生一同回家所需的最少步數。若無法達成，請輸出$-1$。
### Sample Input
6 5
2 3
3 4
0 0 1 0 0
0 0 1 0 0
1 0 1 0 1
1 1 1 1 0
1 0 0 0 0
0 0 0 1 0
### Sample Output
5
### Hints
範測的圖像化結果如下：
一個合法的最短路徑為$(1,1)$->$(1,4)$->$(3,4)$->$(3,2)$->$(6,2)$->$(6,5)$，其長度為$5$。
### Problem Source
110學年度建國中學校內資訊能力競賽初試pC
### Subtasks
1. $N,M\leq 6$。 (16%)
2. $a_{ij}=0$對於所有$1\leq i\leq N,1\leq j\leq M$。 (17%)
3. $p=q=1$。 (18%)
4. 無特別限制。 (49%)
### Notes
「或許人世間的那些邂逅，都是建立在這種奇妙的平衡上的吧。」—醋青魚

> 跪求更好的圖示範例
後記：你下一秒就發現了，這些鬼只不過是你喝醉後所看見的幻影而已。不過出乎意料的，那位女高中生並不是幻影，是真的存在。然後之後的劇情大家都知道了，不知道的可以參考[這篇文章](https://w.linovelib.com/novel/2428.html)
Osu!上超多這部的OP和ED 打爆vivy和86 WTF
希望題目不會油到出事

> 9/1 update: 是的我又把很糟糕的東西放回來了爽啦
> 9/12 update: 那個說要加「因為奇葩的理由」的是在暴雷吧，8e7你很會喔

## pD.DZ的因數遊戲

### Description
`Danb`與`Zisk`是資訊奧林匹亞的國手，除了在程式競賽上決勝負之外，平常的他們也會玩各種遊戲以互相較勁。

今天`Danb`與`Zisk`在玩一個與因數有關的遊戲。遊戲一開始他們在白板上寫下兩個正整數$x, y$，接著雙方會輪流進行操作。每次操作會選目前比較大的數字$c$，接著他們會擦掉$c$，並寫下任何一個小於$c$的因數（即寫下的數字$d$必須整除$c$且$d < c$）。`Danb`為先手，而當某位玩家無法在進行操作時，那位玩家就輸了。

因為`Danb`和`Zisk`都絕頂聰明，因此他們一定會用最佳策略玩此遊戲。但即使如此，最終仍然有人會勝出，而你想知道誰會是勝出的人。
### Input Format
第一行輸入一個正整數$t$，代表`Danb`跟 `Zisk` 玩了多少場遊戲。
接下來每行有兩個正整數$x, y$，代表一場遊戲一開始寫下的數字。

對於所有測資，$t \leq 10$，$x, y \leq 10^8$，且單筆測資裡面所有$x, y$的總和不會超過$2\times10^8$。
### Output Format
輸出$t$行，第$i$行表示對於第$i$場遊戲，如果`Danb`有必勝策略輸出"Danb"，如果`Zisk`有必勝策略輸出"Zisk"(不含引號)。
### Sample Input
2
3 4
1 1
### Sample Output
Danb
Zisk
### Hints
以範測為例，第一場對局中，`Danb`可以把$4$改成$2$，而`Zisk`只能把$3$改成$1$，於是`Danb`把$2$改成$1$，`Zisk`無法行動，`Danb`勝。而第二場對局中，`Danb`一開始就無法行動，因此`Zisk`勝。
### Problem Source
110學年度建國中學校內資訊能力競賽初試pD
### Subtasks
1. $x = 1$。 (4%)
2. $x$整除$y$。 (5%)
3. $x$ 是質數。 (11%)
4. $x, y \leq 1000$ (13%)
5. $x, y \leq 10^6$ (28%)
6. 無其他限制 (39%)
### Notes
「你會遭天譴。」—Zisk

## pE.買分

### Description
植物園高級中學是全國首屈一指的名校，其設立目的旨在培育肩負國家未來的重要人才。而這所中學的畢業生，無論是升學或是就業均有受到保障，要進入頂尖的大學或企業都易如反掌。

然而由於是高手的聚集地，這所學校內部的競爭壓力也是高的驚人。尤其這所學校有中途退學的機制，想要在這裡安然無事的度過三年畢業，可說是難如登天。

你是植物園高級中學的學生之一，而學校剛舉行了第一次的定期考試。這個考試有個特殊的規定，那就是只要一個學生有任何一個科目不及格，那麼他就得接受中途退學的懲罰。及格的定義是該科全班成績平均值的一半。

你的班上有$N$位同學（包含你），編號為$1$到$N$，進行了一場總分為$C$分的定期考試，所有人的分數皆為$0$到$C$之間的整數。等到考試的成績一揭曉，就可能有人必須退學。

不過神通廣大的你，在分數正式公布前，早已事先得知了全班每個人的成績，其中第$i$號的人成績為$s_i$。而且根據你所知道的消息，在這所學校裡，有十萬零八千種以上的方法，可以讓一個人的分數上升或下降。當然，這麼做必須付出一定的代價，而且每個人的代價也不盡相同。根據你的資料，對於第$i$個人，使他的成績每上升一分，就必須付出$a_i$的代價，而使他的成績每下降一分，就必須付出$b_i$的代價。不過每個人的成績最後都必須落在$0$到$C$分之間，否則是不合法的。

你希望使全班的所有同學都度過這次的定期考試，但又不希望付出太多代價。求欲使所有人皆及格所需付出的代價最小值是多少。
### Input format
輸入的第一行有兩個整數$N,C$，分別表示全班的總人數以及考試的總分。
接下來一行有$N$個整數$s_1,s_2,...,s_N$，$s_i$表示第$i$個人的分數。
接下來一行有$N$個整數$a_1,a_2,...,a_N$，$a_i$表示使第$i$個人的分數上升一分所需的代價。
接下來一行有$N$個整數$b_1,b_2,...,b_N$，$b_i$表示使第$i$個人的分數下降一分所需的代價。

對於所有測試資料，保證$1\leq N\leq 10^5$，$1\leq C\leq 5\times10^8$，$0\leq s_i\leq C$，$1\leq a_i,b_i\leq 10^5$。
### Output Format
輸出一個整數，表示使全班及格所需的最小花費。
### Sample Input
3 100
20 100 80
6 5 4
3 2 1
### Sample Output
85
### Hints
對於範例測資，代價最小的方案如下：將第一個人提高$5$分，並將第三個人降低$55$分，所需代價為$5\times 6+55\times 1=85$。
### Problem Source
110學年度建國中學校內資訊能力競賽初試pE
### Subtasks
1. $N,C\leq 100$。 (10%)
2. $N,C\leq 1000$。 (16%)
3. $C\leq 5\times 10^ 5$。 (29%)
4. 無特別限制。 (45%)
### Notes
「這世界一點也不平等。」—衣笠彰梧

> 要不要來個$N\leq 25$和$N\leq 40$致敬原作XDD