Source code for submission s1112

Ants.java

  1. import java.util.*;
  2. import java.io.*;
  3.  
  4. class Ants {
  5.  
  6. //private static final boolean DEBUG = true;
  7. static int a1pos, a2pos;
  8. static double time, actTime;
  9.  
  10. public static void main( String[] args ) throws Exception {
  11. String line = br.readLine();
  12. String[] p;
  13. while ( line != null ) {
  14. p = line.split( " " );
  15. int l = Integer.parseInt( p[0] );
  16. int a = Integer.parseInt( p[1] );
  17. ArrayList<Ant> ants = new ArrayList<Ant>();
  18. for ( int i = 0; i < a; ++i ) {
  19. p = br.readLine().split( " " );
  20. ants.add( new Ant( Integer.parseInt(p[0]), p[1].charAt(0) ) );
  21. }
  22. //if (DEBUG) System.out.println( "solving" );
  23. solve( l, ants );
  24. if ( a2pos != -1 ) System.out.println( String.format("The last ant will fail down in %.0f seconds - started at %d and %d.", time, a1pos, a2pos ));
  25. else System.out.println( String.format( "The last ant will fail down in %.0f seconds - started at %d.", time, a1pos ) );
  26. line = br.readLine();
  27. }
  28. }
  29.  
  30. // simulation
  31. private static void solve( int l, ArrayList<Ant> ants) {
  32. actTime = 0;
  33. Collections.sort( ants );
  34. //if (DEBUG) System.out.println( "DEBUG: ants - " + ants );
  35. a1pos = -1;
  36. a2pos = -1;
  37. time = -1;
  38. int n = ants.size();
  39. while ( n > 0 ) {
  40. ArrayList<Ant> nants = new ArrayList<Ant>();
  41. //if (DEBUG) System.out.println( "DEBUG: left" );
  42. // remove those walking left
  43. for ( int i = 0; i < n; ++i ) {
  44. Ant ant = ants.get(i);
  45. if ( ant.dir == 'L' ) {
  46. double tmp = ant.pos;
  47. if ( tmp + actTime == time ) {
  48. a2pos = ant.start;
  49. }
  50. if ( tmp + actTime > time ) {
  51. time = tmp + actTime;
  52. a1pos = ant.start;
  53. }
  54. } else {
  55. nants.add( ant ); // copy to new list
  56. for ( int j = i+1; j < n; ++j ) { nants.add( ants.get(j)); }
  57. break;
  58. }
  59. }
  60. ants = nants;
  61. n = ants.size();
  62. nants = new ArrayList<Ant>();
  63. //if (DEBUG) System.out.println( "DEBUG: ants - " + ants );
  64.  
  65. //if (DEBUG) System.out.println( "DEBUG: right" );
  66. // remove those walking right
  67. for ( int i = n-1; i >= 0; --i ) {
  68. Ant ant = ants.get(i);
  69. if ( ant.dir == 'R' ) {
  70. double tmp = l - ant.pos;
  71. if ( tmp + actTime == time ) {
  72. a2pos = ant.start;
  73. }
  74. if ( tmp + actTime> time ) {
  75. time = tmp + actTime;
  76. a1pos = ant.start;
  77. }
  78. } else {
  79. nants.add( ant ); // copy to new list
  80. for ( int j = i-1; j >= 0; --j ) { nants.add( ants.get(j)); }
  81. break;
  82. }
  83. }
  84. ants = nants;
  85. Collections.sort( ants );
  86. n = ants.size();
  87. nants = new ArrayList<Ant>();
  88. //if (DEBUG) System.out.println( "DEBUG: ants - " + ants );
  89.  
  90. // find smallest space
  91. //if (DEBUG) System.out.println( "DEBUG: move" );
  92. HashSet<Integer> si = new HashSet<Integer>(); // smallest firts ant index
  93. double ss = -1D; // smallest space
  94. for ( int i = 0; i < n - 1; ++i ) {
  95. Ant f = ants.get( i );
  96. Ant s = ants.get( i+1 );
  97. if ( f.dir == 'R' && f.dir != s.dir ) {
  98. double tmp = s.pos - f.pos;
  99. if ( ss == -1 || ss > tmp ) {
  100. si.clear();
  101. si.add( i );
  102. ss = tmp;
  103. }
  104. if ( ss == tmp ) {
  105. si.add( i );
  106. }
  107. }
  108. }
  109. move( ants, ss / 2, si );
  110. //if (DEBUG) System.out.println( "DEBUG: ants - " + ants );
  111. }
  112. }
  113.  
  114. private static void move( ArrayList<Ant> ants, double d, HashSet<Integer> set ) {
  115. //if (DEBUG) System.out.println( "DEBUG: d=" + d + ", set=" + set.toString() );
  116. actTime += d;
  117. int n = ants.size();
  118. for ( int i = 0; i < n; ++i ) {
  119. Ant act = ants.get(i);
  120. if ( act.dir == 'L' ) {
  121. act.pos -= d;
  122. if (set.contains(i) || set.contains(i-1) ) {
  123. act.dir = 'R';
  124. }
  125. } else {
  126. act.pos += d;
  127. if (set.contains(i) || set.contains(i-1) ) {
  128. act.dir = 'L';
  129. }
  130. }
  131. }
  132. Collections.sort( ants );
  133. }
  134.  
  135. private static class Ant implements Comparable<Ant> {
  136. double pos; // position
  137. char dir; // direction
  138. int start;
  139.  
  140. Ant( int p, char d ) { start = p; pos = p; dir = d; }
  141.  
  142. public int compareTo( Ant a ) {
  143. if ( a.pos == this.pos ) {
  144. if ( this.dir == 'L' ) return -1;
  145. else return 1;
  146. }
  147. return this.pos < a.pos ? -1 : 1;
  148. }
  149.  
  150. /*public String toString() {
  151. boolean d = DEBUG;
  152. return String.format( "[pos=%f, dir=%c, start=%d]", pos, dir, start );
  153. }*/
  154.  
  155. }
  156.  
  157.  
  158. }
  159.