← 返回题目列表

Codeforces · 1481/B

B. 新殖民地

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

到达目的地后,你想在新星球上建立一个新的殖民地。由于这个星球有许多山脉,而殖民地必须建立在平坦的表面上,因此您决定使用巨石将山脉夷为平地(您仍然在做梦,所以这对您来说是有道理的)。

给你一个数组 $$$h_1, h_2, \dots, h_n$$$,其中 $$$h_i$$$ 是第 $$$i$$$ 山的高度,$$$k$$$ - 你拥有的巨石数量。

你将从第一座山的山顶开始逐个投掷巨石,它们将如下滚动(假设当前山的高度为$$$h_i$$$):

- 如果$$$h_i \ge h_{i + 1}$$$,巨石将滚到下一座山;
- 如果$$$h_i < h_{i + 1}$$$,巨石将停止滚动并使山高增加$$$1$$$ ($$$h_i = h_i + 1$$$);
- 如果巨石到达最后一座山,它将落入废物收集系统并消失。

您想要找到第 $$$k$$$ 巨石的位置或确定它将落入废物收集系统。

输入

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

每个测试用例由两行组成。每个测试用例中的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 100$$$; $$$1 \le k \le 10^9$$$) - 山脉的数量和巨石的数量。

第二行包含 $$$n$$$ 整数 $$$h_1, h_2, \dots, h_n$$$ ($$$1 \le h_i \le 100$$$) — 山脉的高度。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$100$$$。

输出

对于每个测试用例,如果第 $$$k$$$ 巨石落入收集系统,则打印 $$$-1$$$。否则,打印第 $$$k$$$ 巨石的位置。

示例

输入 #1

4
4 3
4 1 2 3
2 7
1 8
4 5
4 1 2 3
3 1
5 3 1

输出 #1

2
1
-1
-1

注意

我们来模拟第一种情况:

- 第一个巨石从 $$$i = 1$$$ 开始;由于 $$$h_1 \ge h_2$$$ 它滚动到 $$$i = 2$$$ 并在那里停止,因为 $$$h_2 < h_3$$$。
- 新高度为$$$[4,2,2,3]$$$。
- 第二块巨石从 $$$i = 1$$$ 开始;由于 $$$h_1 \ge h_2$$$ 巨石滚动到 $$$i = 2$$$;由于 $$$h_2 \ge h_3$$$,巨石滚动到 $$$i = 3$$$ 并停在那里,因为 $$$h_3 < h_4$$$。
- 新高度为$$$[4,2,3,3]$$$。
- 第三块巨石从 $$$i = 1$$$ 开始;由于 $$$h_1 \ge h_2$$$ 它滚动到 $$$i = 2$$$ 并在那里停止,因为 $$$h_2 < h_3$$$。
- 新高度为$$$[4,3,3,3]$$$。

每块巨石停止的位置如下:$$$[2,3,2]$$$。

在第二种情况下,所有 $$$7$$$ 巨石将恰好停在第一座山的高度从 $$$1$$$ 上升到 $$$8$$$ 处。

第三种情况与第一种情况类似,但现在你会扔 $$$5$$$ 巨石。前三个将以与第一个测试用例相同的方式滚动。之后,山的高度将等于 $$$[4, 3, 3, 3]$$$,这就是为什么其他两块巨石将落入收集系统。

在第四种情况下,第一个也是唯一一个巨石将直接落入收集系统。