In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.
Byteasar wants to take a taxi from the town Bytehole to the town Bytepit,
which is kilometres away from Bytehole.
Exactly
kilometres along the way from Bytehole to Bytepit, there is
a base of
taxis, numbered from
to
.
The taxi no.
has enough fuel to drive exactly
kilometres.
Byteasar can change taxis at any point. All the taxis start at their base but need not return there. Your task is to determine whether Byteasar can be driven from Bytehole to Bytepit, and if so, what it the minimum number of taxis required for such a journey.
The first line of the standard input holds three integers,
,
, and
(
,
),
separated by single spaces.
Those denote, respectively: the distance from Bytehole to Bytepit,
the distance from Bytehole to the taxi base, and the number of taxis at
the base.
The second line of input contains
integers,
(
), separated by single spaces.
The number
denotes the maximum distance (in kilometres) that the
-th taxi can travel.
In tests worth 40% of all points an additional
condition holds.
Your program should print a single integer to the standard output:
the minimum number of taxis Byteasar has to take to get from
Bytehole to Bytepit. If getting there is impossible, your program should
print the number .
For the input data:
42 23 6 20 25 14 27 30 7
the correct result is:
4
Explanation of the example: Byteasar can take the taxis no. 4, 5, 1, and 2, in this order.
Task authors: Krzysztof Diks, Wojciech Rytter.
<Submit a solution> [0/100]