Milk flow

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
2 upvotes
Asked in companies
AmazonD.E.Shaw

Problem statement

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).

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
2 2 1
8 3 2
Sample Output 1:
0.500000
1.000000
Explanation for Sample Input 1:
For case 1:
A child standing in N = 2 at M = 1, i.e., in the second row at first position, is child-2. A total of 2 liters of milk is given to child-1. He keeps one liter for himself and passes 0.5 liters to child-2 and child-3 each. Hence child-2 has 0.5 liters of milk.

For Case 2:
A child standing in N = 3 at M = 2, i.e., in the third row at second position, is child-5. 
child-1 gets 8 liters and passes 3.5 liters to child-2 and child-3 each.
child-2 gets 3.5 liters from child-1 and passes 1.25 liters to child-4 and child-5 each.
child-3 gets 3.5 liters from child-1 and passes 1.25 liters to child-5 and child-6 each.
child-5 gets a total of 2.5 liters (1.25 from child-2 and 1.25 from child-3). He keeps 1 liter and passes the remaining to the next. Hence child-5 has 1 liter of milk.
Sample Input 2:
3
6 3 3
6 4 2
1 2 2
Sample Output 2:
0.750000
0.250000
0.000000
Hint

Implement the flow of milk from the first row to N-th row.

Approaches (1)
Brute Force

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.
  • 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.
Time Complexity

O(N ^ 2), where ‘N’ is the row number of the target child.

We calculate the amount of milk for each child till N-th row. There are total N*(N+1)/2 children. Hence, overall time complexity becomes O(N ^ 2).

Space Complexity

O(N ^ 2), where ‘N’ is the row number of the target child.

We maintain a dp of size N*(N+1)/2. Hence, overall space complexity becomes O(N ^ 2).

Code Solution
(100% EXP penalty)
Milk flow
Full screen
Console