最近各種DIY的小型吊飾十分熱門,不只可以讓人享受手作的樂趣,還能自己挑選喜歡的款式,因而受到大眾的喜愛。而你與你的$k$個好朋友,也受到這股潮流的影響,想要一起製作屬於自己的裝飾品。經過一番挑選,你們選擇了一種有$N$個珠子排成一列的吊飾,來進行製作。
珠子一共有兩種型態,一種是圓形,而另一種是方形。將這些珠子以任意的順序排成一列,再把他們小心的串在一起,就完成屬於自己的吊飾了。
你的$k$個朋友們依序完成了自己的吊飾,而當你也準備開始製作時,突然想到:「我的吊飾必須『與眾不同』!」對於兩串吊飾$A$、$B$,定義他們的「相異度」為兩串吊飾有多少個位置的珠子種類不同。例如一個順序為「圓、圓、方、圓、方」的吊飾與一個順序為「圓、方、方、圓、圓」的吊飾,他們的「相異度」為$2$。
你希望你最後製作出的吊飾,與其他$k$個朋友的吊飾的「相異度」的最小值,可以越大越好。請輸出任意一個合法的吊飾,使它與其他$k$個吊飾的「相異度」最小值最大。
最近你的朋友變多了! 而他們等你計算最大的相異度已經等到不耐煩了,因此你制定了一個標準$L$,只要吊飾的相異度不小於$L$你就足夠滿意。
本題原本應該是Output Only題,但由於TIOJ目前不支援Output Only,因此在上傳與評分方式有一些不同。
本題共有$6$筆測資,依序編號為$1$至$6$。
請至 此處 下載測資至本機。
每一筆測試資料有兩個整數$N,k$,表示吊飾的珠子個數與朋友的數目。
接下來共$k$行,第$i$行有一個長度為$N$的01字串$S_i$,表示第$i$位朋友製作的吊飾(0代表圓形的珠子,1代表方型的珠子)。
每一筆測試資料的範圍如下:
上傳的時候,請寫一個程式,並將每一筆測資的答案貼在程式內部。請輸入一個整數$id$,代表測資的編號,並直接輸出該測資的解。
本題有九個子問題,每一子題的測資編號與相異度標準$L$在下方Subtasks
區。如果你在該測資的答案相異度$\geq L$,你將會獲得該子題的全部分數。
參考Input Format
的說明。
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 |