eolymp
bolt
Try our new interface for solving problems
Məsələlər

Bad Wiring

Bad Wiring

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 32 MiB

The ninja Ryu has infiltrated the Shadow Clan fortress and finds himself in a long hallway. Although ninjas are excellent fighters, they primarily rely on stealth to complete their missions. However, many lights are turned on in the hallway, and this way it will not take long before Ryu is spotted by a guard. To remain unseen, Ryu will need to turn off all the lights as quickly as possible.

The hallway contains a sequence of n lights L_1...L_n. Some of these lights are turned on. Destroy-ing the lights with his shurikens would be too loud, so he needs to turn them off the old-fashioned way, using light switches. Luckily, there is a switch box nearby with a light switch S_i for every light L_i. However, after trying one of the switches, he notices something funny. When he ips the switch S_i, it does not only turn on/off light L_i, but also some of the neighboring lights. Ryu notices that there is a parameter D such that ipping switch S_i turns on/off all the lights L_{i-D}...L_{i+D}, if they exist (This means that S_1 turns on/off all the lights L_1...L_{D+1} and S_n turns on/off all the lights L_{n-D}...L_n. Of course, if Dn, then L_{D+1} and L_{n-D} will not exist either.). Turning on or off lights can attract the attention of the guards, so Ryu would like to turn off all the lights with the minimum number of times flipping a switch. Can you help him out?

Giriş verilənləri

The first line of the input contains a single number: the number of test cases to follow. Each test case has the following format:

  • One line with two integers n (1n100) and D (0D15): the number of lights and the parameter mentioned above.

  • One line with n integers. The i^th integer describes the current state of light L_i, where 0 means off and 1 means on.

Çıxış verilənləri

For every test case in the input, the output should contain one integer on a single line: the minimum number of times Ryu needs to flip a switch to turn off all the lights. If it is impossible to turn off all the lights, then output the string "impossible" instead.

Example

In the first example below, flipping switch S_4 followed by S_7 will turn off all the lights.

Nümunə

Giriş verilənləri #1
2
7 3
1 1 1 0 0 0 0
5 1
1 0 1 0 1
Çıxış verilənləri #1
2
3
Mənbə ICPC BAPC 2011 Finals