2013年7月11日 星期四

11100 - The Trip, 2007


Problem A: The Trip, 2007

在俱樂部的一群學生每年都會前往異國情調的地點旅遊。他們過去曾去過印第安納波利斯、鳳凰城、納什維爾、費城、聖何塞、亞特蘭大、恩荷芬、奧蘭多、溫哥華、檀香山、比佛利山莊(Beverly Hills)、布拉格、上海和聖安東尼奧。今年春天,他們打算也來個類似的旅行,但不知道在何時何地舉辦。

旅遊的討論議題是關於他們非常慷慨的贊助商,贊助商總是給他們很多種背包以及提包,他們必須在旅行前整理。但是航空公司最多允許一定配額的行李,因此他們打算集中他們得到的禮物(指的是各種背包以及提包)放進包包中,最小化行李個數。

每個包包都有相同的形狀,唯一不同的地方在線性維度(一個正整數不超過 100,0000)。較小維度的包包將可以放入較大維度的包包中,計算哪個包包放入哪個包包中,最小化最外層的包包個數,同時在相同時,維護在每個外層包包內的包包個數的最大值最小化。

輸入有多組測資,每組第一行有一個整數 1 ≤ n ≤ 10000,接下來會有 n 個整數,每個數字表示被給予的維度。最後一組 n = 0 結束程式。

對於每組測資,輸出一個 k,表示最少的個數,接下來要印出 k 行,每行上表示一個外層包包內的所有維度,輸入的每個維度確切只會在輸出出現一次,而包包只會呈現巢狀放在另一個包包內。

如果有不只一組解,任何一組都可以。測資組間輸出一個空行。

Sample Input

6
1 1 2 2 2 3
0

Output for Sample Input

3
1 2
1 2
3 2

Troy Vasiga, Graeme Kemkes, Ian Munro, Gordon V. Cormack