Ants.java

 
import java.io.BufferedReader;
 
/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.logging.Level;
import java.util.logging.Logger;
 
/**
 *
 * @author cteam021
 */
public class Ants {
 
    private Klada klada;
 
    public static void main(String[] args) {
        try {
            new Ants();
        } catch (Exception e) {
            System.out.println("Exc");
            e.printStackTrace();
        }
    }
 
    public Ants() throws IOException {
 
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String line = reader.readLine();
        String length = line.substring(0, line.indexOf(' '));
        Integer lengthKlada = Integer.parseInt(length);
 
        Integer numAnts = Integer.parseInt(line.substring(line.indexOf(' ') + 1));
 
        klada = new Klada(lengthKlada);
 
 
        for (int i = 0; i < numAnts; i++) {
            line = reader.readLine();
            int pos = Integer.parseInt(line.substring(0, line.indexOf(' ')));
            String or = line.substring(line.indexOf(' ') + 1);
            if (or.equals("R")) {
                klada.addAnt(new Ant(pos, true));
            } else {
                klada.addAnt(new Ant(pos, false));
            }
        }
 
        klada.sort();
        doMe();
 
 
 
    }
 
    public void doMe() {
        String prefix = "The last ant will fall down in ";
        String suffix = " seconds - started at ";
        boolean printed = false;
        while (klada.getLength() > 1) {
            //find first collision
            int minIndex = -1;
            double minDiff = -1;
            for (int i = 0; i < klada.getLength() - 1; i++) {
                Ant a1 = klada.get(i);
                Ant a2 = klada.get(i + 1);
                if (collide(a1, a2)) {
                    double diff = Math.abs(a1.getPosition() - a2.getPosition());
                    if ((minDiff == -1 || diff < minDiff) && diff > 0) {
                        minDiff = diff;
                        minIndex = i;
                    }
                }
            }
            double maxDistanceLeft = -1;
            double maxDistanceRight = -1;
 
            Ant corrAntLeft = null;
            Ant corrAntRight = null;
            if (minDiff == -1) {
 
                for (Ant a : klada.getAnts()) {
 
 
 
                    if (a.isIsRight()) {
                        double maxLocal = (klada.getInitLength() - a.getPosition());
                        if (maxDistanceRight == -1 || maxLocal > maxDistanceRight) {
                            corrAntRight = a;
                            maxDistanceRight = maxLocal;
                        }
 
                    } else {
                        double maxLocal = a.getPosition();
                        if (maxDistanceLeft == -1 || maxLocal > maxDistanceLeft) {
                            corrAntLeft = a;
                            maxDistanceLeft = maxLocal;
                        }
                    }
                }
 
                if (maxDistanceLeft > maxDistanceRight) {
                    System.out.println(prefix + (int) (klada.getSeconds() + maxDistanceLeft) +
                            suffix +
                            corrAntLeft.getStartingPosition() + ".");
                } else if (maxDistanceLeft < maxDistanceRight) {
                    System.out.println(prefix + (int) (klada.getSeconds() + maxDistanceRight) + suffix +
                            corrAntRight.getStartingPosition() + ".");
                } else {
                    System.out.println(prefix + (int) (klada.getSeconds() + maxDistanceRight) +
                            suffix +
                            corrAntLeft.getStartingPosition() + " and " + corrAntRight.getStartingPosition() + ".");
                }
                printed = true;
                break;
            }
 
 
 
            double collideIn = minDiff / 2.0;
            //shift all ants
            klada.shiftAnts(collideIn);
 
            //turn all colliding ants
            klada.turnColliding();
            klada.removeFallen();
 
        }
        Ant a = klada.get(0);
        double maxLocal;
        if (a.isIsRight()) {
            maxLocal = (klada.getInitLength() - a.getPosition());
        } else {
            maxLocal = a.getPosition();
 
 
        }
        if (!printed) {
            System.out.println(prefix + (int) (klada.getSeconds() + maxLocal) +
                    suffix +
                    a.getStartingPosition() + ".");
        }
    }
 
    public boolean collide(Ant a1, Ant a2) {
        if (a1.isIsRight() != a2.isIsRight()) {
            return true;
        }
        return false;
    }
}
 
class Klada {
 
    private double seconds = 0;
    private List<Ant> ants = new ArrayList<Ant>();
    private Integer length;
 
    public Integer getInitLength() {
        return length;
    }
 
    public Klada(Integer length) {
        this.length = length;
    }
 
    public void turnColliding() {
        for (int i = 0; i < ants.size() - 1; i++) {
            Ant a1 = ants.get(i);
            Ant a2 = ants.get(i + 1);
            if (a1.getPosition() == a2.getPosition()) {
                a1.setIsRight(!a1.isIsRight());
                a2.setIsRight(!a2.isIsRight());
            }
        }
    }
 
    public void sort() {
        for (int i = 0; i < ants.size() - 1; i++) {
            for (int j = 0; j < ants.size() - 1 - i; j++) {
                if (ants.get(j).getPosition() > ants.get(j + 1).getPosition()) {
                    Ant a = ants.get(j);
                    ants.set(j, ants.get(j + 1));
                    ants.set(j + 1, a);
                }
            }
        }
 
    }
 
    public void removeFallen() {
        List<Ant> newAnts = new ArrayList<Ant>();
        for (Ant a : ants) {
            if (a.getPosition() >= 0 && a.getPosition() <= length) {
                newAnts.add(a);
            }
        }
        ants = newAnts;
    }
 
    public void shiftAnts(double timeShiftFor) {
        seconds += timeShiftFor;
        for (Ant a : ants) {
            if (a.isIsRight()) {
                //shift right
                a.setPosition(a.getPosition() + timeShiftFor);
            } else {
                a.setPosition(a.getPosition() - timeShiftFor);
            }
        }
    }
 
    public void addAnt(Ant ant) {
        ants.add(ant);
    }
 
    public List<Ant> getAnts() {
        return ants;
    }
 
    public Ant get(int i) {
        return ants.get(i);
    }
 
    public void setAnts(List<Ant> ants) {
        this.ants = ants;
    }
 
    public Integer getLength() {
        return ants.size();
    }
 
    public void setLength(Integer length) {
        this.length = length;
    }
 
    public double getSeconds() {
        return seconds;
    }
 
    public void setSeconds(double seconds) {
        this.seconds = seconds;
    }
}
 
class Ant {
 
    private double position;
    private Integer startingPosition;
    //true= right; left= false
    private boolean isRight;
 
    public Ant(Integer position, boolean isRight) {
        this.position = position;
        this.isRight = isRight;
        this.startingPosition = position;
    }
 
    public Integer getStartingPosition() {
        return startingPosition;
    }
 
    public void setStartingPosition(Integer startingPosition) {
        this.startingPosition = startingPosition;
    }
 
    public boolean isIsRight() {
        return isRight;
    }
 
    public void setIsRight(boolean isRight) {
        this.isRight = isRight;
    }
 
    public double getPosition() {
        return position;
    }
 
    public void setPosition(double position) {
        this.position = position;
    }
}