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