Equal Division

★★★★★

3.3

7 votes

Algorithms, Easy, Greedy Algorithms, Recruit

Details

Submissions

Discussion

Editorial

Problem

There are $N$ teams in a software company. The $i^{th}$ team has $B_i$ employees in it and a total budget of $A_i$ units of money. Each team has to divide their budget within their employees equally. But for some teams, it's not possible to divide the budget equally.
Therefore, the company have to perform revisions in the teams' budget sizes.

In one revision, to revise the budget of $i^{th}$ team, the budget of the first $i$ teams has to be increased by $1$ .

Your task is to find the minimum number of revisions needed so that for each team, equal distribution of their budget among the employees is possible.

Constraints:

$1 \le N \le 10^5$
$0 \le A_i \le 10^9$
$1 \le B_i \le 10^9$

Input Format:

The first line contains an integer $N$ , denoting the number of teams.

Next $N$ lines contain two space-separated integers, $A_i$ and $B_i$ , each.

Output Format:

In a single line, print the minimum number of revisions needed so that for each team, equal distribution of their budget among the employees is possible.

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

Initially, the budges of the teams are $1$ , $3$ and $5$ .

In the first revision, the company will increase the budget for first $2$ teams by $1$ . This will make the budgets as $2$ , $4$ and $5$ .

In next $3$ revisions, the company will increase the budget of first $3$ teams by $1$ .

The final budgets will be $5$ , $7$ and $8$ which can now be equally distributed within each team.

You cannot achieve the equal distribution characteristic in less than four revisions.