CLAW - Captain Claw
Captain Claw is at the bank of a river of acid and he needs to cross it. The river is x metres wide but Captain Claw can jump at most d metres.
However, the Captain can jump on stones which keep appearing in the stream.
Input
There are multiple test cases. For each test case.
The first line contains n, x and d.
The next n lines denotes subsequent seconds.
For each line, the first integer, c, denotes the number of number of stones appearing in this second.
Then c integers follow.
The ith integer means that a stone would appears at the position of that integer.
Find the minimum time needed by the Captain to cross the river.
1 <= t <= 30
1 <= x <= 10^5
1 <= d <= x
1 <= n <= 10^3
1 <= sum(c) <= 10^5
Assumption
Captain Claw is super fast. The time taken by jumps is negligible to a second.
Output
Print a single integer in each line - the time taken to cross the river.
Output -1 if its not possible to cross the river in n seconds.
Example
Input:
1
4 6 2
1 5
1 3
1 1
1 2
Output:
3
Explanation:
Sec 1: Captain Waits
Sec 2: Captain Waits
Sec 3: Captain Jumps from bank(0) → 1 → 3 → 5 → bank(6)
hide comments
alex2003top:
2023-10-20 05:22:28
I don’t understand why I don’t have a solution, can you tell me, my shipment number is 32051024? |
Added by: | sarfaraz |
Date: | 2016-01-20 |
Time limit: | 0.100s-1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 GOSU JS-MONKEY |