← 返回题目列表

Codeforces · 2072/A

A. 新世界,新我,新阵列

中文机器翻译题面 查看原题

夏目秋人刚刚在新世界醒来,立刻就接到了第一个任务!系统为他提供了一个由$$$n$$$个零组成的数组$$$a$$$、一个整数$$$k$$$和一个整数$$$p$$$。

在一次操作中,Akito 选择两个整数 $$$i$$$ 和 $$$x$$$,使得 $$$1 \le i \le n$$$ 和 $$$-p \le x \le p$$$,并执行赋值 $$$a_i = x$$$。

Akito还没有完全习惯控制他的新身体,所以帮他计算一下使数组中所有元素的总和等于$$$k$$$所需的最少运算次数,或者告诉他这是不可能的。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。

每个测试用例的唯一行包含三个整数 $$$n$$$, $$$k$$$, $$$p$$$ ($$$1 \le n \le 50$$$, $$$-2500 \le k \le 2500$$$, $$$1 \le p \le 50$$$) — 数组的长度,所需的总和以及段的边界可以从中替换数字。

输出

对于每个测试用例,输出实现数组中最终总和 $$$k$$$ 的最小操作数,如果无法实现总和 $$$k$$$,则输出 $$$-1$$$。

示例

输入
复制

8
21 100 10
9 -420 42
5 -7 2
13 37 7
10 0 49
1 10 9
7 -7 7
20 31 1

输出
复制

10
-1
4
6
0
-1
1
-1

注意

在第五个示例中,数组的和最初为零,因此不需要任何操作。

在第六个示例中,我们可以实现的数组中的最大和为$$$9$$$(通过将数字$$$9$$$分配给单个元素),因此无法通过任何操作获得和$$$10$$$。

在第七个示例中,仅需要一次操作$$$a_3 = -7$$$。