P1146 Coin Flipping

There is a row of $N$ coins on the table, all initially heads up. You need to turn all coins to tails up. The rule is that each time you may flip any $N-1$ coins (a heads-up coin becomes tails up, and vice versa). Find a shortest sequence of operations (each flip of $N-1$ coins counts as one operation).

A natural number $N$ (where $N$ is an even number no greater than 100).

The first line contains an integer $S$, the minimal number of operations needed. The next $S$ lines each describe the state of the coins on the table after that operation (a line with $N$ integers 0 or 1, indicating each coin’s state; 0 means heads up, 1 means tails up). No extra spaces are allowed. If there are multiple valid operation sequences, output one whose sequence of operations is lexicographically smallest. The lexicographical order of an operation is defined as follows: for each position in a single operation, 1 means flip, and 0 means do not flip. However, you must output the state after each operation, where 0 means heads up and 1 means tails up.

Translated by ChatGPT 5