Binary XOR
Time limit2sMemory limit128 MB
Given binary strings, find the closest achievable XOR combination (using at least one XOR) to a target, breaking ties by fewest operations then lexicographic order.
- Level
Medium6 of 10
- Topics
- Bit manipulation, Math, Brute force
- Solved
- No attempts yet
Problem
You are given E binary strings of length B. (1 <= B <= 16, 1 <= E <= 100)
You may choose two binary strings from the strings you already have or from strings created by earlier XOR operations, and XOR them. You may choose the same binary string twice.
If the target binary string can be made, output that string. Otherwise, output the binary string that is closest to the target. The distance between two binary strings is the number of bit positions where they differ.
If several candidates have the same minimum distance, choose the one that uses the fewest XOR operations to make. If there is still a tie, choose the lexicographically smallest binary string.
The XOR operator is ^. For each bit, 0^0=0, 0^1=1, 1^0=1, and 1^1=0; 10110 ^ 11101 produces 01011.
Input
The first line contains B and E.
The second line contains the target binary string of length B.
Each of the next E lines contains one available binary string of length B.
Output
On the first line, print the number of XOR operations used to make the chosen binary string.
On the second line, print the chosen binary string.
At least one XOR operation must be performed.