[ARC155E] Split and Square
Score : points
Problem Statement
For a set of non-negative integers, let denote the set of non-negative integers that can be represented as the bitwise of two integers (possibly the same) in . As an example, for , we have .
You are given a set of non-negative integers less than : .
You may perform the following operation any number of times.
- Divide into two sets and (one of them may be empty). Then, replace with the union of and .
Find the minimum number of operations needed to make .
What is bitwise $\mathrm{XOR}$?
The bitwise $\mathrm{XOR}$ of non-negative integers $A$ and $B$, $A \oplus B$, is defined as follows.
- When $A \oplus B$ is written in binary, the $k$-th lowest bit ($k \geq 0$) is $1$ if exactly one of the $k$-th lowest bits of $A$ and $B$ is $1$, and $0$ otherwise.
Generally, the bitwise \mathrm{XOR} of k non-negative integers p_1, p_2, p_3, \dots, p_k is defined as (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k), which can be proved to be independent of the order of p_1, p_2, p_3, \dots, p_k.
Constraints
- are pairwise distinct.
- Each is given with exactly digits in binary (possibly with leading zeros).
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
Output
Print the answer.
4 2
00
01
10
11
2
In the first operation, you can divide into , for which $f(T_1) =\lbrace 0, 1\rbrace, f(T_2) =\lbrace 0, 1\rbrace$, replacing with .
In the second operation, you can divide into , making .
There is no way to make in fewer than two operations, so the answer is .
1 8
10011011
1
In the first operation, you can divide into , making . Note that or may be empty.
1 2
00
0
We have from the beginning; no operation is needed.
20 20
10011011111101101111
10100111100001111100
10100111100110001111
10011011100011011111
11001000001110011010
10100111111011000101
11110100001001110010
10011011100010111001
11110100001000011010
01010011101011010011
11110100010000111100
01010011101101101111
10011011100010110111
01101111101110001110
00111100000101111010
01010011101111010100
10011011100010110100
01010011110010010011
10100111111111000001
10100111111000010101
10