主页 讨论版 问题 名次 状态 统计

请自觉遵守比赛规则,违者严惩,不接受求情!

问题 A: Furude_Rika and coins

问题 A: Furude_Rika and coins

时间限制:10000 ms 内存限制:256 MB
提交:86 解决:31
[ 提交][ 状态][ 讨论版]

题目描述

Furude_Rika 有 $n$ 种硬币,每种硬币的价值都是一定的,且数量都是无限的。

现在有 $q$ 次查询,每次查询只有一个数字 $m$ ,求在只用不超过两种硬币,且使用硬币的总数不大于给定的一个数 $s$ 的条件下, 最少要多少枚硬币才能使他们的价值之和为 $m$。

如果无法构造出 $m$ 或者答案大于 $s$,则输出 $-1$。

输入

第一行两个数 $n,s$ $(n\le 5000,s\le 100)$ 代表硬币种数和给定的数

之后一行 $n$ 个整数(均小于等于 $100000$ 且大于 $0$) 代表对应的硬币的价值

之后一行一个整数 $q$ $(q\le 1000)$ 代表查询次数

之后q行每行一个整数 $m$ 代表查询的价值 $(q\le 1000,1\le m\le 10000000)$

输出

每行输出一个整数即为答案。

样例输入

6 20 10 50 100 500 1000 5000 8 4200 100000 95000 96000 99000 10100 2015 9950

样例输出

6 20 19 20 -1 3 -1 -1

提示

对于第一组4200的查询 很明显是用4枚1000的硬币和2枚100的硬币组成的 答案为6

而对于第一组99000的查询 很明显最少需要19枚5000的硬币和4枚1000的硬币 答案为23 由于大于s 则输出-1

有个很关键的点 s是在查询之前给的 而且只给了一次

另外 请注意时限

[ 提交][ 状态][ 讨论版]
Baidu
map