Cin006-Editorial

PROBLEM LINK:Contest Page | CodeChef

Author: Rishab Soni
Tester: Rishab Soni
Editorialist: Rishab Soni

DIFFICULTY:

EASY

PREREQUISITES:

Modular Arithmetic, basic Maths

PROBLEM:

Sonal and Mamta are two friends and want to buy some chocolates which are sold at price z rupees per chocolate. Sonal has x rupees, mamta has y rupees. Each girl will buy as many chocolates as she can using only her money. This way each girl will buy an integer non-negative number of chocolates. The girls discussed their plans and found that the total number of chocolates they buy can increase (or decrease) if one of them gives several rupees to the other girl. The rupee can’t be split in parts, so the girls can only exchange with integer number of rupees.( 0.665 or 67.67 rupees not possible)

Consider the following example - Suppose sonal has 5 rupees, mamta has 4 rupees, and the price for one chocolate be 3 rupees. If the girls don’t exchange with rupees, they will buy 1+1=2 chocolates. However, if, for example, mamta gives sonal one rupee, then sonal will have 6 rupees, mamta will have 3 rupees, and the girls will buy 2+1=3 chocolates.

It is not that easy to live without chocolate now, so sonal and Mamta want to exchange with rupees in such a way that they will buy the maximum possible number of chocolates. Nobody wants to have a debt, so among all possible ways to buy the maximum possible number of chocolates find such a way that minimizes the number of rupees one girl gives to the other (it is not important who will be the person giving the rupees).

EXPLANATION:

  1. It’s easy to calculate how much chocolates we will buy: k= floor value of (x + y) /z (suppose that all money transferred to a single person,
    this way the number of bought coconuts would be clearly maximal)
  2. If k= floor value of ( x/z ) + floor value of ( y/z ) , then the answer is (k,0). The remaining case is a bit harder.
  3. Let’s notice, that there is no need to transfer ≥ z rupees, since the one transferring money could have used z rupees to buy one more chocolate herself.
  4. Also it’s optimal to transfer coins such that the remainder modulo z of the receiving part will turn to be exactly zero (we could have simply transfer less for the same effect)
  5. also k = k + ( x mod z + y mod z ) / z
  6. So the answer is k and min of (z−(x mod z),z−( y mod z )). ( mod means modular operator (%) ) or k and 0 ( if ( x mod z + y mod z ) / z is 0 )

SOLUTIONS:

Setter's Solution

#include <bits/stdc++.h>
#define ll long long int
using namespace std;

int main()
{
ll t,a,b,c,d,i,j,k,l,n,m,x,y,z;
scanf("%lld",&t);
while(t–){
cin>>x>>y>>k;
l=0;
l+=x/k;
l+=y/k;
a=x%k;
b=y%k;
z=0;
if(a+b>=k){
l++;
z=max(a,b);
d=k-z;
}
else
d=0;
cout<<l<<" "<<d<<endl;
}
}

Tester's Solution

#include <bits/stdc++.h>
#define ll long long int
using namespace std;

int main()
{
ll t,a,b,c,d,i,j,k,l,n,m,x,y,z;
scanf("%lld",&t);
while(t–){
cin>>x>>y>>k;
l=0;
l+=x/k;
l+=y/k;
a=x%k;
b=y%k;
z=0;
if(a+b>=k){
l++;
z=max(a,b);
d=k-z;
}
else
d=0;
cout<<l<<" "<<d<<endl;
}
}

Editorialist's Solution

#include <bits/stdc++.h>
#define ll long long int
using namespace std;

int main()
{
ll t,a,b,c,d,i,j,k,l,n,m,x,y,z;
scanf("%lld",&t);
while(t–){
cin>>x>>y>>k;
l=0;
l+=x/k;
l+=y/k;
a=x%k;
b=y%k;
z=0;
if(a+b>=k){
l++;
z=max(a,b);
d=k-z;
}
else
d=0;
cout<<l<<" "<<d<<endl;
}
}