Binary Table
Time limit2sMemory limit512 MB
Given n shuffled row values and the corner sum X, find X among the n+1 numbers and rebuild the 0/1 table, or report if it is not unique.
- Level
Medium7 of 10
- Topics
- Math, Bit manipulation, Implementation
- Solved
- No attempts yet
Problem
Kipa received an by table filled with 0s and 1s as a gift from Yul. Kipa liked the gift so much that Kipa wrote, to the right of each row, the value of that row read as a binary number and converted to decimal. In the same way, Kipa wrote below each column the value of that column read as a binary number, and wrote the sum of all those values in the bottom-right corner.
Then Minti took the table. Minti told Kipa the numbers in the rightmost column, in shuffled order, and then burned Kipa's precious table!
Kipa worked out which of the numbers Minti gave is , the one in the bottom-right corner. But Kipa is too sad to continue. Can you do this for Kipa?
Input
The first line contains a positive integer at most and a positive integer less than .
From the second line, lines follow. Each contains one of the numbers Minti gave, excluding . Each number is a positive integer, the numbers are distinct, and each is less than .
All numbers are given in decimal.
Output
If the given information determines the table uniquely, print the original by table without spaces. Otherwise, print kipa so sad :(.
Hint
For the first input, the table below can be built, and it is unique.