最近各種DIY的小型吊飾十分熱門,不只可以讓人享受手作的樂趣,還能自己挑選喜歡的款式,因而受到大眾的喜愛。而你與你的$k$個好朋友,也受到這股潮流的影響,想要一起製作屬於自己的裝飾品。經過一番挑選,你們選擇了一種有$N$個珠子排成一列的吊飾,來進行製作。
珠子一共有兩種型態,一種是圓形,而另一種是方形。將這些珠子以任意的順序排成一列,再把他們小心的串在一起,就完成屬於自己的吊飾了。
你的$k$個朋友們依序完成了自己的吊飾,而當你也準備開始製作時,突然想到:「我的吊飾必須『與眾不同』!」對於兩串吊飾$A$、$B$,定義他們的「相異度」為兩串吊飾有多少個位置的珠子種類不同。例如一個順序為「圓、圓、方、圓、方」的吊飾與一個順序為「圓、方、方、圓、圓」的吊飾,他們的「相異度」為$2$。
你希望你最後製作出的吊飾,與其他$k$個朋友的吊飾的「相異度」的最小值,可以越大越好。請輸出任意一個合法的吊飾,使它與其他$k$個吊飾的「相異度」最小值最大。
輸入的第一行有兩個整數$N,k$,表示吊飾的珠子個數與朋友的數目。
接下來共$k$行,第$i$行有一個長度為$N$的01字串$S_i$,表示第$i$位朋友製作的吊飾(0代表圓形的珠子,1代表方型的珠子)。
對於所有測試資料,保證$1\leq N\leq 10^ 5$,$1\leq k\leq 3$。
輸出一個長度為$N$的01字串$S$,表示滿足與其他$k$個吊飾的「相異度」最小值最大的吊飾。若有多組合法的解,輸出任意一組皆可。
以範測為例,字串"10010"與"00101"、"01100"的「相異度」皆為$4$,因此最小值為$4$,是所有可能性中最大的,符合要求。除此之外,字串"11011"也符合要求,其餘字串皆不符合要求。
110學年度建國中學校內資訊能力競賽初試pB
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~19 | $n \leq 15$ | 15 |
2 | 20~34 | $k \leq 2$ | 49 |
3 | 0~49 | $無其他限制$ | 36 |