Submit | All submissions | Best solutions | Back to list |
CHICKEGG - Chicks |
There are n hens in a farm. The egg laying ability of all the hens decreases by 1 day after each time they lay an egg. (i.e. every hen will lay the next egg 1 day slower than the time it took to lay the previous egg)
Let the initial egg laying ability of Hen[i] be D[i].
- Hen[i] lays its first egg on D[i]th day.
- Hen[i] lays its second egg on 2*D[i]+1 th day.
- Hen[i] lays its third egg on 3*D[i]+3rd day.
- Hen[i] lays its fourth egg on 4*D[i]+6th day.
- Hen[i] lays its fifth egg on 5*D[i]+10th day.
and so on.
Given n - the number of hens and the array D - the initial egg laying ability of the hens, find the minimum number of days required to produce at least K eggs. You can safely assume that eggs neither gets damaged nor converted into hens.
Input
The first line consists of integers t, the number of test cases. For each test case, the first line consists two integers n and K. The next line consists of n integers representing the initial egg-laying ability of the hens.
Output
For each test case, find the minimum number of days required to produce at least K eggs.
Constraints
1 <= t <= 10^2
1 <= n <= 10^3
1 <= K <= 10^8
1 <= D[i] <= 10^8
Example
Sample Input: 3 1 4 1 2 5 2 5 5 1000000 1 2 3 4 5 Sample Output: 10 11 20000500003
Explanation of Test case #2
There are 2 hens and we need to produce 5 eggs
At time 2, Hen 0 lays an egg.
At time 5, Hen 0 and Hen 1 lay an egg each.
At time 9, Hen 0 lays an egg
At time 11, Hen 1 lays an egg.
Added by: | cegprakash |
Date: | 2015-01-06 |
Time limit: | 5s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: BF GOSU SCM qobi |
hide comments
2015-02-01 05:00:28 cegprakash
Let 'a' be the initial egg hatching ability of a hen. First egg will be laid on ath day, Second egg on a + (a+1)th day, third egg on a+(a+1)+(a+1+1)th day and so on.. Last edit: 2015-02-01 05:43:58 |
|
2015-02-01 04:51:18 mala da.... annamala
how does the hen 0 lay the second egg at 5th day? after it lays its egg at d[0]=2, d[0] becomes 3. So it should lay its second egg on 2*d[0]+1 = 2*3+1=7th day right? Last edit: 2015-02-01 04:55:00 |