TopCoder

餘切
pooh is 8

User's AC Ratio

38.5% (10/26)

Submission's AC Ratio

25.0% (20/80)

Tags

Description

最近各種DIY的小型吊飾十分熱門,不只可以讓人享受手作的樂趣,還能自己挑選喜歡的款式,因而受到大眾的喜愛。而你與你的k個好朋友,也受到這股潮流的影響,想要一起製作屬於自己的裝飾品。經過一番挑選,你們選擇了一種有N個珠子排成一列的吊飾,來進行製作。

珠子一共有兩種型態,一種是圓形,而另一種是方形。將這些珠子以任意的順序排成一列,再把他們小心的串在一起,就完成屬於自己的吊飾了。

你的k個朋友們依序完成了自己的吊飾,而當你也準備開始製作時,突然想到:「我的吊飾必須『與眾不同』!」對於兩串吊飾AB,定義他們的「相異度」為兩串吊飾有多少個位置的珠子種類不同。例如一個順序為「圓、圓、方、圓、方」的吊飾與一個順序為「圓、方、方、圓、圓」的吊飾,他們的「相異度」為2

你希望你最後製作出的吊飾,與其他k個朋友的吊飾的「相異度」的最小值,可以越大越好。請輸出任意一個合法的吊飾,使它與其他k個吊飾的「相異度」最小值最大。

最近你的朋友變多了! 而他們等你計算最大的相異度已經等到不耐煩了,因此你制定了一個標準L,只要吊飾的相異度不小於L你就足夠滿意。

Input Format

本題原本應該是Output Only題,但由於TIOJ目前不支援Output Only,因此在上傳與評分方式有一些不同。

本題共有6筆測資,依序編號為16
請至 此處 下載測資至本機。

每一筆測試資料有兩個整數N,k,表示吊飾的珠子個數與朋友的數目。
接下來共k行,第i行有一個長度為N的01字串Si,表示第i位朋友製作的吊飾(0代表圓形的珠子,1代表方型的珠子)。

每一筆測試資料的範圍如下:

上傳的時候,請寫一個程式,並將每一筆測資的答案貼在程式內部。請輸入一個整數id,代表測資的編號,並直接輸出該測資的解。

本題有九個子問題,每一子題的測資編號與相異度標準L在下方Subtasks區。如果你在該測資的答案相異度L,你將會獲得該子題的全部分數。

Output Format

參考Input Format的說明。

Sample Input 1

假設$id=0$的測資為:
5 2
00101
01100
那麼輸入會是:
0

Sample Output 1

當$id=0$時,輸出
10010

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0 id=1,L=5 9
2 1 id=2,L=14 10
3 2 id=3,L=416 14
4 3 id=4,L=279 6
5 4 id=4,L=378 11
6 5 id=5,L=57 9
7 6 id=5,L=70 12
8 7 id=6,L=116 13
9 8 id=6,L=136 16

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1
1 1000 65536 65536 2
2 1000 65536 65536 3
3 1000 65536 65536 4
4 1000 65536 65536 5
5 1000 65536 65536 6
6 1000 65536 65536 7
7 1000 65536 65536 8
8 1000 65536 65536 9