Problem C
Sparkle's Seven

In the wake of King Sombra’s siege on Equestria, Princess Celestia and Princess Luna have solicited the help of Shining Armor—Twilight Sparkle’s older brother—to ramp up the defenses of Canterlot Castle. Now, they have asked of Twilight to assemble a squad and try to break into the castle, hopefully exposing any security flaws it might have in the process.

\includegraphics[width=0.43\textwidth ]{TBO_Heist.png}
Figure 1: Illustration by Kyle Coate.

The sibling rivalry between Twilight and Shining Armor is obviously well-known, and Twilight could not resist the opportunity to once again one-up her brother.

Twilight quickly assembled her heist squad, consisting of herself, Applejack, Rarity, Pinkie Pie, Fluttershy, Rainbow Dash and Spike, and sketched out a scheme to break into the castle.

They have identified seven potential points of weakness in the defenses of Canterlot Castle. To complete the heist successfully, they need to exploit all seven points of weakness. Unfortunately, not all points of weakness can be exploited by every member of the squad; for example, it may be the case that only Rarity can construct costumes intricate enough to fool the royal guards, and only Rainbow Dash can fly fast enough to defeat the system of giant fans that have been installed.

Twilight has noted for every member of the squad whether or not that member can exploit each of the seven points of weakness.

In one operation, Twilight must choose some non-empty subset of the members of the squad (possibly everyone) and have each chosen member exploit one weakness. It might not be possible to exploit all seven points of weakness in just one operation, so she can construct multiple such operations, possibly sending the same member on multiple operations. After all operations have been conducted, every weakness must have been exploited exactly once.

Of course, the more operations she needs to execute, the longer the heist will take and the greater the chance her conspiracy will be discovered; therefore, the number of operations should be as small as possible.

Can you help her plan out the heist?

If it is not possible for the heist to succeed at all, you should also let her know.


There will be seven lines of input.

Each line contains seven integers. In particular, the $j^\text {th}$ integer on the $i^\text {th}$ of these lines is either:

  • $0$, if the $i^\text {th}$ member cannot exploit the $j^\text {th}$ weakness;

  • $1$, if the $i^\text {th}$ member can exploit the $j^\text {th}$ weakness.

The members are, in order, Twilight Sparkle, Applejack, Rarity, Pinkie Pie, Fluttershy, Rainbow Dash and Spike.


If it is not possible for the heist to succeed, output a single line containing the string IMPOSSIBLE.

Otherwise, on the first line, output a single integer $p$ ($1 \leq p \leq 7$), the minimum number of operations needed to complete the heist successfully.

Then, output the $p$ operations.

The $i^\text {th}$ operation should first contain a single integer $m_ i$ ($1 \leq m_ i \leq 7$) on a single line, the number of members involved in the $i^\text {th}$ operation.

Then, on the next $m_ i$ lines, output the members involved in the $i^\text {th}$ plan. In particular, the $j^\text {th}$ of these lines should contain one of Twilight Sparkle, Applejack, Rarity, Pinkie Pie, Fluttershy, Rainbow Dash or Spike followed by a single integer $e_{i, j}$ ($1 \leq e_{i, j} \leq 7$), separated by a space, denoting that the given member should exploit the $e_{i, j}^\text {th}$ point of weakness.

Each member should appear at most once in one operation, and every weakness should be exploited exactly once across all the operations. Within each operation, you can output the members in any order.

If there are multiple correct answers, you can output any of them.

Sample Input 1 Sample Output 1
1 0 1 0 0 0 0
0 1 1 0 0 0 0
1 0 1 0 0 1 0
0 0 1 1 0 0 0
1 0 1 0 0 1 0
0 0 1 0 1 0 1
0 0 1 0 0 0 0
Applejack 2
Pinkie Pie 4
Rarity 6
Rainbow Dash 7
Twilight Sparkle 1
Fluttershy 3
Rainbow Dash 5
Sample Input 2 Sample Output 2
0 0 0 0 0 0 0
0 0 1 0 1 0 0
0 0 1 0 1 0 0
0 0 0 0 0 0 0
0 0 1 1 1 0 0
0 1 0 0 0 1 0
0 0 0 0 0 0 0

Please log in to submit a solution to this problem

Log in