P2447 [SDOI2010] Alien Millipedes

On February 3, $2333$, after a long journey of $17$ years and $3$ months, the re-entry capsule of the manned rocket “Genagelu-1” finally landed safely. Developed and launched by NASA, this rocket traveled past $23$ bodies in the Solar System, including Mars, Venus, Titan, Europa, Ceres, and “Zhangheng Star,” and eventually discovered extraterrestrial life on the asteroid “Jason Star.” Astronauts found a batch of precious living samples $45.70$ meters below the surface rock layer of “Jason Star” and brought them back for testing. Among the living samples, the most fascinating are these alien millipedes. Their bodies are long and divided into segments. When touched, they curl into a ring and take a while before resuming activity. There is more. Researchers found that, unlike terrestrial millipedes whose legs appear in pairs with a total even number, these aliens have a variable number of legs under each body segment, but the total number of legs is always odd. Although they are hard to distinguish by appearance, by counting the number of legs, scientists can determine a millipede’s home planet based on parity. As a secret agent sent by country J to NASA, you want to join the research to gather more intelligence. However, NASA’s selected researchers are all top scientists. So Charles Bolden, the NASA Administrator, set a challenge to test your ability: There are $N$ millipedes numbered $1 \ldots N$ in front of you. Your task is to determine the home planet of each millipede, but you are not allowed to count their legs directly. Each time, Charles will select some of the $N$ millipedes and put them into the Insect Feet Counter (IFC). The counter automatically sums the total number of legs inside. Charles will give you the result modulo $2$, and also tell you which millipedes were put into the machine. He will perform this operation $M$ times, and you should reach the conclusion as early as possible. If, after the $K$-th measurement, the existing data are already sufficient to uniquely determine each millipede’s identity, you should report this $K$ to Charles. If $K

The first line contains two positive integers $N, M$. The next $M$ lines give, in order, the $M$ results from Charles’s use of the counter. Each line contains a $01$ string and a number, separated by a space. The $01$ string indicates, by position, whether each millipede is put into the machine: if the $i$-th character is $0$, millipede $i$ is not put in; if it is $1$, it is put in. The following number is the total number of legs modulo $2$. Since NASA’s experimental machines are perfectly accurate, the data are guaranteed to be consistent. That is, there is at least one solution.

If the given data yield a unique solution, output $N+1$ lines. The first line outputs a positive integer $K$ not exceeding $M$, indicating that after the $K$-th measurement the unique solution is determined. The next $N$ lines output the identity of each millipede in order: output `?y7M#` for an odd number of legs, and `Earth` for an even number of legs. If the input data admit multiple solutions, output `Cannot Determine`.

Scoring - For each test point, if your output file exactly matches the answer file, you get full credit for that point. - Otherwise, if the solution is unique and you correctly output the identities of all millipedes, you get $50\%$ of the points for that test point. - In all other cases, you get zero for that test point. Constraints and Conventions - For $20\%$ of the test points, $N=M\leq 20$. - For $40\%$ of the test points, $N=M\leq 500$. - For $70\%$ of the test points, $N\leq 500$, $M\leq 10^3$. - For $100\%$ of the test points, $1\leq N\leq 10^3$, $1\leq M\leq 2\times 10^3$. Translated by ChatGPT 5