Need Help in CHOCOPRO

I was trying to solve the problem CHOCOPRO in KJCS2019 but i am not able to get the approach behind the problem .

Given X chocolates, you have to divide them among N children such that it fulfills the given condition. Note that the number of chocolates that each child receives should be distinct. Also, the gap between the number of chocolates each child receives should remain constant. So we can think of the problem as an Arithmetic Progression where X is the sum of all elements of the AP and N is the number of elements of the AP. Also, if there are multiple answers possible, we need to minimize the number of chocolates the first child receives, say a.

From the sum of elements of an AP, S = \frac{n}{2}[2*a+(n-1) d] ( where n = number of elements of the AP, a = first term of the AP and d = common difference of the AP ) , we can try out for all values of a where 1 \le a \le X and check whether there is any satisfactory integer value of d. If it exists, we print ‘Y’ and the corresponding value of A else we print ‘N’.

int x,n;cin>>x>>n;int ans=-1;
for(int a=1;a<=x;a++){
int d=(2*x-2*n*a)/(n*(n-1));
if(d>=1)if(2*n*a+(n*n-n)*d==2*x){ans=a;break;}
}
if(ans==-1)cout<<"N\n";
else cout<<"Y "<<ans<<"\n";


its simple brute force,try every value of a until x as we have to find minimum start from 1, notice d>=1 guarantees distinct element.

Hey nvdrag_123!
I was reading this sol. What do you think of the value of a in formula of sum of n terms of AP. Will it always lie between 1 and n (as he wrote in solution) or can it be greater than n?

actually ans lies between [1,n-1], lets say we assume a=n+x where x>0 ,
then S=(2(n+x)+(n-1)d)=(2a’+(n-1)d’)
here a’<n then assume , n+x-t=a’,
also,then 2*t must be multiple of (n-1),
if t is a multiple of (n-1) then, there will always exists a solution a’<n.

Thanks to all of you @anon49701446 @nvdrag_123 @humblejumbo

1 Like

Didn’t got you!
(20 characters)

its very simple lets say a>n and a’<n then ,a’=a-t , for some t ,
now put the values in S=n/2(2a+(n-1)d) = n/2( 2a’ + 2*t + (n-1)d) ,
now if t=(n-1)*p for some p>=0 i.e, multiple of (n-1) then, for d’=d+2p , there will always
exist a solution for a’ .so S=n/2(2a’ + (n-1)(d+2p))

I got it very well
.