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.


原文出處