Submit | All submissions | Best solutions | Back to list |
POWERCAR - Car with powers |
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. |