Providing gifts

You are given 

$N$ coins whose values are from $1$ to $N$. The value of each coin ranges from $1$ to $N$. You want to gift as many people as you can.

You also want to be fair with everyone and therefore, you prepare the gift such that each person can be gifted the same amount of money. You are allowed to put several denominations together in a gift. What is the maximum number of gifts that you can prepare?

Note: It does not make sense to prepare empty gifts.

Input format

• The first line contains $T$ denoting the number of test cases.
• The first and only line of each test case contains an integer $N$ as described in the problem statement.

Output format

For each test case, print a single integer consisting of the maximum number of gifts.

Constraints

$1\le T\le 20000$

$1\le N\le {10}^9$

SAMPLE INPUT

 

1
4

SAMPLE OUTPUT

 

2

Explanation

Suppose you decide that each gift should be worth 3 units. We can put (1,2) in one gift and (3) in another so we will have 2 gifts. There is no more optimal strategy.

Problem Link : https://www.hackerearth.com/practice/algorithms/greedy/basics-of-greedy-algorithms/practice-problems/algorithm/monotization-065bcc29/

Solution :

If N is even answer is N/2 else answer is (N-1)/2 +1.

We will always aim for making each gift of value N.

we will club (1,N-1) , (2,N-2) ....

Answer :

1. #include<bits/stdc++.h>
2. using namespace std;
3. #define FIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
4. #define mod 1000000007
5. #define endl "\n"
6. #define test ll t; cin>>t; while(t--)
7. typedef long long int ll;
8. int main() {
9. FIO;
10. test
11. {
12. ll n;
13. cin>>n;
14. ++n;
15. n/=2;
16. cout<<n<<endl;
17. }
18. return 0;
19. }

Test :

1. t = int(input())
2. while t > 0:
3. t -= 1
4. n = int(input())
5. print((n + 1) // 2)