miércoles, 1 de junio de 2011

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

  

https://www.spoj.pl/problems/CANDY/



public class Candy 
{
   public static void main( String args[] ) throws Exception
   {
      int[] paquetes = new int[ 10000 ];
      int suma, promedio, cantMovidas, car;
  
      int cantPaquetes = sig();
  
      while( cantPaquetes != - 1 )
      {
         suma = 0;
   
         // Leemos el valor de cada paquete y lo sumamos al total de paquetes
         for( int i = 0; i < cantPaquetes; i ++ )
         {   
            paquetes[ i  ] = sig();
            suma += paquetes[ i ];
         }
   
         // Verificamos si es posible dividir los paquetes en cantidades iguales
         if( suma % cantPaquetes == 0 )
         {
            promedio = suma / cantPaquetes;
            cantMovidas = 0;
    
            // Calculamos la cantidad de movimientos necesarios para lograr
            // repartir los paquetes en cantidades iguales
            for( int i = 0; i < cantPaquetes; i ++ )
            {
               if( paquetes[ i ] > promedio )
                  cantMovidas += ( paquetes[ i ] - promedio ); 
            }
         }
         else
            cantMovidas = -1;
   
         System.out.println( cantMovidas );
   
         // Caso especial de lectura, por el signo menos.
         // Leemos la cantidad de paquetes del siguiente caso.
         car = System.in.read();
   
         if( car == '-' )
            break;
         else
         {
            cantPaquetes = car - 48;
            car = System.in.read();
    
            while( car != 10 )
            {
               cantPaquetes = 10 * cantPaquetes + ( car - 48 );
               car = System.in.read();
            }
         }
      }
   }
 
   public static int sig() throws Exception
   {
      int val = 0;
      int car = System.in.read();
  
      while( car != 10 )
      {
         val = 10 * val + ( car - 48 );
         car = System.in.read();
      }
  
      return val;
   }
}


No hay comentarios:

Publicar un comentario