990A. Commentary Boxes

ImplementationMathematics

Berland Football Cup starts really soon! Commentators from all over the world come to the event.

Organizers have already built n commentary boxes. m regional delegations will come to the Cup. Every delegation should get the same number of the commentary boxes. If any box is left unoccupied then the delegations will be upset. So each box should be occupied by exactly one delegation.

If n is not divisible by m, it is impossible to distribute the boxes to the delegations at the moment.

Organizers can build a new commentary box paying a burles and demolish a commentary box paying b burles. They can both build and demolish boxes arbitrary number of times (each time paying a corresponding fee). It is allowed to demolish all the existing boxes.

What is the minimal amount of burles organizers should pay to satisfy all the delegations (i.e. to make the number of the boxes be divisible by m)?

Hints

1. Can the boxes be equally distributed to the delegations?

2. If no, then will building more or demolishing boxes help?

3. Which approach would be economical?

Solution

Our objective is to make n divisible by m. So first we check if the given n is already divisible by m. If it is, then we needn’t do anything since our objective is already satisfied. Hence the answer is 0.

But if our objective isn’t satisfied we need to find a way which is more economical i.e building the required number of boxes or demolishing the required number of boxes to satisfy our objective.

To put it mathematically, the answer equals

$min(cost\ of\ construction \times (n\ mod\ m), cost\ of\ demolition \times (n-n\ mod\ m))$

Here (n%m) gives the number of boxes required to be build and (n-n%m) gives the number of boxes to be demolished to satisfy our objective.

Code

#include<bits/stdc++.h>
#define endl '\n'

int main() {
    ll n,m,a,b;
    cin >> n >> m >> a >> b;
    ll ans = 0;
    
    //Check if n is already divisible by m
    if(n%m==0){
        cout << 0 << endl;
        return 0;
    }
    
    //To find the most economical cost
    ans = min(b*(n%m), (m-n%m)*a);
    cout << ans << endl; 
}

Written by Aswanth