← 返回题目列表

Codeforces · 1566/A

A. 中值最大化

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

给你两个正整数 $$$n$$$ 和 $$$s$$$。找到 $$$n$$$ 非负整数(不一定不同)数组的最大可能中位数,使其元素之和等于 $$$s$$$。

长度为 $$$m$$$ 的整数数组的中位数是其元素非递减排序中位于 $$$\lceil {\frac{m}{2}} \rceil$$$ 第(向上舍入)位置的数字。职位编号从 $$$1$$$ 开始。例如,数组 $$$[20,40,20,50,50,30]$$$ 的中位数是 $$$[20,20,30,40,50,50]$$$ 的第 $$$\lceil \frac{m}{2} \rceil$$$ 个元素,因此它是 $$$30$$$。中位数还存在其他定义,但在这个问题中我们使用所描述的定义。

输入

输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例包含一行,其中包含两个整数 $$$n$$$ 和 $$$s$$$ ($$$1 \le n, s \le 10^9$$$) - 数组的长度和所需元素的总和。

输出

对于每个测试用例,打印一个整数 - 最大可能的中位数。

示例

输入 #1

8
1 5
2 5
3 5
2 1
7 17
4 14
1 1000000000
1000000000 1

输出 #1

5
2
2
0
4
4
1000000000
0

注意

前三个测试用例的可能数组(在每个数组中,中位数带有下划线):

- 在第一个测试用例中 $$$[\underline{5}]$$$
- 在第二个测试用例中 $$$[\underline{2}, 3]$$$
- 在第三个测试用例中 $$$[1, \underline{2}, 2]$$$