308632: CF1550A. Find The Array
Memory Limit:256 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Find The Array
题意翻译
一个数组 $a$ 是好的当且仅当数组内每一个数 $a_i$ 满足: - $a_i = 1$ - $a_i - 1 \in a$ - $a_i - 2 \in a$ 其中之一。现在给出一个好的数组 $a$ 的元素和 $S$,询问 $a$ 数组最少有几个数。题目描述
Let's call an array $ a $ consisting of $ n $ positive (greater than $ 0 $ ) integers beautiful if the following condition is held for every $ i $ from $ 1 $ to $ n $ : either $ a_i = 1 $ , or at least one of the numbers $ a_i - 1 $ and $ a_i - 2 $ exists in the array as well. For example: - the array $ [5, 3, 1] $ is beautiful: for $ a_1 $ , the number $ a_1 - 2 = 3 $ exists in the array; for $ a_2 $ , the number $ a_2 - 2 = 1 $ exists in the array; for $ a_3 $ , the condition $ a_3 = 1 $ holds; - the array $ [1, 2, 2, 2, 2] $ is beautiful: for $ a_1 $ , the condition $ a_1 = 1 $ holds; for every other number $ a_i $ , the number $ a_i - 1 = 1 $ exists in the array; - the array $ [1, 4] $ is not beautiful: for $ a_2 $ , neither $ a_2 - 2 = 2 $ nor $ a_2 - 1 = 3 $ exists in the array, and $ a_2 \ne 1 $ ; - the array $ [2] $ is not beautiful: for $ a_1 $ , neither $ a_1 - 1 = 1 $ nor $ a_1 - 2 = 0 $ exists in the array, and $ a_1 \ne 1 $ ; - the array $ [2, 1, 3] $ is beautiful: for $ a_1 $ , the number $ a_1 - 1 = 1 $ exists in the array; for $ a_2 $ , the condition $ a_2 = 1 $ holds; for $ a_3 $ , the number $ a_3 - 2 = 1 $ exists in the array. You are given a positive integer $ s $ . Find the minimum possible size of a beautiful array with the sum of elements equal to $ s $ .输入输出格式
输入格式
The first line contains one integer $ t $ ( $ 1 \le t \le 5000 $ ) — the number of test cases. Then $ t $ lines follow, the $ i $ -th line contains one integer $ s $ ( $ 1 \le s \le 5000 $ ) for the $ i $ -th test case.
输出格式
Print $ t $ integers, the $ i $ -th integer should be the answer for the $ i $ -th testcase: the minimum possible size of a beautiful array with the sum of elements equal to $ s $ .
输入输出样例
输入样例 #1
4
1
8
7
42
输出样例 #1
1
3
3
7