Advertisement
Guest User

Untitled

a guest
Nov 2nd, 2014
218
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. import java.util.Arrays;
  3. import java.util.Scanner;
  4.  
  5. public class Solution {
  6.     static int gasStations;
  7.     static Long maxFuel;
  8.     static Long startingFuel;
  9.     static Long length;
  10.  
  11.     private static class Station implements Comparable<Station> {
  12.         long  price;
  13.         long  pos;
  14.  
  15.         private Station(long  price, long pos) {
  16.             this.price = price;
  17.             this.pos = pos;
  18.         }
  19.  
  20.         @Override
  21.         public int compareTo(Station o) {
  22.             return Long.valueOf(price).compareTo(o.price);
  23.         }
  24.  
  25.         @Override
  26.         public String toString() {
  27.             return "{" + price + "$, " + pos + "}";
  28.         }
  29.     }
  30.  
  31.     public static void main(String[] args) {
  32.         Scanner scanner = new Scanner(System.in);
  33.         int M = Integer.parseInt(scanner.nextLine());
  34.         for (int i = 0; i < M; i++) {
  35.             String[] line = scanner.nextLine().split("\\s+");
  36.             gasStations = Integer.parseInt(line[0]);
  37.             maxFuel = Long.parseLong(line[1]);
  38.             startingFuel = Long.parseLong(line[2]);
  39.             length = Long.parseLong(line[3]);
  40.             Station[] stations = new Station[gasStations];
  41.             for (int s = 0; s < gasStations; s++) {
  42.                 line = scanner.nextLine().split("\\s+");
  43.                 stations[s] = new Station(Long.parseLong(line[1]), Long.parseLong(line[0]));
  44.             }
  45.             //SORTING STATIONS, CHEAPEST FIRST
  46.             Arrays.sort(stations);
  47.             checkSolution(stations);
  48.         }
  49.  
  50.     }
  51.  
  52.     private static void checkSolution(Station[] stations) {
  53.         long[] reserveFuel = {0};
  54.         System.out.println(recursiveCall(0, length, startingFuel, stations, reserveFuel));
  55.     }
  56.  
  57.         // RETURNS THE $$ SPENT IN FUEL
  58.     // PARAMS:
  59.     //  START: the start point of this part of the trip
  60.     //  END: the goal of this part of the trip
  61.         //  FUEL: the amount of fuel I have for this section
  62.     //  STATIONS: all the stations, nulled out the ones I have been to
  63.     //  RESERVE FUEL: pointer used to return the amount of gas that was left after the trip. /*I'm not proud of this*/
  64.     private static long recursiveCall(long start, long end, long fuel, Station[] stations, long [] reserveFuel) {
  65. //      System.out.println("RECURSIVING -- start:" + start + " end:" + end + " fuel:" + fuel);
  66.             // IF I HAVE ENOUGH FUEL TO GET TO THE END
  67.         if (end - start <= fuel) {
  68.             reserveFuel[0] = fuel - (end - start);
  69.             return 0; //SPENT NO CASH, I COULD GET THERE WITH THE CURRENT TANK
  70.         }
  71.  
  72.         Station station = null;
  73.         for (int s = 0; s < gasStations && station == null; s++) {
  74.                 // GET THE FIRST (AND CHEAPEST) STATION BETWEEN MY CURRENT START AND END POSITIONS
  75.             if (stations[s] != null && stations[s].pos >= start && stations[s].pos < end) {
  76.                 station = stations[s];
  77.                 stations[s] = null; //NULLING OUT USED STATIONS
  78.             }
  79.         }
  80.             // THERE ARE NO STATIONS BETWEEN START AND END
  81.         if (station == null) {
  82.             return -1; // CAN'T GET THERE
  83.         }
  84.         long ans = 0; // TOTAL $ SPENT
  85.  
  86.             long var = recursiveCall(start, station.pos, fuel, stations, reserveFuel);
  87.             // IF I COULDN'T MAKE IT
  88.         if(var == -1)
  89.             return var;
  90.  
  91.             ans += var; // ADDING THE $$ NEEDED TO GET HERE
  92.  
  93.             long neededFuel = Math.min(maxFuel- reserveFuel[0], end - station.pos - reserveFuel[0]);
  94.  
  95.             long chargedFuel = reserveFuel[0] + neededFuel;
  96.         ans += (neededFuel * station.price); // ADDING WHAT I SPENT HERE
  97.        
  98. //      System.out.println("CHARGING FUEL -- $" + (neededFuel * station.price) + " in:" + station.pos);
  99.         reserveFuel[0] = 0;
  100.         var = recursiveCall(station.pos, end, chargedFuel, stations, reserveFuel);
  101.             // IF I COULDN'T MAKE IT
  102.         if(var == -1)
  103.             return var;
  104.  
  105.             ans += var; // ADDING WHAT I WILL SPEND IN THE REST OF THE TRIP TO MY GOAL        
  106.         return ans;
  107.     }
  108. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement