← 返回题目列表

Codeforces · 1550/A

A. 查找数组

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

如果从 $$$1$$$ 到 $$$n$$$ 的每个 $$$i$$$ 都满足以下条件,那么我们称一个由 $$$n$$$ 正(大于 $$$0$$$)整数组成的数组 $$$a$$$ 为美丽数组:要么 $$$a_i = 1$$$,要么 $$$a_i - 1$$$ 中的至少一个数字和$$$a_i - 2$$$ 也存在于数组中。

例如:

- 数组 $$$[5, 3, 1]$$$ 很漂亮:对于 $$$a_1$$$,数字 $$$a_1 - 2 = 3$$$ 存在于数组中;对于$$$a_2$$$,数组中存在数字$$$a_2 - 2 = 1$$$;对于 $$$a_3$$$,条件 $$$a_3 = 1$$$ 成立;
- 数组 $$$[1, 2, 2, 2, 2]$$$ 很漂亮:对于 $$$a_1$$$,条件 $$$a_1 = 1$$$ 成立;对于每个其他数字 $$$a_i$$$,数字 $$$a_i - 1 = 1$$$ 存在于数组中;
- 数组 $$$[1, 4]$$$ 并不美观:对于 $$$a_2$$$,数组中既不存在 $$$a_2 - 2 = 2$$$ 也不存在 $$$a_2 - 1 = 3$$$,并且 $$$a_2 \ne 1$$$;
- 数组 $$$[2]$$$ 并不美观:对于 $$$a_1$$$,数组中既不存在 $$$a_1 - 1 = 1$$$ 也不存在 $$$a_1 - 2 = 0$$$,并且 $$$a_1 \ne 1$$$;
- 数组 $$$[2, 1, 3]$$$ 很漂亮:对于 $$$a_1$$$,数字 $$$a_1 - 1 = 1$$$ 存在于数组中;对于 $$$a_2$$$,条件 $$$a_2 = 1$$$ 成立;对于 $$$a_3$$$,数组中存在数字 $$$a_3 - 2 = 1$$$。

给你一个正整数$$$s$$$。求一个漂亮数组的最小可能大小,其元素总和等于 $$$s$$$。

输入

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

然后是 $$$t$$$ 行,第 $$$i$$$ 行包含第 $$$i$$$ 测试用例的一个整数 $$$s$$$ ($$$1 \le s \le 5000$$$)。

输出

打印 $$$t$$$ 整数,第 $$$i$$$ 个整数应该是第 $$$i$$$ 个测试用例的答案:元素总和等于 $$$s$$$ 的漂亮数组的最小可能大小。

示例

输入 #1

4
1
8
7
42

输出 #1

1
3
3
7

注意

考虑示例测试:

1. 在第一个测试用例中,数组$$$[1]$$$满足所有条件;
2. 在第二个测试用例中,数组 $$$[3, 4, 1]$$$ 满足所有条件;
3. 在第三个测试用例中,数组$$$[1, 2, 4]$$$满足所有条件;
4. 在第四个测试用例中,数组 $$$[1, 4, 6, 8, 10, 2, 11]$$$ 满足所有条件。