2011年8月25日 星期四

434 - Matty's Blocks


馬弟喜歡玩方塊積木,他喜歡將一堆一堆的積木疊在一起後,把每組疊在一起的積木放在K x K大小的的棋盤方格中(K最大為8),每組方塊的高度最大為8。

下圖為K=4的列子:

馬弟也喜歡畫畫,他會把方塊組成的圖形輪廓畫出來,不過3D立體方塊圖對他來說太難了,所以他只畫出了前視輪廓圖與側視輪廓圖,分別為從前面與側面的投影,顯示從該方向所看到的輪廓。如下圖所示:

前視圖                                側視圖
他以為只要畫出這兩張圖之後就可以照著圖重新組合方塊結構,不過他錯了,不同的方塊結構可能會有相同的輪廓圖,同時,他發現依照所描繪的兩張輪廓圖 重組方塊所需的數量不盡相同,且有一個最少方塊數量的組合方式,其所需的最少方塊數為N。若以此基礎增加方塊數量且保持相同的輪廓圖,直到增加M塊方塊之 後達到最大的數量。也就是說,最少N塊,最多(N+M)塊有相同輪廓圖。
以上例來說明,最少與最大數量的方塊分別為7, 17塊,即N=7, M=10,如下圖所示:

最小的結構                            最大的結構
給定一組輪廓圖,請你計算N, M之值為何。

Input Specification

輸入資料的第一列為一個整數表示測試資料的組數。每組資料的第一列為整數K,表示積木所在區域的大小,接下來有兩列資料,分別表示前輪廓圖與側輪廓圖,每列有K個以空白字元隔開的非負整數,每個整數表示相對應位置輪廓的高度。每組資料必可構成最少一種方塊組合。

Output specification

請以下列格式輸出N, M之值。

Matty needs at least N blocks, and can add at most M extra blocks.

Sample Input

2
4
2 0 3 1
1 1 2 3
1
1
1

Sample Output

Matty needs at least 7 blocks, and can add at most 10 extra blocks.
Matty needs at least 1 blocks, and can add at most 0 extra blocks.


原文出處

沒有留言:

張貼留言