Ants.java

 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;
 
public class Ants {
 
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static ArrayList<Ant> ants = new ArrayList<Ant>();
 
    static class Ant {
 
        boolean d;
        int p, t = 0, s;
    }
    static Comparator<Ant> antComp = new Comparator<Ant>() {
 
        public int compare(Ant a1, Ant a2) {
            return (a1.s - a2.s);
        }
    };
 
    public static void main(String[] args) throws IOException {
 
        int L, A, s, e, x;
 
        do {
            String line = br.readLine();
            if (line == null) {
                break;
            }
            StringTokenizer st = new StringTokenizer(line);
            L = 2 * Integer.parseInt(st.nextToken());
            A = Integer.parseInt(st.nextToken());
            ants.clear();
            for (int i = 0; i < A; i++) {
                st = new StringTokenizer(br.readLine());
                Ant a = new Ant();
                a.s = a.p = 2 * Integer.parseInt(st.nextToken());
                a.d = st.nextToken().equals("R") ? true : false;
                ants.add(a);
            }
            s = 0;
            e = A - 1;
            Collections.sort(ants, antComp);
            while (s <= e) {
                if (!ants.get(s).d) {
                    ants.get(s).t += ants.get(s).p;
                    ants.get(s).p = 0;
                    s++;
                } else if (ants.get(e).d) {
                    ants.get(e).t += L - ants.get(e).p;
                    ants.get(e).p = L;
                    e--;
                } else {
                    for (int i = s; i < e; i++) {
                        if (ants.get(i).d && !ants.get(i + 1).d) {
                            if (ants.get(i).t > ants.get(i + 1).t) {
                                ants.get(i + 1).p -= ants.get(i).t - ants.get(i + 1).t;
                                ants.get(i + 1).t = ants.get(i).t;
                            } else if (ants.get(i).t < ants.get(i + 1).t) {
                                ants.get(i).p += ants.get(i + 1).t - ants.get(i).t;
                                ants.get(i).t = ants.get(i + 1).t;
                            }
                            x = (ants.get(i + 1).p - ants.get(i).p) / 2;
                            ants.get(i).t += x;
                            ants.get(i + 1).t += x;
                            ants.get(i).p += x;
                            ants.get(i + 1).p -= x;
                            ants.get(i).d = false;
                            ants.get(i + 1).d = true;
                        }
                    }
                }
            }
            System.out.print("The last ant will fall down in ");
            if (s < A && e >= 0) {
                if (ants.get(s).t == ants.get(e).t) {
                    System.out.print(ants.get(s).t / 2 + " seconds - started at " + ants.get(e).s / 2 + " and " + ants.get(s).s / 2 + ".");
                } else {
                    if (ants.get(s).t > ants.get(e).t) {
                        System.out.print(ants.get(s).t / 2 + " seconds - started at " + ants.get(s).s / 2 + ".");
                    } else {
                        System.out.print(ants.get(e).t / 2 + " seconds - started at " + ants.get(e).s / 2 + ".");
                    }
                }
            } else if (s < A) {
                System.out.print(ants.get(s).t / 2 + " seconds - started at " + ants.get(s).s / 2 + ".");
            } else {
                System.out.print(ants.get(e).t / 2 + " seconds - started at " + ants.get(e).s / 2 + ".");
            }
 
        } while (true);
 
    }
}