8169: USACO 2023 January Contest, Gold Problem 2. Lights Off
[Creator : ]
Description
Bessie wants to go to sleep, but the farm's lights are keeping her awake. How can she turn them off?
Bessie has two bit strings of length N (2≤N≤20), representing a sequence of lights and a sequence of switches, respectively. Each light is either on (1) or off (0). Each switch is either active (1) or inactive (0).
A *move* consists of the following sequence of operations:
Bessie has two bit strings of length N (2≤N≤20), representing a sequence of lights and a sequence of switches, respectively. Each light is either on (1) or off (0). Each switch is either active (1) or inactive (0).
A *move* consists of the following sequence of operations:
- Toggle exactly one switch (set it to active if it is inactive, or vice versa).
- For each active switch, toggle the state of the corresponding light (turn it off if it is on, or vice versa).
- Cyclically rotate the switches to the right by one. Specifically, if the bit string corresponding to the switches is initially $s_0s_1…s_{N−1}$ then it becomes $s_{N−1}s_0s_1…s_{N−2}$.
Input
First line contains T and N. Next T lines each contain a pair of length-N bit strings.
Output
For each pair, the minimum number of moves required to turn all the lights off.
Sample 1 Input
4 3
000 101
101 100
110 000
111 000
Sample 1 Output
0
1
3
2
- First test case: the lights are already all off.
- Second test case: We flip the third switch on the first move.
- Third test case: we flip the first switch on the first move, the second switch on the second move, and the second switch again on the third move.
- Fourth test case: we flip the first switch on the first move and the third switch on the second move.
Sample 2 Input
1 10
1100010000 1000011000
Sample 2 Output
2
It can be shown that 2 moves are required to turn all lights off.
- We flip the seventh switch on the first move and then again on the second move.