POWERCAR - Car with powers

no tags 

Car with Powers race track

The race track is a straight line with starting point at Track[0] and ending point at Track[n-1]. The car is initially at Track[0].

Track[i]='#' if the track has a wall at Track[i].

The car can move from Track[i] to Track[i+1] if and only if Track[i+1] is not a wall. The time taken to move from Track[i] to Track[i+1] is 1 unit.

If there is a wall at Track[i+1], you can shoot it from Track[i] if you have enough bullets in the car. Once a bullet is fired, the bullets count will decrease by 1. The time required to fire a bullet is 0.

It is also allowed to ride the car off the track. It's allowed to move from Track[i] to offTrack[i], from offTrack[i] to offTrack[i+1] and from offTrack[i] to Track[i] (if Track[i] is not a wall). The time taken for any of these steps is 2 units.

Find the fastest possible time to finish the race. Print "Impossible" if it's impossible to finish the race.

Input:

The first line consists of an integer t, the number of test cases. For each test case, the first line consists of two integers the length of race track n and the number of bullets the car can fire followed by a line with a string representing the Track.

Output:

For each test case, print the expected result as specified in the problem statement.

Input Constraints:

1 <= t <= 100

2 <= n <= 1000

0 <= bullets <= 1000

Track[i] ∈ {'S','E', '0', '#'}

Track[0]='S', Track[n-1]='E'

Sample Input:

10
7 3
S00000E
2 2
SE
4 1
S00E
8 1
S0000##E
8 3
S0#00#0E
7 2
S0#0##E
10 4
S00#0#0##E
5 2
S000E
7 1
S0##00E
9 0
S0000##0E

 

Sample Output:

6
1
3
13
7
12
9
4
12
15

 


hide comments
achint mittal: 2017-02-21 14:08:37

Came to this question after 2 years, AC in 1 go!!! feels good!!

ALi Ibrahim: 2016-05-26 14:12:26

Finally Accepted, After about 6 hours of debugging and 7 WA!!! but i really did enjoy it :D

anuveshkothari: 2015-08-13 13:12:52

awesome [spoiler] problem..

Last edit: 2016-07-29 22:39:37
:(: 2015-04-02 14:57:37

2nd even with cin and cout.... Awesome problem ;)

Nebojsa: 2015-03-28 17:49:59

When is it impossible to finish the race?

MaHmOuD.: 2015-03-11 02:27:14

Last edit: 2015-03-12 15:53:38
Vikas Yadav: 2014-06-26 19:59:09

AC in one go!! :D

Agam Gupta: 2014-06-04 00:21:48

Awesome Problem !!

785227: 2014-05-10 13:22:40

Awesome problem. Learnt a new thing :)


Added by:cegprakash
Date:2014-03-10
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: BF GOSU