【測驗M17】 2004網際網路程式設計全國大賽高中組-初賽題目 [回前頁]
題目A 迴文數目
輸入檔: pa.in /輸出檔: pa.out
所謂的「迴文」，就是指一個字串從頭開始唸跟倒著唸結果完全一樣。例如abccaaccba就是一個迴文字。
而所謂的「全排列」，則是指一個字串裡的每個字母在經過順序的調換以後所能得到的各種排列。例如abcd的全排列就是：
abcd abdc acbd acdb adbc adcb
bacd badc bcad bcda bdac bdca
cabd cadb cbad cbda cdab cdba
dabc dacb dbac dbca dcab dcba
請寫出一個程式，對於輸入的字串，算出在這個字串的全排列裡有多少個是迴文。例如aabb的全排列為：
aabb abab abba baab baba bbaa
其中abba和baab是迴文，因此aabb的全排列裡有2個迴文。
輸入檔說明：
輸入檔第一行是一個整數 N (1 ≤ N ≤ 50) 代表題目的數目。接下來N行輸入，每一行會有一個長度不超過40的字串，這個字串會完全由小寫的英文字母構成。﹝字串的長度最少是1﹞
輸出檔說明：
對每一行字串，請在每行輸出這個字串的全排列裡有幾個迴文﹝如果全排列裡一個迴文都沒有的話，就輸出0﹞。輸出的數字不會超過integer的大小。
範例輸入：
3
aabb
a
abc
範例輸出:
2
1
0
題目B 骨牌遊戲
輸入檔: pb.in /輸出檔: pb.out
骨牌是一片片長方形的塑膠牌,可以將它立起來排成你想要的圖案,加上骨牌本身會有顏色的變化,所以在壓下骨牌後,骨牌一塊塊倒下,就可以展現出美麗的圖案.但是在排骨牌的過程中,常常會有不小心壓到的時候,導致辛苦的結果都不見了.所以有人發明了一種很重的骨牌,在必要的地方把關,防止在你不小心壓下骨牌後,造成的結果會很慘,因為它有足夠的重量,不會倒下,讓傷害停在這裡.
然而我們所擁有的很重骨牌只有幾個,只能在真的非常重要的地方把關,每一個地方會用一個正整數(cost)表示,定義為它排好所需的時間,需要越長,代表重排也要越久,也就越重要.於是我們必須善用這些很重的骨牌,讓傷害降到最小,我們將最大傷害強度定義為,碰倒任一張骨牌之後(可能向前倒或向後倒),可能需要重排的cost總和的最大值.
輸入檔說明：
w個很重的骨牌,n條排好的骨牌列,每一列的cost按照順序排好,形式如下
n w
s1 s2 ... sn
也許會有很多組,讀到w和n都是0的時候結束,不需對這一組做輸出
(w和n和s1,s2 ... sn都為小於1001的正整數)
輸出檔說明：
min
min為在你安排好很重骨牌的位置後,讓最大傷害強度降到最低的值
範例輸入：
3 1
2 3 5
0 0
範例輸出:
5
說明
由於3 1那一組可以將一個很重的骨牌放在 2 前, 2 3間, 3 5間, 5後,其中2前的最大傷害強度為10 , 2 3間的最大傷害強度為 8 , 3 5間的最大傷害強度為5 , 5後的最大傷害強度為10,所以把重骨牌放在3 5間做保護會得到最好的結果min(10,8,5,10)=5,因此最後min為5
題目C 張貼廣告
輸入檔: pc.in /輸出檔: pc.out
從台大旁邊的麥當勞走進台大, 不經意地往道路旁邊看, 你會發現有好多好多的廣告: 有的是社團招生, 有的是學生會會長競選的廣告, 有些是家教徵人或是宿舍出租的廣告. 在某些角落, 它們沒有管理得很好, 新貼廣告的人, 不一定會把舊的廣告撕下來, 所以映入你眼簾的, 就是層層疊疊附在牆上的廣告單張, 遠看這各色重疊的廣告, 再加上點藝術眼光來看, 還不錯看呢!
你實在太無聊了, 所以你現在想寫一個程式來模擬這個圖樣, 把你的螢幕當作廣告牆, 貼一貼廣告來瞧瞧.
輸入檔說明：
輸入資料的第一行是一個正整數 C, 表示接下來有 C 個廣告牆的描述. 每個廣告牆的描述的第一行有三個正整數 H, W 和 N. H 表示廣告牆的高度, W 表示寬度, H 和 W 都不會超過 100. N 表示他要貼 N 張廣告, N 也不會超過 100. 接下來會有 N 行, 每行表示一張廣告. 這 N 行裡, 每行有四個正整數和一個英文字母, 都會用一個空白隔開. 四個正整數分別是這張廣告的左邊, 上邊, 右邊, 下邊的位置, 而英文字母表示它的顏色. 補充說明, 這面牆的最左上角座標是 (1, 1), 最右下角的座標是 (W, H). 而給定的這些廣告的順序, 就是廣告單貼上去的順序. 一開始還沒有貼廣告的時候, 整面牆的顏色是小寫的 o. 如果還有什麼不夠清楚的, 請看範例.
輸出檔說明：
對每一個廣告牆, 輸出 H 行, 每行 W 個字, 也就是這面牆最後的模樣. 而在每一個廣告牆的輸出之後, 輸出一個空白行.
範例輸入：
1
5 5 2
1 1 2 2 A
2 2 3 3 B
範例輸出:
AAooo
ABBoo
oBBoo
ooooo
ooooo
題目D 工作排程
輸入檔: pd.in /輸出檔: pd.out
小光是模型工廠的老闆，每天都會接到許多訂單，可是每張訂單要求的截止時間都不一樣，小光的工廠裡只有一台機器，你知道的，做生意最主要是要講求信用，接下的訂單如果來不及完成就要早點跟客戶說。
小光有個習慣，那就是今天收到的訂單會在隔天一起處理，而訂單的截止日期也都是在隔天，只是時間早晚不同，當然機器處理每份訂單的時間長短也不同。因此，工廠每天要處理多少份訂單在前一天下班時就已經決定了，這下問題來了，小光不知道隔天是不是能順利處理完所有的訂單，如果不行的話，那他就要提早跟客戶說抱歉了，你能幫小光解決這個問題嗎？
輸入檔說明：
輸入檔第一行包含一個整數 N ( 1 ≤ N ≤ 100 )，代表 N 天收到的訂單資料，每天的訂單資料第一行包含一個整數 M ( 1 ≤ M ≤ 1000 )，表示這天有 M份訂單，接下來M行每行包含兩個整數 E, D ( 1 ≤ E ≤ D ≤ 10000 )，分別代表訂單的處理時間和訂單的截止時間，小光每天從時間0開始工作。
輸出檔說明：
一共輸出N行，一天若可以順利處理完所有的訂單，請輸出”schedulable”，若不能順利處理完，則請輸出”unschedulable”。
範例輸入：
2
3
3 5
4 7
2 10
4
2 4
4 8
3 9
4 12
範例輸出：
schedulable
unschedulable
題目E 駭客任務
輸入檔: pe.in /輸出檔: pe.out
在密碼學裡，有一種加密法叫做 Hill cipher, 方法如下：
假定我們要加密的文字都是由大寫字母 (A-Z)、小寫字母 (a-z) 及底線 (_) 共 53 種字元組成。我們先把這些字元這樣編號：_ 是 0, A 是 1, B 是 2, ..., Z 是 26, a 是 27, ..., z 是 52。如果我們要加密 "National_Problem_Solving_Contest" 這一段文字，我們先設定 block size 為 4，以 4 個字元為一組把原文切成很多個 block："Nati", "onal", "_Pro", ..., "test"。另外，我們還有一組加密公式：
y1 = ( 3 x1 + 5 x2 + 2 x3 + 0 x4) mod 53
y2 = ( 1 x1 - 7 x2 + 6 x3 + 4 x4) mod 53
y3 = (- 5 x1 - 8 x2 + 0 x3 + 0 x4) mod 53
y4 = (- 1 x1 - 1 x2 - 1 x3 - 1 x4) mod 53
我們不妨把這組加密公式稱做「母體 (Matrix)」，其中 mod 53 代表除以 53 取餘數 (介於 0 到 52 之間)，例如 61 mod 53 = 8, 而 -61 mod 53 = 45。
接下來，我們開始對每一個 block 來加密。以 "Nati" 為例，我們先按照上面的字元編號轉成一組數字 (14, 27, 46, 35), 然後把 (x1, x2, x3, x4) = (14, 27, 46, 35) 代入「母體」之中，得到 (y1, y2, y3, y4) = (4, 29, 32, 37)，再把這一串數字轉成文字，就變成 "Dcfk"。用這個方法把每一個 block 都加密完成之後，就變成 "DcfkFVEMIyeERygWR_GHbPJCrNcVLRzr"。你也可以改變上面的各項的係數以產生不同的「母體」來加密。不過值得注意的是，不是所有的「母體」都能用來加密，因為有些母體加密出來的文件有可能解不出原來的內容。
當然，整個 Hill cipher 最重要的東西，就是所謂的「母體」了。如果不知道「母體」的內容，你就很難破解出原文來。但是這套加密法有個破綻，就是只要你拿到足夠數量的原文以及加密後的結果，你就可以分析出這個密碼系統的「母體」，進而破解 Hill cipher。身為情報部門幹員的你，偶然間攔截到了敵國的機密文件，以及這份文件加密後的文字，因此你必須寫一個程式來破解這個加密系統，以便當敵國日後再用這套系統加密傳送機密資料時，能夠立即破解出原文。
輸入檔說明：
輸入檔的第一列包含一個數字 T, 代表輸入檔裡面有多少套 Hill cipher 系統等著你破解。在每一套系統裡的第一列是一個數字 n (1 ≤ n ≤ 100)，代表 block size。接下來有三個部分：第一個部分是你得到的機密文件內容，第二部份是這個機密文件加密過後的結果，第三部份是你要破解的其他加密過後的資料。每一個部份都是由上述 53 種字元所組成。這三個部份字元數都是 n 的倍數，且不會超過 65536 個字元。一整套系統的格式如下：
4 block size
===== #以一列 "=====" (5 個等號) 開始第一部份。
National_Problem_ #機密文件內容，可能會被分成很多列。
Solving_Contest
===== #以一列 "=====" 開始第二部份。
DcfkFVEMIyeERy #加密過的文件內容，也可能被分成很多列。
gWR_GHbPJCrNcVLRzr
===== #以一列 "=====" 開始第三部份。
RZDCrYapMEDiDpAk #你要破解的加密文件，可能被分成很多列。
===== #以一列 "=====" 結束整套系統。
輸出檔說明：
針對輸入檔的每一套系統，輸出你破解出來的原文。請你把原文輸出成一列，不要隨便換行。因此你的輸出檔應該會有 T 列。如果因為攔截到的資訊不足，或是資料不正確 (說不定這是敵國故意放出來擾亂的訊息)，導致無法分析出唯一一組「母體」，請你輸出 "Unable to crack the Matrix"。
範例輸入：
1
4
=====
National_Problem_
Solving_Contest
=====
DcfkFVEMIyeERy
gWR_GHbPJCrNcVLRzr
=====
RZDCrYapMEDiDpAk
=====
範例輸出：
Crack_the_Matrix
題目F 益智拼盤
輸入檔: pf.in /輸出檔: pf.out
相信大家小時候都玩過益智拼盤吧！這個遊戲是這樣玩的，在一個N乘N的矩形上，分割成很多塊形狀不同的拼圖，把拼圖打散以後，拼回原來的矩形裡就是這個遊戲的目的。
例如下面的拼圖：
111 22 333 444 55 666 7 88
111 2222 333 44444 5555 6 777 88
1 22 33 55 6 777 88
1 666 7 88
可以拼成一個8乘8的矩形如下：
11155666
11155556
12333556
12333666
22233788
22277788
44477788
44444788
你的工作就是寫一個程式把輸入的拼圖塊拼成一個N乘N的矩形。提示：每塊拼圖都可以自由的旋轉90度，180度，270度；不過為了簡化題目，所以你可以假定不需要把拼圖左右鏡射。例：
444 44 44444 4 444
44444 可轉成 44 或 444 或 4 但不能變成 44444
44 44
4 44
4 44
輸入檔說明：
輸入檔會有好幾組資料，每組資料的第一行有二個整數 N M 以一個空白格開(2 ≤ N ≤ 20)，(2≤M≤9)， N代表矩形的大小，M代表拼圖有幾塊。接下來會有好幾行表示拼圖的圖案，第1塊拼圖，第2塊拼圖… 第M塊拼圖會依序出現，中當第M個拼圖輸入完以後，這組資料就結束。
每塊拼圖的輸入分別是這樣的，對第i塊拼圖來說，會用數字i來代表這塊屬於拼圖的部份，其他部分則是以0表示；首先會有一行有兩個正整數Xi Yi，用空白格開，代表這塊拼圖是在Xi乘Yi的格子裡，接下來會有Xi行輸入，每行長Yi，代表行輸入就是這塊拼圖的外形，你可以假設每塊拼圖都是完整的不會碎裂成好幾塊，且每塊拼圖都至少會有一部分貼在一行的最左邊。
最後如果N M是0 0的話，就代表所有的輸入結束。
輸出檔說明：
對每組輸入資料，請把拼好的N乘N矩形輸出，後面再多加上一行空行。輸入資料裡的拼圖只會有一種拼法可以拼成N乘N的矩形，但是因為旋轉的關係，可能會變成4種，請你輸出最小的那種﹝至少會有一種方法可以拼成N乘N的矩形﹞。
一個拼圖的大小怎麼判斷呢？我們可以把一個拼圖當成一個很長的正整數依序寫成的，例如拼圖
111
321
222
可以看成是111321222這個數字，因此這個雖然拼圖還可以旋轉成
112 222 231
122 或 123 或 221
132 111 211
但我們要輸出的還是數字最小的
111
321
222
範例輸入：
8 8
4 3
111
111
100
100
3 4
2200
2222
2200
3 3
333
333
033
2 5
44400
44444
3 4
5500
5555
0055
4 3
666
006
006
666
4 3
007
777
777
007
4 2
88
88
88
88
3 3
2 3
111
001
2 3
222
020
1 1
3
0 0
範例輸出：
11155666
11155556
12333556
12333666
22233788
22277788
44477788
44444788
111
321
222