d597: 2. 便當的編號與配菜組合
Tags :
Accepted rate : 134人/137人 ( 98% ) [非即時]
評分方式:
Tolerant

最近更新 : 2009-12-22 12:26

Content

有一家便當店生意很好,他們的特色是每一個便當內的配菜組合都不會跟當
天的另一個便當完全相同。這家店的秘訣是依靠一個能夠產生所有從{1, 2,
3, …, n}中取k 組合的程式。當設定好n 與k 值後,這個程式就會輸出C(n, k)
列,每一列都是以k 個數的遞增數列來表示一種k 組合,而這些k 組合又是依照
字典遞增順序(increasing lexicographic order)來產生,也就是說,在k
組合均以k 個數的遞增數列來表示的前提下,第1 個數越小的k 組合會越先產
生,若第1 個數一樣,則第2 個數越小的k 組合會越先產生,依此類推。假設便
當店當天的配菜共有n 種,每一種份量都很充足,且製作每一個便當均需放入k
種配菜,那麼便當店只要設定好程式的n 與k 值後,當天編號1 的便當就依程式
輸出第1列的k組合來配菜,編號2的便當就依程式輸出第2列的k組合來配菜,
依此規則,配菜組合自然就不會重複了。舉例來說,當n 為5,k 為3 時,便當
編號與配菜組合的對應如下:
便當編號 配菜組合

         1 1 2 3
         2 1 2 4
         3 1 2 5
         4 1 3 4
         5 1 3 5
         6 1 4 5
         7 2 3 4
         8 2 3 5
         9 2 4 5
        10 3 4 5
現在要請你寫一個目的有點不同的程式,當輸入便當店所有配菜種類數n、
每一便當所需配菜種類數k、與某一個{1, 2, 3, …, n}中取k 的配菜組合後,
你的程式要在第1 列輸出這個配菜組合對應的便當編號,並在第2 列輸出下一編
號(上面的編號加1)便當的配菜組合。萬一輸入的配菜組合已經是最後一種組
合,第1 列還是要先輸出對應的便當編號,而因為沒有下一編號的便當,第2
列只要輸出『no next combination』即可。

Input
輸入共有2 列。第1 列有兩個整數n 與k,中間由一個空白隔開,1≤ k ≤ n
≤ 10。第2 列有k 個遞增的整數,中間均由一個空白隔開,表示一個{1, 2, 3, …,
n}中取k 的配菜組合(你的程式不用檢查第2 列是否為組合,因為測試資料一定
會給一種可能的組合)。
Output
輸出共有2 列。第1 列為對應到輸入配菜組合的便當編號。第2 列為下一編
號便當的配菜組合,請以k 個遞增的整數表示,中間均由一個空白隔開。若輸入
的配菜組合已經是最後一種組合,第1 列還是要先輸出對應的便當編號,而第2
列只要輸出『no next combination』即可。
Sample Input
輸入範例1:
5 3
1 4 5

輸入範例2:
5 3
3 4 5
Sample Output
輸出範例1:
6
2 3 4

輸出範例2:
10
no next combination
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (20%): 2.0s , <1K
公開 測資點#1 (20%): 2.0s , <1K
公開 測資點#2 (20%): 2.0s , <1K
公開 測資點#3 (20%): 2.0s , <1K
公開 測資點#4 (20%): 2.0s , <1K
Hint :
Tags:
出處:
98學年度全國資訊學科能力競賽 [管理者:
swda289346 (太威啦)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」