CANDY - Candy I Editorial or Solution SPOJ - UCS - Unleash-Coding-Skills

Saturday, 7 April 2018

CANDY - Candy I Editorial or Solution SPOJ - UCS

CANDY - Candy I

Jennifer is a teacher in the first year of a primary school. She has gone for a trip with her class today. She has taken a packet of candies for each child. Unfortunatelly, the sizes of the packets are not the same.
Jennifer is afraid that each child will want to have the biggest packet of candies and this will lead to quarrels or even fights among children. She wants to avoid this. Therefore, she has decided to open all the packets, count the candies in each packet and move some candies from bigger packets to smaller ones so that each packet will contain the same number of candies. The question is how many candies she has to move.

Input specification

The input file consists of several blocks of data. Each block starts with the number of candy packets N(1<= N <=10000) followed by N integers (each less than 1000) in separate lines, giving the number of candies in each packet. After the last block of data there is the number -1.

Output specification

The output file should contain one line with the smallest number of moves for each block of data. One move consists of taking one candy from a packet and putting it into another one. If it is not possible to have the same number of candies in each packet, output the number -1.

Example

Input file:
5
1
1
1
1
6
2
3
4
-1

Output file:
4
-1
 

Link to this problem:

http://www.spoj.com/problems/CANDY/

Explanation:

In this problem we need to find number of candies have to move from one packet to other so that all packets must contain same number of candies.

Step1: Take input as given in input data.
Step2 : Sum or total number of candies in the packets.
step3: Total number candies in each packet = (sum)/n where n is total number  of packets.Let answer of (sum)/n is stored again in sum.
step4: Here take two variable less and more with initial values as 0.
 if sum>array element or value then add to more i.e., more = more+(sum-array element value).
if sum < array element or value then add to less i.e., less = less + (array element value - sum).
step5: If less not equal to more then it is not possible to make equal candies in all packets with given input.
step6: Otherwise print the candies required is either less or more.

Note: While taking input the end of input is indicated with "-1" so take care about the input format.

CPP code for the problem is:

#include <iostream> #include <cstdio> using namespace std; int main(void) { long long i,j,k,n,sum,a[100001],less,more; while(1) { scanf("%lld",&n); //n==-1 indicates the end of the input or values if(n==-1) break; //Initialize less , more and sum with "0" less=0; more=0; sum=0; for(i=1;i<=n;i++) { scanf("%lld",&a[i]); } for(i=1;i<=n;i++) sum=sum+a[i]; sum=sum/n; //sum here indicates number of candies that should be
//there in each packets from here after for(i=1;i<=n;i++) { //calculating more and less as mentioned in our explanation if(a[i]<sum) less+=(sum-a[i]); else more+=(a[i]-sum); } //Incase less and more are not equal then we can't
// keep equal number of candies in all packets //according to given input otherwise print the output if(less!=more) printf("-1\n"); else printf("%lld\n",more); } return 0; }

 

Happy Coding........
Feel Free to Comment...........

 


No comments:

Post a comment