D. 蚂蚁竞走I
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
D. 蚂蚁竞走I
时间限制:1s
空间限制:64MB
本题分值:250
题目描述
蚂蚁竞走十年了!
一只蚂蚁处在草原上的某一点,不妨设为 \((0,0)\) ,它想通过若干移动,移动到点 \((x,0)\) 处。
给定一个长度为 \(n\) 的正整数数组 \(a_1,a_2,...,a_n\)。
蚂蚁能从给定数组中的某个元素的值作为步长,从一个点移动至另一个点,即两点之间的距离等于该 \(a_i\)。
请问,蚂蚁从 \((0,0)\) 到 \((x,0)\) 最少要走几步?
注意,蚂蚁可以移动到草原的任意位置( 不一定要走到格点 )。
例如,当 \(x=6,a={2,4,5}\) 时,\((0,0)→(2,0)→(6,0)\) 和 \((0,0)→(3,4)→(6,0)\) 和 \((0,0)→(4,0)→(6,0)\) 均为合理最佳方案之一。
输入格式
第一行包含整数 \(T\),表示共有 \(T\) 组测试数据。
每组数据第一行包含两个整数 \(n\) 和 \(x\)。
第二行包含 \(n\) 个整数 \(a_1\),\(a_2\),…,\(a_n\)。
输出格式
每组数据输出一行结果,表示最少步数。如若不能走到输出-1。
输入样例:
5
2 4
1 3
3 12
3 4 5
1 5
5
2 10
15 4
1 4
5
输出样例:
2
3
1
2
2
数据范围及限制
\(1\le T\le 100\)
\(1\le x\le 10^6\)
\(1\le a_i\le 10^5\)
\(i\neq j\to a_i\neq a_j\)
测试点编号 | 约定 | 测试点分值 |
---|---|---|
1 | \(n=1\) | 每个测试点50分 |
2~3 | \(1\le n\le 10^3,\sum n\le 10^3\) | 每个测试点40分 |
4~6 | \(1\le n\le 10^5,\sum n\le 10^5\) | 每个测试点40分 |
2021年互联网创新创业科技节程序设计大赛
- 状态
- 已结束
- 规则
- OI
- 题目
- 10
- 开始于
- 2021-12-23 17:30
- 结束于
- 2021-12-23 21:00
- 持续时间
- 3.5 小时
- 主持人
- 参赛人数
- 98