PetrolPumps

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package petrol_pumps_geeks4geeks;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;

/**
 *
 * @author 141021
 */

/*
 Suppose there is a circle. There are n petrol pumps on that circle. You are given two sets of data.

 1. The amount of petrol that every petrol pump has.
 2. Distance from that petrol pump to the next petrol pump.

 Calculate the first point from where a truck will be able to complete the
 circle (The truck will stop at each petrol pump and it has infinite capacity).
 Expected time complexity is O(n). Assume for 1 litre petrol, the truck can go 1 unit of distance.

 For example, let there be 4 petrol pumps with amount of petrol and distance to
 next petrol pump value pairs as {4, 6}, {6, 5}, {7, 3} and {4, 5}.
 The first point from where truck can make a circular tour is 2nd petrol pump.
 Output should be “start = 1″ (index of 2nd petrol pump).
 */
class Pumpa {

    int litriBenzin;
    int rastojanie;

    public Pumpa(int litriBenzin, int rastojanie) {
        this.litriBenzin = litriBenzin;
        this.rastojanie = rastojanie;
    }
}

public class PetrolPumps {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        ArrayDeque<Pumpa> queue = new ArrayDeque<>();
        int N = Integer.parseInt(br.readLine());

        for (int i = 0; i < N; i++) {
            String[] split = br.readLine().split(" ");
            queue.add(new Pumpa(Integer.parseInt(split[0]), Integer.parseInt(split[1])));
        }

       int brojac = 1;
        int start = 0;
        for (;;) {
            Pumpa p = queue.peek();
            if (p.litriBenzin >= p.rastojanie) {
                ++brojac;

                if (brojac == queue.size()) {
                    break;
                }

                queue.remove(p);
                queue.add(p);
            } else {
                ++brojac;
                ++start;
                queue.remove(p);
                queue.add(p);
            }
        }
        System.out.println("start = " + start);
    }
}
/*
INPUT:
4
4 6
6 5
7 3
4 5

OUTPUT:

start = 1

*/