3918: 传递（transmit）
内存限制：512 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：74
解决：5
题目描述
transmit.in/out
小W和小Z 想从河的一端跳到另一端，它们分别选择了一条道路，每条道路 上都有 n个石头， 小W在第一条道路上进行跳跃，小Z 在第二条道路上进行跳跃。 双方不能跳到对方的道路上，他们只能跳到石头上，不能跳到河里。而且他们只能前 进，不能后退，可以一次跳过多个石头，不必逐个石头向前跳。他们跳跃的距离至多 为 m，但是他们有一个助跳器，可以让自己的跳跃距离上限变为k(mk)，则无法传递。
请问小W和小Z都跳到终点(第 n 个石头)最少需要传递几次助跳器？
保证相邻石子的距离之差小于 k，可以证明他们一定可以都抵达终点。
【样例 3 输入】
4 2 5 6
4 8 12 14
5 10 15 20
【样例 3 输出】
3
【样例 3 说明】
小W 跳一次之后传给小Z，小Z 跳两次到 10，此时两人距离是 10 − 4 = 6，刚
好可以传递，再由 小Z传递给小W，让 小W一直跳到终点（14），小W 再传递给 小Z 让小Z 跳到终点。共传递 3 次。
【样例 4 输入】
4 3 6 7
4 5 9 11
5 11 16 19
【样例 4 输出】
3
小W和小Z 想从河的一端跳到另一端，它们分别选择了一条道路，每条道路 上都有 n个石头， 小W在第一条道路上进行跳跃，小Z 在第二条道路上进行跳跃。 双方不能跳到对方的道路上，他们只能跳到石头上，不能跳到河里。而且他们只能前 进，不能后退，可以一次跳过多个石头，不必逐个石头向前跳。他们跳跃的距离至多 为 m，但是他们有一个助跳器，可以让自己的跳跃距离上限变为k(m
4 2 5 6
4 8 12 14
5 10 15 20
【样例 3 输出】
3
【样例 3 说明】
小W 跳一次之后传给小Z，小Z 跳两次到 10，此时两人距离是 10 − 4 = 6，刚
【样例 4 输入】
4 3 6 7
4 5 9 11
5 11 16 19
【样例 4 输出】
3
输入
第一行输入四个正整数 n,m,k,q。
接下来一行包含 n个正整数，分别表示小W面前的 n颗石头到起点的距离，第 i
个正整数为 ai (1 ≤ ai≤ 10
6 )，保证对于任意的 i，有 a[i]< a[i+1 ] 。
接下来一行包含 n个正整数，分别表示小Z面前的 n 颗石头到起点的距离，第i 个正整
数为 bi (1 ≤ bi≤ 10
6 )，保证对于任意的 i，有 b[i]< b[i+1 ]
【样例 1 说明】
小W拿着助跳器直接跳到终点，而小Z 面前的石子距离较近，可以直接跳，所
以可以不借助助跳器直接跳到终点。共传递 0 次助跳器
输出
输出一行一个整数表示答案。
【样例 2 说明】
小W 先走到第二颗石头（位置 10），此时将助跳器传递给小Z；小Z 跳到终
点（位置 20）再将助跳器传递给小W，小W跳到终点。
注意：若小W 直接跳到终点，则此时助跳器传递不到 小Z（因为两人此时的距离大于
q），小Z 无法抵达终点。
样例输入 复制
4 2 5 10
5 10 15 20
2 4 6 8样例输出 复制
0