ants.java

 
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
 
/**
 *
 * @author cteam049
 */
public class ants {
 
    protected Ant[] ants;
    protected int antsCnt;
 
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        ants program = new ants();
        program.run();
    }
 
    protected void run() {
        try {
            for (;;) {
                int l = this.nextInt();
                this.antsCnt = this.nextInt();
                this.ants = new Ant[ this.antsCnt ];
 
                for (int i = 0; i < this.antsCnt; i++) {
                    this.ants[i] = new Ant(this.nextInt(), this.nextToken().charAt(0));
                }
 
                Arrays.sort( this.ants );
 
 
                int maxL = -10;
                int maxR = -10;
                int posL = 0;
                int posR = 0;
 
                for ( int i = this.antsCnt - 1; i >= 0; i-- )
                {
                    if ( this.ants[ i ].direction == 'L' )
                    {
                        maxL = this.ants[ i ].pos;
                        posL = i;
                        break;
                    }
                }
 
                for ( int i = 0; i < this.antsCnt; i++ )
                {
                    if ( this.ants[ i ].direction == 'R' )
                    {
                        maxR = l - this.ants[ i ].pos;
                        posR = i;
                        break;
                    }
                }
 
 
                if ( maxL == -10 )
                {
                    System.out.println( "The last ant will fall down in " + maxR + " seconds - started at " + this.ants[ 0 ].pos + "." );
                    continue;
                }
 
                if ( maxR == -10 )
                {
                    System.out.println( "The last ant will fall down in " + maxL + " seconds - started at " + this.ants[ this.antsCnt - 1 ].pos + "." );
                    continue;
                }
 
 
                if ( maxR == maxL )
                {
                    this.ants[ posL ].last = true;
                    this.ants[ posR ].last = true;
                }
                else if ( maxR < maxL )
                {
                    this.ants[ posL ].last = true;
                }
                else
                {
                    this.ants[ posR ].last = true;
                }
 
 
                boolean swapped;
                boolean tmp;
 
                do
                {
                    swapped = false;
                    for ( int i = 0; i < this.antsCnt - 1; i++ )
                    {
                        if ( this.ants[ i ].direction == 'R' && this.ants[ i + 1 ].direction == 'L' )
                        {
                            this.ants[ i ].direction     = 'L';
                            this.ants[ i + 1 ].direction = 'R';
 
                            tmp = this.ants[ i ].last;
                            this.ants[ i ].last = this.ants[ i + 1 ].last;
                            this.ants[ i + 1 ].last = tmp;
 
                            swapped = true;
                        }
                    }
                } while ( swapped );
 
 
                boolean two = false;
                for ( int i = 0; i < this.antsCnt; i++ )
                {
                    if ( this.ants[ i ].last )
                    {
                        if ( ! two )
                        {
                            two = true;
                            System.out.print( "The last ant will fall down in " + Math.max( maxR, maxL ) + " seconds - started at " + this.ants[ i ].pos );
                        }
                        else
                        {
                            System.out.print( " and " + this.ants[ i ].pos );
                        }
                    }
                }
                System.out.println(".");
 
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
 
 
 
    protected class Ant implements Comparable<Ant> {
 
        public int     pos;
        public char    direction;
        public boolean last;
 
        public Ant(int pos, char direction) {
            this.pos       = pos;
            this.direction = direction;
            this.last      = false;
        }
 
        public int compareTo( Ant ant ) {
            return this.pos - ant.pos;
        }
    }
 
 
 
 
 
 
 
 
    /* INPUT READING */
    StringTokenizer st = new StringTokenizer("");
    BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
 
    public String nextToken() throws Exception {
        while (!st.hasMoreTokens()) {
            st = new StringTokenizer(input.readLine());
        }
        return st.nextToken();
    }
 
    public int nextInt() throws Exception {
        return Integer.parseInt(this.nextToken());
    }
 
    public String nextLine() throws Exception {
        return input.readLine();
    }
}