Preparando MOJI
A bitstring is a string that contains only the characters 0 and 1.
Koyomi Kanou is working hard towards her dream of becoming a writer. To practice, she decided to participate in the Binary Novel Writing Contest. The writing prompt for the contest consists of three bitstrings of length $$$2n$$$. A valid novel for the contest is a bitstring of length at most $$$3n$$$ that contains at least two of the three given strings as subsequences.
Koyomi has just received the three prompt strings from the contest organizers. Help her write a valid novel for the contest.
A string $$$a$$$ is a subsequence of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero) characters.
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.
The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$).
Each of the following three lines contains a bitstring of length $$$2n$$$. It is guaranteed that these three strings are pairwise distinct.
It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$10^5$$$.
For each test case, print a single line containing a bitstring of length at most $$$3n$$$ that has at least two of the given bitstrings as subsequences.
It can be proven that under the constraints of the problem, such a bitstring always exists.
If there are multiple possible answers, you may output any of them.
2 1 00 11 01 3 011001 111010 010001
010 011001010
In the first test case, the bitstrings 00 and 01 are subsequences of the output string: 010 and 010. Note that 11 is not a subsequence of the output string, but this is not required.
In the second test case all three input strings are subsequences of the output string: 011001010, 011001010 and 011001010.
Informação
Provedor Codeforces
Código CF1508A
Tags
Submetido 0
BOUA! 0
Taxa de BOUA's 0%
Datas 09/05/2023 10:12:30
Relacionados