USACO 2014 December Gold

Problem 3: CowJog

Cow Jog

Farmer John’s N cows (1 <= N <= 100,000) are out exercising their hooves again, jogging along an infinite track. Each cow starts at a distinct position on the track, and some cows run at different speeds.

The track is divided into lanes so that cows may move past each other. No two cows in the same lane may ever occupy the same position. Farmer John doesn’t want any cow to have to change lanes or adjust speed, and he wonders how many lanes he will need to accomplish this if the cows are going to run for T minutes (1 <= T <= 1,000,000,000).

INPUT: (file cowjog.in)

The first line of input contains N and T.

The following N lines each contain the initial position and speed of a single cow. Position is a nonnegative integer and speed is a positive integer; both numbers are at most 1 billion. All cows start at distinct positions, and these will be given in increasing order in the input.

SAMPLE INPUT:

5 3
0 1
1 2
2 3
3 2
6 1

OUTPUT: (file cowjog.out)

A single integer indicating the minimum number of lanes necessary so that no two cows in the same lane ever occupy the same location (including at time T).

SAMPLE OUTPUT:

3

import javax.xml.soap.Node;
import java.io.*;
import java.util.*;

class Beef implements Comparable<Beef> {
    long position;
    long speed;
    int id;
    Beef(int p, int s, int i) {
        position = p;
        speed = s;
        id = i;
    }
    @Override
    public int compareTo(Beef o) {
        return (this.position < o.position ? -1 :
                (this.position == o.position ? 0 : 1));
    }
}

public class CowJog2 {

    List<Beef> m_cows;

    CowJog2() {
        m_cows = new ArrayList<Beef>();
    }

    void sortCow() {
        Collections.sort(m_cows);
    }

    void printCows() {
        for (int i = 0; i < m_cows.size(); i++) {
            System.out.printf("(%d, %d), ",(int) m_cows.get(i).position, (int) m_cows.get(i).speed);
        }
        System.out.println();
    }


    Integer cowJ(int T) {
        for (int i = 0; i < m_cows.size(); i++) {
            m_cows.get(i).position = m_cows.get(i).position + (m_cows.get(i).speed * T);
        }
        // use dp for finding collisions
        int currentGroups = m_cows.size();
        for (int i = m_cows.size() - 2; i >= 0; i--) {
            if (m_cows.get(i).position >= m_cows.get(i + 1).position) {
                // collision
                currentGroups--;
                m_cows.get(i).position = m_cows.get(i + 1).position;
            }
        }
        return currentGroups;
    }

    Integer cowJog() {
        int currentGroups = m_cows.size();
        int worldTime = 0;
        for (int i = m_cows.size() - 1; i > 0; i--) {
            if (m_cows.get(i).speed < m_cows.get(i - 1).speed) {
                    //m_cows.get(i - 1).speed = m_cows.get(i).speed;
                    System.out.println(m_cows.get(i - 1).id);
                    currentGroups--;
                }
            }

        return currentGroups;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new FileReader("cowjog.in"));
        PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("cowjog.out")));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int T = Integer.parseInt(st.nextToken());

        CowJog2 cowJog2 = new CowJog2();

        for(int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            Beef currentCow = new Beef(x, y, i);

            cowJog2.m_cows.add(currentCow);
        }

        cowJog2.sortCow();

        int ans = cowJog2.cowJ(T);

        pw.println(ans);
        pw.close();
    }
}