LA 2722

From Algorithmist
Jump to navigation Jump to search

LA 2722 - Light Bulbs[edit]

Summary[edit]

Given is a row of bulbs and a row of switches. Each switch flips the corresponding bulb and its two neighbors. (The leftmost and the rightmost switch flip less than three bulbs.)

Given are an initial state of the bulbs and a desired final state. Both configurations are encoded as decimal numbers. Find whether the final state can be reached. If yes, find such a solution (a set of switches) that its encoding into a decimal number is as small as possible.

Explanation[edit]

Once we fix the state of the leftmost switch (flipped/not flipped), the rest of the switches is uniquely determined: We know the current state of the leftmost bulb, thus we know whether to flip the second switch, and so on, the bulb before the last one determines the last switch, and the last bulb is either correct (and we found a solution) or wrong.

Thus there are at most two solutions. If there is zero or one solution, the answer is clear. Otherwise, encode both of them and output the smaller answer.

Gotchas[edit]

  • Watch out for other small cases, e.g., "1 0".
  • Don't overlook that the input (and output) numbers can have up to 100 digits.

Input[edit]

12 16
1 1
3 0
30 5
7038312 7427958190
4253404109 657546225
0 0

Output[edit]

Case Number 1: 8

Case Number 2: 0

Case Number 3: 1

Case Number 4: 10

Case Number 5: 2805591535

Case Number 6: impossible