TopCoder

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

User's AC Ratio

61.7% (50/81)

Submission's AC Ratio

17.8% (59/331)

Tags

Description

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

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

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

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

Input Format

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

對於所有測試資料,保證$1\leq N\leq 10^ 5$,$1\leq k\leq 3$。

Output Format

輸出一個長度為$N$的01字串$S$,表示滿足與其他$k$個吊飾的「相異度」最小值最大的吊飾。若有多組合法的解,輸出任意一組皆可。

Sample Input 1

5 2
00101
01100

Sample Output 1

10010

Hints

以範測為例,字串"10010"與"00101"、"01100"的「相異度」皆為$4$,因此最小值為$4$,是所有可能性中最大的,符合要求。除此之外,字串"11011"也符合要求,其餘字串皆不符合要求。

Problem Source

110學年度建國中學校內資訊能力競賽初試pB

Subtasks

No. Testdata Range Constraints Score
1 0~19 $n \leq 15$ 15
2 20~34 $k \leq 2$ 49
3 0~49 $無其他限制$ 36

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1 3
1 1000 65536 65536 1 3
2 1000 65536 65536 1 3
3 1000 65536 65536 1 3
4 1000 65536 65536 1 3
5 1000 65536 65536 1 3
6 1000 65536 65536 1 3
7 1000 65536 65536 1 3
8 1000 65536 65536 1 3
9 1000 65536 65536 1 3
10 1000 65536 65536 1 3
11 1000 65536 65536 1 3
12 1000 65536 65536 1 3
13 1000 65536 65536 1 3
14 1000 65536 65536 1 3
15 1000 65536 65536 1 3
16 1000 65536 65536 1 3
17 1000 65536 65536 1 3
18 1000 65536 65536 1 3
19 1000 65536 65536 1 3
20 1000 65536 65536 2 3
21 1000 65536 65536 2 3
22 1000 65536 65536 2 3
23 1000 65536 65536 2 3
24 1000 65536 65536 2 3
25 1000 65536 65536 2 3
26 1000 65536 65536 2 3
27 1000 65536 65536 2 3
28 1000 65536 65536 2 3
29 1000 65536 65536 2 3
30 1000 65536 65536 2 3
31 1000 65536 65536 2 3
32 1000 65536 65536 2 3
33 1000 65536 65536 2 3
34 1000 65536 65536 2 3
35 1000 65536 65536 3
36 1000 65536 65536 3
37 1000 65536 65536 3
38 1000 65536 65536 3
39 1000 65536 65536 3
40 1000 65536 65536 3
41 1000 65536 65536 3
42 1000 65536 65536 3
43 1000 65536 65536 3
44 1000 65536 65536 3
45 1000 65536 65536 3
46 1000 65536 65536 3
47 1000 65536 65536 3
48 1000 65536 65536 3
49 1000 65536 65536 3