3710: 传递(第一轮04)
题目描述
两只小青蛙 A 和 B 想从河的一端跳到另一端， 它们分别选择了一条道路，每 条道路上都有 n 个石子，A 在第一条道路上进行跳跃，B 在第二条道路上进行 跳跃。双方不能跳到对方的道路上， 青蛙只能跳到石子上，不能跳到河里。青蛙 只能前进，不能后退，可以一次跳过多个石子，不必逐个石子向前跳。青蛙的跳 跃距离至多为 m ，但是他们有一个助跳器，可以让自己的跳跃距离上限变为 k(m < k)。
初始时跳跃器在青蛙 A 手中， 它们虽然不在一个道路上， 但是可以相互传递跳 跃器。即 A 可以将跳跃器传给 B，B 也可以将跳跃器传给 A。但是如果他们距 离之差超过 q(k < q)，则无法传递。
请问两只青蛙都跳到终点(第 n 个石子)最少需要传递几次助跳器？
保证相邻石子的距离之差小于 k，可以证明两只青蛙一定可以都抵达终点。
输入
第一行输入四个正整数 n, m, k, q 。
接下来一行包含 n 个正整数，分别表示第一只青蛙面前的 n 颗石头到起点的 距离，第 i 个正整数为 a i (1 ≤ ai ≤ 10^6 )，保证对于任意的 i，有 ai < ai+1 。
接下来一行包含 n 个正整数，分别表示第二只青蛙面前的 n 颗石头到起点的 距离，第 i 个正整数为 bi (1 ≤ bi ≤ 10^6 )，保证对于任意的 i，有 bi < bi+1 。
输出
输出一行一个整数表示答案。
样例输入 复制
4 2 5 10
5 10 15 20
2 4 6 8样例输出 复制
0提示
【样例 1 说明】
A 拿着助跳器直接跳到终点，而 B 面前的石子距离较近，可以直接跳，所以 B 可以不借助助跳器直接跳到终点。共传递 0 次助跳器。
【样例 2 输入】
4 2 5 10
5 10 15 20
5 10 15 20
【样例 2 输出】
2
【样例 2 说明】
青蛙 A 先走到第二颗石头（位置 10），此时将助跳器传递给青蛙 B；青蛙 B 跳 到终点（位置 20）再将助跳器传递给 A， A 跳到终点。
注意：若 A 直接跳到终点，则此时助跳器传递不到 B（因为两青蛙此时的距离 大于 q）， B 无法抵达终点。
【样例 3 输入】
4 2 5 6
4 8 12 14
5 10 15 20
【样例 3 输出】
3
【样例 3 说明】
A 跳一次之后传给 B，B 跳两次到 10，此时两青蛙距离是 10 − 4 = 6，刚好可 以传递，再由 B 传递给 A，让 A 一直跳到终点 （14）， A 再传递给 B 让 B 跳到终点。共传递 3 次。
【样例 4 输入】
4 3 6 7
4 5 9 11
5 11 16 19
【样例 4 输出】
3
【数据范围】
本题共有 10 个测试点
对于 1 − 2 的测试点，有 1 ≤ n, m, k, q ≤ 8
对于 3 − 4 测试点，有 an ≤ k
对于 5 − 7 测试点，有 1 ≤ n, m ≤ 80, m < k < q ≤ 300
对于 100% 的数据，有 1 ≤ n, m, k, q ≤ 1000, m < k < q