PREE05 - Editorial

editorial
, , ,
1

Problem Link:

Contest

Difficulty:

Easy

Pre-Requisites:

Mathematics

Problem:

George is fond of playing with balls.One day he found a bag in his home with N number of balls each having
a particular value Vi.He pick up a pair of balls from the bag randomly and increases their value by K and
put them in the bag again.He can increase the value of those pair of balls which have value less than or equal
to M(&lt=M) i.e. Vi + k , Vj+k .He perform picking up 2 balls until he was unable to choose 2 balls with value &lt=M
After performing all this stuff,he calculate the final total value he get from the bag.
TOTAL VALUE==&gt It is equal to the sum of the values of the all balls.

Now he wants to know,how many unique or different total values he can obtain by playing with balls in the bag.

Explaination:

A ball in bag can be incremented at most 1 + floor((M-Vi)/K )times.We need to find out the total sum of incrementation of all balls that can be obtained by one scan through array.Then remove the incrementation value of ball which can be incremented maximally from the sum calculated previously

Now find out the minimum of two values(sum,incrementation value of max incremented ball ).Output the (min/2) as answer.Check some base cases also.(Read the program)

So the algo for this problem is:

Take number N,M,K as input.
For each ball
   	calculate inc=(m-a/k) + 1 for all balls.
	calculate max of inc.
	get sum using sum+=inc. and max(inc).
subtract max from sum.
Output min(max and sum)/2. 

### Actual Program is:

#include&ltcstdio&gt
#include&ltalgorithm&gt
using namespace std;
typedef long long LL;

LL m,n,k,sum=0,a,maximum=0;

int main(){
	int t;
	scanf("%d",&t);
	while(t--)
	{
	maximum=0;
	sum=0;
	scanf("%lld %lld %lld",&n,&m,&k);
	LL i;
	for(i=0;i &lt n;i++){
		scanf("%lld",&a);
		a = (m-a)/k+1;
		if(maximum &lt a) maximum = a;
		sum+=a;

	}

	sum-=maximum;
	if(maximum &gt sum) maximum = sum;
	LL ans = maximum/2;
	if(!(sum&1)) ans++;

	printf("%lld\n",ans%1000000007);
	}
	return 0;
}
2

Can someone tell me whats the logic behind subtracting max from sum and the outputing min(sum,max)/2 ???

3

Detailed explanation can be found here: http://discuss.codechef.com/questions/24631/rrgame-editorial

4

i don’t understand why ans++ when sum is even , pls reply.