The Number of Sequences
Time limit1sMemory limit128 MB
For a given N and C, find the lexicographically smallest triple (X, Y, Z) such that exactly C ordered N-tuples of 31-bit integers have OR X, AND Y, XOR Z, or report none exists.
- Level
Hard9 of 10
- Topics
- Bit manipulation, Combinatorics, Math, Dynamic programming
- Solved
- No attempts yet
Problem
Consider a sequence of numbers that satisfies all four conditions below.
- Every number in the sequence is an integer between and , inclusive.
- The bitwise OR of every number in the sequence is .
- The bitwise AND of every number in the sequence is .
- The bitwise XOR of every number in the sequence is .
Taekhee owned every sequence that satisfies these conditions, but he lost some of them while moving. Once he knows , , and , he can build all of them again.
Taekhee remembers two facts. The sequence length is , and exactly sequences satisfy all four conditions.
Find the values of , , and . Two sequences whose numbers appear in a different order count as different sequences.
Input
The first line contains the sequence length and the number of sequences that satisfy the conditions, separated by a space. (, )
Output
On the first line print integers , , and between and , separated by spaces, for which exactly sequences satisfy the conditions.
If several triples satisfy the conditions, print the lexicographically smallest one. Take the smallest , among those the smallest , and among those the smallest .
If no such , , exist, print and nothing else.