- Prepare
- Algorithms
- Graph Theory
- Drive
- Discussions
Drive
Drive
+ 0 comments import java.io.; import java.util.; import java.text.; import java.math.; import java.util.regex.*;
public class Solution {
public static void main(String[] args) { Scanner scan = new Scanner(System.in); //try{scan = new Scanner(new File("input00.txt"));}catch(Exception e){} step[] steps = new step[scan.nextInt()]; passenger[] passengers = new passenger[scan.nextInt()]; int nitro = scan.nextInt(); loadStuff(scan,steps,passengers); addPassengers(steps,passengers); calcDepartures(steps); //printStations(steps); //System.out.println(passengerTime(steps,passengers)); Queue<run> runs = new PriorityQueue(); findruns(runs,steps); //printruns(runs); //System.out.println(totalDistance(steps)); saveNitro(steps,runs,nitro); calcDepartures(steps); System.out.println(passengerTime(steps,passengers)); } static void saveNitro(step[] steps,Queue<run> runs,int nitroLimit){ long targetSaving = totalDistance(steps) - nitroLimit; run r; int s; int x; while(0<targetSaving){ r = runs.poll(); s = r.station; x = steps[s].distance - steps[s].travelTime; if(x>r.deadline){x=r.deadline;} if(x>targetSaving){x=(int)targetSaving;} //System.out.println("Station "+String.valueOf(s)+", saved "+String.valueOf(x)); steps[s].travelTime += x; r.deadline -= x; targetSaving -= x; if ((0<s) && (0 < r.deadline)){ r.carrying += steps[s].dropped; r.station--; runs.add(r); } } } static long totalDistance(step[] steps){ long distance=0; for(step s : steps){ distance += s.distance; } return distance; } static void printruns(Queue<run> runs){ for(run r : runs){ System.out.println("~~~~~~~~"); System.out.println("station : "+String.valueOf(r.station)); System.out.println("deadline : "+String.valueOf(r.deadline)); System.out.println("tocarry : "+String.valueOf(r.carrying)); } } static void findruns(Queue<run> runs,step[] steps){ // timeTaken should be 0 for all stations steps[steps.length-1].departure = 2000000000; for(int i=0;i<steps.length-1;i++){ if(steps[i].departure < steps[i+1].departure){ run r = new run(); r.station = i; r.deadline = steps[i+1].departure - steps[i].departure; r.carrying = steps[i+1].dropped; runs.add(r); } } } static long passengerTime(step[] steps,passenger[] passengers){ long total = 0; for(passenger p : passengers){ total += steps[p.dest-1].departure + steps[p.dest-1].travelTime - p.arrival; } return total; } static void calcDepartures(step[] steps){ int t = 0; for (step s : steps){ if(s.departure < t){ s.departure = t; }else{ t = s.departure; } t+=s.travelTime; } } static void addPassengers(step[] steps, passenger[] passengers){ for (passenger p : passengers) { if(steps[p.start].departure < p.arrival){ steps[p.start].departure = p.arrival; } steps[p.start].pickedUp++; steps[p.dest].dropped++; } int load=0; for (step s : steps){ load += s.pickedUp - s.dropped; s.carried = load; } } static void loadStuff(Scanner scan,step[] steps, passenger[] passengers){ for(int i=0;i<steps.length-1;i++){ steps[i] = new step(); steps[i].distance = scan.nextInt(); steps[i].departure = 0; steps[i].travelTime = 0; steps[i].carried = 0; steps[i].pickedUp = 0; steps[i].dropped = 0; } steps[steps.length-1] = new step(); for(int i=0;i<passengers.length;i++){ passengers[i] = new passenger(); passengers[i].arrival = scan.nextInt(); passengers[i].start = scan.nextInt()-1; passengers[i].dest = scan.nextInt()-1; } } static void printStations(step[] steps){ for(step s : steps){ //System.out.println(" : "+String.valueOf(s)); System.out.println("-------"); System.out.println("departure : "+String.valueOf(s.departure)); System.out.println("distance : "+String.valueOf(s.distance)); System.out.println("travel time : "+String.valueOf(s.travelTime)); System.out.println("picked up : "+String.valueOf(s.pickedUp)); System.out.println("dropped : "+String.valueOf(s.dropped)); System.out.println("carried : "+String.valueOf(s.carried)); } }
}
class passenger{ public int arrival; int start; int dest; }
class step{ public int departure; int distance; int carried; int pickedUp; int dropped; int travelTime; }
class run implements Comparable{ public int station; int deadline; int carrying;
@Override public int compareTo(run r2){ return (this.carrying - r2.carrying); }
}
+ 0 comments any help to fix this?
import java.io.; import java.util.;
public class Solution {
public static void main(String[] args) { /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */ Scanner in = new Scanner(System.in); int st = in.nextInt(); int pass = in.nextInt(); int nitro = in.nextInt(); int [] timeSt =new int [st -1]; for (int i =0; i< st-1; i++){ timeSt[i]= in.nextInt(); //System.out.print(" " + timeSt[i]); } //System.out.print(st +" "+ pass +" "+ nitro + " " + in.nextInt()); // estacion , max tiempo de espera int auxT = 0; int auxE = 0; int trash = 0; Map <Integer,Integer> trav = new HashMap<>(); for (int i = 0; i < pass; i ++){ auxT = in.nextInt(); auxE = (in.nextInt()) - 1; trash = (in.nextInt()); //System.out.println("T: "+ auxT+" ST: "+auxE); if (!(trav.containsKey(auxE))){ trav.put(auxE, auxT); }else{ if(trav.get(auxE)< auxT ){ trav.put(auxE, auxT); // System.out.println("metemos ->T: "+ auxT+" ST: "+auxE); } } } // nitro int aux = 0; for (int i = timeSt.length -1; i>=0; i--){ if (2*nitro <= timeSt[i]){ timeSt[i] -= nitro; nitro = 0; break; }else { if (timeSt[i] % 2 == 1){ aux = (timeSt[i]-1 / 2); timeSt[i] = (timeSt[i]+1) /2; nitro -= nitro; } } } // se presupone que empezamos enn t=0 long timeTot = 0; for (int i = 0; i<st-1; i++){ //System.out.println("parada" + i+ "time " + timeTot); if (i >= 0){ // ojo las estaciones empiezan en st[0], // cogemos pasajeros if(trav.containsKey(i)){ if (timeTot < trav.get(i)){// tiempo de espera //System.out.println(timeTot); timeTot = trav.get(i); // esperamos a cargar pasajeros // System.out.println("Esperamos a la carga hasta "+ timeTot+ "en st " + i); } // nos desplazamos // System.out.println(i +"-> " + timeSt[i]); } // System.out.println("ST " + i + " Time " + timeTot+ " ST+1 " + timeSt[i]); timeTot += timeSt[i]; } } //System.out.println(); //vuelta al head for (int i = 0; i<st-1; i++){ timeTot += timeSt[i]; } System.out.println(timeTot); }
}
+ 0 comments I think the test cases may be flawed - I think the test cases assume that time is decreased for all customers on the bus when nitro is used.
However, what should be the case is that the customer's travel time is reduced by using nitro if they get off at the following stop. If a customer has to hang around at the stop waiting for customers to get onto the bus at their normal time (ignorant of the use of nitro), then the benefits of using nitro are lost.
+ 2 comments The bus is equipped with K units of Nitro (N2O). If going from station i to station j takes x seconds, then using t units of nitro can decrease the time taken to max(x-t, 0) seconds where max(a,b) denotes the greater of the two values between a & b
Can someone please explain this to me? It's pretty confusing with the example given. Please make it clear.
+ 1 comment can a commuter arrive at a station before the train
Sort 6 Discussions, By:
Please Login in order to post a comment