decimal/decimal_vanb_slow.java

  1 
  2 import java.io.*;
  3 import java.util.*;
  4 import java.awt.geom.*;
  5 
  6 /**
  7  * Solution to Decimals
  8  * 
  9  * @author vanb
 10  */
 11 public class decimal_vanb_slow
 12 {
 13     public Scanner sc;
 14     public PrintStream ps;
 15     
 16     public static final int MAX = 500;
 17     
 18     public boolean seen[] = new boolean[MAX*10+1];
 19     
 20     public int declen( int num, int den )
 21     {        
 22         // Count the number of digits before the '.'
 23         int i = num/den;
 24         int result = 1;
 25         if( i>9 ) ++result;
 26         if( i>99 ) ++result;
 27         
 28         // If the number has decimal places
 29         if( num%den > 0 )
 30         {
 31             //Count the '.'
 32             ++result;
 33     
 34             Arrays.fill( seen, false );
 35             
 36             int count = 0;
 37             int remainder = 0;
 38             num = (num%den)*10;
 39             for(;;)
 40             {
 41                 remainder = num % den;
 42                 if( remainder==0 || seen[num] ) break;
 43                 seen[num] = true;
 44                 ++count;
 45                 num = remainder*10;
 46             }
 47             
 48             result += count;
 49             if( remainder!=0 ) result += 2; else ++result;
 50         }
 51         return result;
 52     }
 53      
 54     /**
 55      * Driver.
 56      * @throws Exception
 57      */
 58     public void doit() throws Exception
 59     {
 60         sc = new Scanner( new File( "decimal.judge" ) );
 61         ps = new PrintStream( new FileOutputStream( "decimal.solution" ) );
 62 
 63         long start = System.currentTimeMillis();
 64         int best[] = new int[MAX+1];
 65         best[1] = 1;
 66         for( int i=2; i<=MAX; i++ )
 67         {
 68             best[i] = best[i-1];
 69             for( int j=1; j<=i; j++ )
 70             {
 71                 int len = declen( i, j );
 72                 if( len>best[i] ) best[i] = len;
 73                 len = declen( j, i );
 74                 if( len>best[i] ) best[i] = len;
 75             }
 76         }
 77         
 78         for(;;)
 79         {
 80             int n = sc.nextInt();
 81             if( n==0 ) break;
 82             
 83             ps.println( best[n] );
 84         }
 85         System.out.println( System.currentTimeMillis() - start );
 86     }
 87     
 88     /**
 89      * @param args
 90      */
 91     public static void main( String[] args ) throws Exception
 92     {
 93         new decimal_vanb_slow().doit();
 94         
 95 //        int inputs[] = new int[MAX];
 96 //        
 97 //        for( int i=0; i<MAX; i++ )
 98 //        {
 99 //            inputs[i] = i+1;
100 //        }
101 //        
102 //        Random r = new Random();
103 //        for( int i=0; i<MAX; i++ )
104 //        {
105 //            int j = r.nextInt(MAX);
106 //            int t = inputs[i];
107 //            inputs[i] = inputs[j];
108 //            inputs[j] = t;
109 //        }
110 //        
111 //        for( int input : inputs )
112 //        {
113 //            System.out.println( input );
114 //        }
115 //        System.out.println( 0 );
116     }   
117 }