2021年京东数据分析工程师秋招笔试编程题

小A养狗

小A很爱狗狗，也想要领养一只狗狗。

狗狗福利院可以找到很多狗狗，小A对其中的每只狗狗都有一个喜爱值，每只狗狗也都有领养成本。

小A是一个爱狗狗的人，如果他领养了狗狗，就要好好喂养它，所以小A还给每只狗狗计算好了其每个月所需要的喂养成本。

小A可以用于领养狗狗的预算有限，每个月能用于喂养狗狗的预算也有限。他希望你能帮忙找到一只两种成本均不高于预算且喜爱值最高的狗狗。

小A的喂养预算会因他对狗狗的喜爱程度而改变，具体计算方法如下：

1、 所有狗狗的喜爱值从低到高排序后的排名依次为1、2、3、…、n；

2、 设定一个预算系数d，每只狗狗对应的每月喂养预算值为 d/n × 排名

第一行有3个正整数n k d，表示能找到的狗狗数量、领养狗狗的预算和喂养狗狗的预算系数；
第二行有n个正整数a1、a2、…、an，表示小A对每只狗狗的喜爱值。
第三行有n个正整数b1、b2、…、bn，表示每只狗狗的领养成本。
第四行有n个正整数c1、c2、…、cn，表示每只狗狗的每月喂养成本。
数字间均有空格隔开
0 ≤ ai, bi, ci, k, d ≤ 107，保证ai两两不同。
1 ≤ n ≤ 10000。

输出描述
输出一行一个整数，表示小A能力范围内能领养到的最喜爱的狗狗所对应的喜爱值。如果没有小A可以领养的狗狗，输出-1。

样例输入
5 100 100
1 2 3 4 5
30 60 90 120 150
11 22 44 88 176
样例输出
3

提示
样例解释
五只狗狗的喂养预算依次为20、40、60、80、100，小A的领养预算能够支持他选择喜爱值为1、2、3的狗狗，喂养预算能够支持他选择喜爱值为1、2、3的狗狗，所以小A能力范围内能领养到的最喜爱的狗狗所对应的喜爱值为3。

K次行动

时间限制： 3000MS
内存限制： 589824KB

题目描述：
小明在一条直线上执行任务，需要在坐标0的位置和坐标a的位置之间来回移动。每次行动小明需要从0移动到a，或者从a移动到0。每移动1个单位坐标，小明携带的仪器需要耗费对应1个单位的能量。携带的仪器最多可装b个单位能量，初始时仪器是满能量。坐标0和a之间有一处坐标f位置可以给仪器充能。现在小明从0移动至a或者从a移动至0都算一次行动。请问小明从0出发，希望完成k次行动，最少需要在f坐标处充能多少次。

输入描述 一行4个空格隔开的数字a、b、f、k，

0<f<a<=10^6，1<=b<=109，1<=k<=10^4，含义如题。

输出描述 一行一个数字，表示最小的充能次数，如果不能完成k次，输出-1。

样例输入
6 9 2 4
样例输出
4

提示 样例2：

输入样例：6 10 2 4

输出样例：2

样例3：

输入样例：6 5 4 3

输出样例：-1