ants.java

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
 
/**
 *
 * @author cteam040
 */
import java.util.*;
import java.io.*;
 
public class ants 
{
	public static void main(String[] s) throws Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		String ln;
		while((ln=br.readLine())!=null)
		{
			st = new StringTokenizer(ln);
                        boolean maxright=false,maxleft = true;
 
			List<Integer> pp = new ArrayList<Integer>(2);
			final int len = Integer.parseInt(st.nextToken());
			int mrav = Integer.parseInt(st.nextToken());
                        List<Ant> ants = new ArrayList<Ant>(mrav);
			int maxdist = -1;
			for(int i=0;i<mrav;i++)
			{
				st = new StringTokenizer(br.readLine());
                                int apos = Integer.parseInt(st.nextToken());
                                int dist = -1;
                                boolean left = false;
                                if("R".equals(st.nextToken()))
                                {
                                    dist = len-apos;
                                    left = false;
                                    ants.add(new Ant(apos,false,dist));
                                }
                                else
                                {
                                    dist = apos;
                                    left = true;
                                    ants.add(new Ant(apos,true,dist));
                                }
                                if(dist>maxdist)
                                {
                                    pp.clear();
                                    maxleft = false;
                                    maxright = false;
                                    maxdist = dist;
                                }
                                if(dist==maxdist)
                                {
                                    if(left) maxleft = true;
                                    else maxright = true;
                                    pp.add(apos);
                                }
			}
                        Collections.sort(ants, new Comparator<Ant>(){
 
                                public int compare(Ant arg0, Ant arg1) {
                                    return arg0.apos-arg1.apos;
                                }
                            });
 
                        boolean ordered = true;
                        do
                        {
                            ordered = true;
                            for(int i=1;i<mrav;i++)
                            {
                                if(!ants.get(i-1).goesleft && ants.get(i).goesleft)
                                {
                                    ordered = false;
                                    ants.get(i-1).goesleft = true;
                                    ants.get(i).goesleft = false;
                                }
                            }
                        }while(!ordered);
                        int boundary = 0;
                        for(int i=0;i<mrav;i++)
                        {
                            if(!ants.get(i).goesleft)
                            {
                                boundary = i;
                                break;
                            }
                            boundary++;
                        }
                        System.out.print("The last ant will fall down in "+maxdist+" seconds - started at ");
                        if(pp.size()==1)
                            System.out.print(ants.get(maxright?boundary:(boundary-1)).apos);
                        else
                            System.out.print(ants.get(boundary-1).apos+" and "+ants.get(boundary).apos);
                        System.out.println(".");
		}
	}
 
                public static class Ant
                {
                    int apos;
                    boolean goesleft;
                    int fallsin=-1;
 
        public Ant(int apos, boolean goesleft,int fallsin) {
            this.apos = apos;
            this.goesleft = goesleft;
            this.fallsin = fallsin;
        }
        public String toString()
        {
            return apos+"-"+goesleft;
        }
 
                }
}