Last Updated: 24 Nov, 2021
Milk flow
Moderate
Asked in companies
You are going to donate some milk to poor children. But being a busy person, you don’t have enough time to give milk to each child by yourself. To distribute the milk efficiently, you arrange children in the following structure and ask them to pass the milk.
Suppose you give 'X' liters of milk to child-1, then he will take 1 liter for himself and pass the remaining milk to child-2 and child-3 in equally half. Each child repeats the same process based on the amount of milk they get. If a child has less than 1 liter of milk, he doesn't pass anything to the next child.
E.g., If child-2 has 6 liters of milk, he keeps 1 liter for himself and passes 2.5 liters to child-4 and 2.5 liters to child-5. It can be seen that child-5 gets milk from child-2 and child-3 both. But he can take a total of 1 liter for himself and have to pass the remaining.
If 'X' liters of milk is given to child-1, find the amount of milk a child has, standing in the 'N'-th row (from top to bottom) at 'M'-th position (from left to right).
Input Format:
The first line contains 'T', denoting the number of tests.
For each Test :
The only line contains three space-separated integers 'X', 'N' and 'M', denoting amount of milk, row number and position of child from left, respectively.
Output Format:
For each test, print one floating number (with 6 digits of precision), denoting the amount of milk a child has, standing in 'N'-th row at 'M'-th position.
Note:
You are not required to print the expected output. It has already been taken care of. Just implement the function.
Constraints -
1 <= 'T' <= 10
1 <= 'M' <= 'N' <= 10^3
0 <= 'X' <= 10^4
Sum of 'N' and sum of 'M' over all test cases doesn't exceed 10^3.
Time Limit: 1 sec
Approaches
Approach: The number of children in i-th row is equal to the number 'i'. Thus, total number of children till i-th row (inclusive) is i*(i+1)/2.
Maintain a 'dp' of size N*(N+1)/2 to store the amount of milk each child has till N-th row.
Run two nested loops, the outer one to iterate row number and the inner one for positions in a particular row. Assign all the milk to the first child and start distributing as mentioned in the problem.
Algorithm:
- Initialize a dp of size N*(N+1)/2, having all values as 0.
- Assume the first child at index 0, and assign all milk to him.
- Iterate a for loop, row = 1 to N-1.
- Iterate a for loop, col = 1 to 'row'.
- Check the total amount of milk the current child has.
- If it is more than 1 liter, take the extra amount from him.
- Assign the extra amount to two following children in the next row, which will be at positions (index+row) and (index+row+1) in dp.
- Move to the next index in the dp.
- Iterate a for loop, col = 1 to 'row'.
- Now, find the position of the target child in dp.
- Till (N-1)'th row there are a total N*(N-1)/2 children.
- We need M-th child, so add M-1 in this number as children are assigned from index 0 in dp.
- The amount of milk our target child has dp[N*(N-1)/2 + M-1].
- If the amount is not more than 1 liter, return it, else return 1.0.