Guest User

CH11 GasStations

a guest
Jun 20th, 2011
948
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.util.LinkedList;
  5. import java.util.List;
  6.  
  7. /*
  8.  * Tuenti Contest
  9.  * Challenge 11 - Gas Stations
  10.  * Author: Pedro Antonio Pardal Jimena
  11.  * Email: pardal@alu.uma.es
  12.  */
  13.  
  14. public class GasStations
  15. {
  16.     private static String formateaLista( List<Integer> gasolineras )
  17.     {
  18.         if ( gasolineras.isEmpty() )
  19.         {
  20.             return "No stops";
  21.         }
  22.         else
  23.         {
  24.             StringBuffer sb = new StringBuffer();
  25.            
  26.             for ( int gasolinera : gasolineras )
  27.             {
  28.                 sb.append( gasolinera + " " );
  29.             }
  30.            
  31.             return sb.toString().trim();
  32.         }
  33.     }
  34.    
  35.     private static String calcularParadas( int maxkm, int disttotal, List<Integer> gasolineras )
  36.     {
  37.         List<Integer> visitadas = new LinkedList<Integer>();
  38.        
  39.         int autonomia = maxkm;
  40.        
  41.         for ( int i = 0; i < (gasolineras.size() - 1); i++ )
  42.         {
  43.             int actual = gasolineras.get( i );
  44.             int siguiente = gasolineras.get( i + 1 );
  45.            
  46.             int distancia = siguiente - actual;
  47.  
  48.             if ( distancia > autonomia )
  49.             {
  50.                 visitadas.add( actual );
  51.                 autonomia = maxkm - distancia;
  52.             }
  53.             else
  54.             {
  55.                 autonomia -= distancia;
  56.             }          
  57.         }
  58.        
  59.         return formateaLista( visitadas );
  60.     }
  61.    
  62.     public static void main( String[] args )
  63.     {
  64.         BufferedReader reader = new BufferedReader( new InputStreamReader( System.in ) );
  65.        
  66.         try
  67.         {
  68.             int ncasos = Integer.parseInt( reader.readLine().trim() );
  69.            
  70.             for ( int i = 0; i < ncasos; i++ )
  71.             {
  72.                 int maxkm = Integer.parseInt( reader.readLine().trim() );
  73.                 int disttotal = Integer.parseInt( reader.readLine().trim() );
  74.                
  75.                 reader.readLine(); // número de gasolineras
  76.                
  77.                 List<Integer> gasolineras = new LinkedList<Integer>();
  78.                
  79.                 gasolineras.add( 0 );
  80.                 for ( String s : reader.readLine().split( " " ) )
  81.                 {
  82.                     gasolineras.add( Integer.parseInt( s ) );
  83.                 }
  84.                 gasolineras.add( disttotal );
  85.                
  86.                 String resultado = calcularParadas( maxkm, disttotal, gasolineras );
  87.                
  88.                 System.out.println( resultado );
  89.             }
  90.         }
  91.         catch ( IOException e )
  92.         {
  93.             System.err.println( "Formato de la entrada incorrecto" );
  94.         }
  95.     }
  96. }
RAW Paste Data