TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

40.0% (8/20)

Submission's AC Ratio

20.8% (10/48)

Tags

Description

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

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

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

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

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

Input Format

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

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

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

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

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

本題有九個子問題,每一子題的測資編號與相異度標準$L$在下方Subtasks區。如果你在該測資的答案相異度$\geq 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