ping/ping_vanb.java

  1 
  2 import java.io.*;
  3 import java.util.*;
  4 import java.awt.geom.*;
  5 
  6 /**
  7  * Solution to Ping!
  8  * 
  9  * @author vanb
 10  */
 11 public class ping_vanb
 12 {
 13     public Scanner sc;
 14     public PrintStream ps;
 15     
 16     /**
 17      * Driver.
 18      * @throws Exception
 19      */
 20     public void doit() throws Exception
 21     {
 22         sc = new Scanner( new File( "ping.judge" ) );
 23         ps = new PrintStream( new FileOutputStream( "ping.solution" ) );
 24         
 25         for(;;)
 26         {
 27             char pings[] = sc.next().toCharArray();
 28             if( pings.length==1 ) break;
 29             
 30             // All of the satellites have unique ping times, and they all start at 0.
 31             // So, skipping time 0, if the earliest ping you see is at time k,
 32             // then there has to be a satellite pinging at k. Furthermore, that has
 33             // to be the fastest pinging satellite. 
 34             String results = "";
 35             for( int i=1; i<pings.length; i++ ) if( pings[i]=='1' )
 36             {
 37                 // Report this satellite
 38                 results += " " + i;
 39                 
 40                 // Remove all of its pings from the future
 41                 for( int j=i; j<pings.length; j+=i )
 42                 {
 43                     pings[j] = (pings[j]=='0') ? '1' : '0';
 44                 }
 45             }
 46             
 47             ps.println( results.trim() );
 48         }
 49     }
 50     
 51     /**
 52      * @param args
 53      */
 54     public static void main( String[] args ) throws Exception
 55     {
 56         new ping_vanb().doit();
 57         
 58         char pings[] = new char[1000];
 59         Random r = new Random();
 60         
 61 //        for( int i=1; i<1000; i++ )
 62 //        {
 63 //            Arrays.fill( pings, '0' );
 64 //            pings[i] = '1';
 65 //            System.out.println( new String( pings ) );
 66 //        }
 67 //        
 68 //        Arrays.fill( pings, '1' );
 69 //        System.out.println( new String( pings ) );
 70 //        
 71 //        Arrays.fill( pings, '0' );
 72 //        for( int i=1; i<1000; i++ )
 73 //        {
 74 //            for( int j=i; j<1000; j+=i)
 75 //            {
 76 //                pings[j] = (pings[j]=='1'?'0':'1');
 77 //            }
 78 //        }
 79 //        
 80 //        System.out.println( new String( pings ) );
 81         
 82 //        for( int i=0; i<100; i++ )
 83 //        {
 84 //            int length = r.nextInt(998)+2;
 85 //            pings = new char[length];
 86 //            Arrays.fill( pings, '0' );
 87 //            boolean gotaone = false;
 88 //            for( int j=0; j<length; j++ )
 89 //            {
 90 //                pings[j] = (r.nextInt( 10 )<5 ? '0' : '1' );
 91 //                if( j>0 && pings[j]=='1' ) gotaone = true;
 92 //            }
 93 //            if( gotaone ) System.out.println( new String( pings ) );
 94 //        }
 95     }   
 96 }