ALIEN3  Aliens at the subway
The female Alien moved to the biggest city in the world, this city has a giant subway system, this subway is always full of people, the Alien doesn't want to see humans and she wants to stay the least time possible in the subway system.
Preventing this scenario, the Alien brought from her planet some interesting and very rare objects, she calls this objects “Portable Teleporters”, with these objects the alien is on the capacity to teleport and ignore the next K stations, as you may know, this objects are limited and it can be used once.
As the city is so big that the subway is always full, she wants to stay the least number stations as possible, the Alien will start from station 0, wishing to go up to an station L, the subway is formed by N+1 (0 through N) stations and the Alien has K “Portable Teleporters”.
When the Alien uses a “Portable Teleporters” she will be teleported immediately to the I+Kj station, being I the station the alien was on and Kj the value of the Portable Teleporter.
If she is unable to use a teleporter or is better for her to go into the next station using the subway, she can do it, however, she can only move forward, NEVER backwards, furthermore, the Alien may not leave the limits of the stations (that means she can't go to any station before station 0 or any station after station N).
As you may know, the Alien doesn't wants to see a large number of people, to prevent this, she wants to visit as maximum T stations, if she can't reach her destination on T stations, she will simply exit the subway and will start walking on the city.
Your task is simple, given the N stations, the K objects and their values and the station the Alien wants to go, the L station the alien wants to go and the T number of tries, output the least stations visited so she can reach her destination.
INPUT:
The Input will start with an integer P denoting the test cases, then P cases will follow, each case have three lines, the first line contains two integers N and K, denoting the N stations and the K portable teleporters, next line will contain K integers, denoting the value of each teleporter, the last line for each case will contain two integers L and T, that it will be the last station the alien wants to go and the T number of stations she wants to visit as maximum.
OUTPUT:
The output will consists on P lines, each line containing the string "Scenario #i: " where i is the test case you're analyzing (starting by 1), followed by the minimum stations visited by the Alien to reach her destination, if she can't reach her destination on maximum T stations, print 1.
INPUT 
OUTPUT 
4 12 6 12 6 10 2 10 2 
Scenario #1: 4 
"Blank line between input sample data is just for clarification and understanding of the problem"
Explanation of the first test case:
She teleports from station 0 to station 4 using the third teleporter, from 4 to 7 using the second teleporter, from 7 to 9 using the fifth teleporter and she can either walk to the next station or use another teleporter.
Explanation of the last case:
She can't reach the station 10 going through only 5 stations, the answer should be then 1.
CONSTRAINTS:
1 <= P <= 50
1 <= N <= 100
1 <= K <= 17
100 <= Ki <= 100
0 <= L <= N
1 <= T <= 50
hide comments
and_roid:
20170723 21:18:42
Similar to http://www.spoj.com/problems/RIOI_2_3/.


Vipul Srivastava:
20170415 21:28:56
. Last edit: 20170415 21:39:47 

kshubham02:
20170323 07:19:02
AC in one go!


dunnohyet:
20140929 19:23:11
getting wa!! any trickey cases?? 

kojak_:
20140924 05:39:27
AC on first try xD


Rocker3011:
20130105 00:47:30
Take care about the limits, it is from 0 to N. Many many W.A because of this 

Vimal Raj Sharma:
20120706 05:58:54
Completely lost :(, problem setter is everything ok with input ? I am getting right answer for every input I am trying, but still WA, please check my submission #7267501 I can't find why it is giving WA. 

david_8k:
20120706 01:38:04
@Mehmet:


mehmetin:
20120705 17:54:00
Two questions,


Vimal Raj Sharma:
20120704 19:19:00
what will be the output for this

Added by:  david_8k 
Date:  20120628 
Time limit:  0.600s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Own problem 