0

Maximize the average working ratio

Difficulty: MEDIUM
Contributed By
Archit Sharma
Avg. time to solve
15 min
Success Rate
85%

Problem Statement

You are given an array ‘BULBS’ of size ‘N’. There are ‘N’ shops and for each shop ‘i’, ‘BULBS[i] = [WORKS, TOTAL]’, where ‘WORKS’ is the number of working bulbs, and ‘TOTAL’ is the total number of bulbs in the shop ‘i’.

You are also given an integer ‘EXTRA’. These are the number of extra bulbs that are guaranteed to be working. You want to assign the extra bulbs to the shops in a way that maximizes the average working ratio across all the shops.

The working ratio of a shop is defined as ‘WORKS/TOTAL’. The average working ratio is the sum of the working ratios of all the shops divides by ‘N’. Your task is to find the maximum possible average working ratio.

Example:
‘N = 3’, ‘EXTRA = 2’
‘BULBS = [ [2, 3], [3, 5], [2, 2] ]
To get the maximum average working ratio, assign one bulb to shop ‘0’ and one bulb to shop ‘1’. So, the average working ratio will be equal to ‘(3/4 + 4/6 + 2/2) / 3 = 0.80556’.
Note:
1. The answers within ‘10^(-5)’ of the actual answer will be accepted.
2. You do not need to print anything, it has already been taken care of. Just implement the function.
Input format:
The first line of input contains an integer ‘T’ which denotes the number of test cases. Then, the ‘T’ test cases follow.

Each test case’s first line contains two integers, ‘N’ and ‘EXTRA’, denoting the number of shops and extra bulbs. Then, ‘n’ lines follow.
Each line contains two integers, ‘WORKS’ and ‘TOTAL’, denoting an element in the array ‘BULBS’.
Output format:
For every test case, return the maximum possible average working ratio. The printed output will be up to ‘5’ decimal places.
The output of each test case will be printed in a separate line.
Constraints:
1 <= T <= 10
1 <= N, EXTRA <= 10^3
1 <= WORKS <= TOTAL <= 10^5
Each element of ‘BULBS’ contains exactly two integers.

Where ‘T’ is the number of test cases, ‘N’ is the number of shops, ‘EXTRA’ is the number of extra bulbs, and ‘[WORKS, TOTAL]’ represents an element in the ‘BULBS’ array.

Time limit: 1 second

Sample input 1:

2
4 3
1 2
2 4
3 4
1 1
3 2
1 2
2 4
4 8

Sample output 1:

0.77500
0.58889

Explanation of sample input 1:

Test Case 1:
‘N = 4’, ‘EXTRA = 3’
‘BULBS = [ [1, 2], [2, 4], [3, 4], [1, 1] ]’

To get the maximum average working ratio, assign one bulb to shop ‘1’ and two bulbs to shop ‘3’. So, the average working ratio will be equal to ‘(3/4 + 3/5 + 3/4 + 1/1) / 4 = 0.77500’.

Test Case 2:
‘N = 3’, ‘EXTRA = 2’
‘BULBS = [ [1, 2], [2, 4], [4, 8] ]’

To get the maximum average working ratio, assign one bulb to shop ‘0’ and one bulb to shop ‘1’. So, the average working ratio will be equal to ‘(2/3 + 3/5 + 4/8) / 3 = 0.58889’.

Sample input 2:

2
3 3
1 2
2 3
3 4
3 5
1 1
2 2
3 3

Sample output 2:

0.75000
1.00000
Reset Code
Full screen
copy-code
Console