← 返回题目列表

Codeforces · 1995/A

A. 对角线

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

Vitaly503 获得了一个棋盘,其一面为 $$$n$$$ 和 $$$k$$$ 筹码。他意识到所有这些 $$$k$$$ 芯片都需要放置在电路板的单元上(单个单元上不能放置超过一个芯片)。

让我们将第 $$$i$$$ 行和第 $$$j$$$ 列中的单元格表示为 $$$(i ,j)$$$。对角线是值 $$$i + j$$$ 相同的单元格集合。例如,单元格 $$$(3, 1)$$$、$$$(2, 2)$$$ 和 $$$(1, 3)$$$ 位于同一对角线上,但 $$$(1, 2)$$$ 和 $$$(2, 3)$$$ 则不然。如果对角线至少包含一个码片,则该对角线被称为已占用。

确定 $$$k$$$ 筹码的所有布局中占用的对角线的最小可能数量是多少。

输入

每个测试都包含多组输入数据。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 500$$$) - 输入数据的组数。然后遵循输入数据组的描述。

每组输入数据中唯一的一行包含两个整数 $$$n$$$、$$$k$$$ ($$$1 \le n \le 100, 0 \le k \le n^2$$$)——分别是棋盘的边长和可用筹码的数量。

输出

对于每组输入数据,输出一个整数——放置所有 $$$k$$$ 筹码后,他能得到的至少一个筹码占据的对角线的最小数量。

示例

输入 #1

7
1 0
2 2
2 3
2 4
10 50
100 239
3 9

输出 #1

0
1
2
3
6
3
5

注意

在第一个测试用例中,没有芯片,因此将占用 0 个对角线。在第二个测试用例中,两个芯片都可以放置在对角线上 $$$(2, 1), (1, 2)$$$,因此答案为 1。在第三个测试用例中,不能将 3 个芯片放置在一条对角线上,但将它们放置在 $$$(1, 2), (2, 1), (1, 1)$$$ 上会占用 2 个对角线。在第 7 个测试案例中,筹码将占据任何有效放置中的所有 5 个对角线。