POWERCAR - Car with powers

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

 


Added by:cegprakash
Date:2014-03-10
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM32-GCC MAWK BC BF C NCSHARP C++ 4.3.2 CPP14 COBOL COFFEE D-CLANG D DART ELIXIR FANTOM FORTH GOSU GRV JULIA KTLN LUA NODEJS OBJC OCAML OCT PIKE PROLOG PYPY3 PYTHON3 R RACKET RUST CHICKEN ST SQLITE SWIFT UNLAMBDA

hide comments
2014-03-30 09:01:07 silence_dogood
all problems were with memset :/ carelessness cost me 4 WA
good problem :D (y)

Last edit: 2014-03-30 09:03:05
2014-03-30 07:57:48 xZiOn
wrong answer only on 16th case?...
2014-03-29 19:06:50 cegprakash
silence_dogood: In Spoj, your solution will be tested for all the test files though your code fails for the first test case.
2014-03-29 17:42:53 silence_dogood
getting wrong answer at the 16th case :/ any corner cases??
2014-03-29 16:20:39 Being Human
Finally AC!!! good one..!!!
2014-03-29 10:34:03 cegprakash
Stop giving free hints on comments!
2014-03-29 11:10:09 vivek n



Last edit: 2014-03-29 10:42:55
2014-03-29 02:44:44 sankar
I think "The Terminator" is correct...
2014-03-29 02:27:33 The Terminator
if the car is allowed to ride off track then there is always a solution right??
plz correct me if i am wrong...
2014-03-28 19:59:16 cegprakash
Simple recursion will TLE. Check the input constraints and think accordingly.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.