|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|4 초||1024 MB||38||19||13||43.333%|
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\le N\le 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:
For $T$ ($1\le T\le 2\cdot 10^5$) instances of the problem above, count the minimum number of moves required to turn all the lights off.
First line contains $T$ and $N$.
Next $T$ lines each contain a pair of length-$N$ bit strings.
For each pair, the minimum number of moves required to turn all the lights off.
4 3 000 101 101 100 110 000 111 000
0 1 3 2
It can be shown that in each case this is the minimal number of moves necessary.
1 10 1100010000 1000011000
It can be shown that $2$ moves are required to turn all lights off.