ZOJ Problem Set - 3799
How narrow the bicycle garage in ZJU is! Every time when LBH finishs his class going to take out his bicycle, he will find his beloved bicycle squeezed among other bikes.However, As narrow as the garage is, Only by clearing out the space that are twice the size of the bike's width can a bike be removed. So if he wants to take out his bike, he has to move a number of bikes in order.What a pity boy! You know that LBH is a lazy boy, so he hope you can help him to solve this problem calculating the minimum number of bikes he has to remove(including his own bike).
To simplify this problem, we assume that bikes in garage are arranged in a single line. A bike can be removed only when the space is more than twice the space of its width.(the left side space of bike + the right side space of bike >= bike width). And LBH just removes the bikes out of the garage. There were several space amomg the bikes. The both ends of the bike line are considered as areas that have infinite space.
There are several test cases.
The first line contains an integer T .
Then T test cases follow.
In each test case, the first line contains two integers n, m(0< n, m <=1000000). The number of total bikes and the index in the following sequence which represents the LBH's bike
And the second line is a sequence containing n numbers ai(0<|ai|<=1000000, 1<=i<=n) represent the width of either bikes or spaces. It represents a space when ai<0 while it represents a bike when ai>0.
For each test case, output one line with the minimum number of bikes LBH need to remove(including his own bike).
2 3 2 1 3 2 10 6 1 -1 4 -2 1 7 1 1 1 1
The cases 1 1. remove position 1 bike 2. remove position 2 LBH's bike The cases 2 1. remove position 5 bike 2. remove position 3 bike 3. remove position 6 LBH's bike
Author: LIN, Binghui
Source: ZOJ Monthly, August 2014