We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Graph Theory
  4. Drive
  5. Discussions

Drive

Problem
Submissions
Leaderboard
Discussions

Sort 6 Discussions, By:

votes

Please Login in order to post a comment

  • dimova
    12 months ago+ 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|
    Permalink
  • juanjoomad
    4 years ago+ 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|
    Permalink
  • collinslyle
    4 years ago+ 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.

    0|
    Permalink
  • tapan09
    6 years ago+ 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.

    0|
    Permalink
  • shubhm96
    6 years ago+ 1 comment

    can a commuter arrive at a station before the train

    0|
    Permalink
Load more conversations

Need Help?


View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature