d790. 00729 - The Hamming Distance Problem
標籤 :
通過比率 : 259人/269人 ( 96% ) [非即時]
評分方式:
Tolerant

最近更新 : 2012-11-15 02:32

內容
給2個相同長度的2元字串,比較他們在相同位置的內容,並計算各位置內容不一樣的總數,我們稱該數為它們之間的Hamming distance。這任務可以經由對字串中各相同位置字元作XOR的運算或者做2進位的相加(但不進位)而得到。以下的例子為2個長度為10的2元字串A、B經過XOR運算。可以看出共有6個1,所以其Hamming distance為6。
                               A      0 1 0 0 1 0 1 0 0 0
                               B      1 1 0 1 0 1 0 1 0 0
                            A XOR B = 1 0 0 1 1 1 1 1 0 0

你的任務是給你字串的長度(N)及所要求的Hamming distance(H),請你輸出所有這樣的2元字串,也就是長度為N的二元字串,且恰好有H個1的字串。由數學我們得知這樣的字串共有C(N,H)個。也就是:

輸入說明

輸入的第一列有一個正整數,代表以下有多少組測試資料。

每組測試資料一列,含有2個正整數N、H(1 <= H <= N <= 16)。N代表字串的長度,H代表Hamming distance。

請參考Sample Input。

輸出說明

對每一組測試資料,輸出所有長度為N,且Hamming distance為H的二元字串,並由小到大輸出。測試資料間請空一列。

範例輸入 #1
2

4 2

3 2
範例輸出 #1
0011
0101
0110
1001
1010
1100

011
101
110
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 1.0s , <1K
提示 :
Lucky 貓 中 英 ★★
標籤:
出處:
UVa729 [管理者: snail (蝸牛) ]

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」