Competitions » Main CodeFu Competitons » CodeFu 2010 » Results
CodeFu 2010 Results

Final Round Results

igorkulev's solution for 300: NumberSequence, written in Java, submitted on 09.05.2010 12:11:26

public class NumberSequence {

	
	public static void main(String[] args) {
		int answer = new NumberSequence().findDigit(55);
		System.out.println(answer);
	}
	
	long calculate(long mom) {
		//System.out.println("T: "+mom);
		long i,j,k;
		long base = 1;
		String num = Long.toString(mom);
		long len = num.length();
		long res = 0;
		long pom = 0;
		
		// for every length smaller than this
		for (i = 1;i<len;i++) {
			// we work with this base
			pom = base*9;
			
			//System.out.println(pom+" "+base+" "+i);
			
			res += pom*i;
			
			
			base *= 10;
		}
		
		base = 1;
		for (i=1;i<len;i++) {
			base *= 10;
		}
		base--;
		
		//System.out.println("FIN: "+base+" "+(mom-base)+" "+len);
		
		res += (mom-base)*len;
		
		return res;
	}
	
	public int findDigitPrev(int N) {
	    long i,j,k;
	    long low, mid, high;
		long LN = N;
	    long score;
		
	    if (N < 10) {
	    	return N;
	    }
	    
		//System.out.println(calculate(1000000100));
		
		
		long slow = 1;
		long shigh = 8888889899L;
		
		low = 1;
		high = 1000000100;
		
		while (high - low > 1) {
			
			mid = (low+high)/2;
			score = calculate(mid);
			// there are score digits ending with the number mid
			
			// this means this number can be included
			if (score >= N) {
				high = mid;
				shigh = score;
			} else {
				// sigurno ovoj broj ne e resenieto
				low = mid;
				slow = score;
			}
			
			
		}
		
		score = calculate(high);
		// mapping score => high(last digit)
		String p = Long.toString(high);
		long len = p.length();
		long dif = score-N;
		
		//System.out.println(p+" "+len+" "+dif);
		
		char res = (char)((int)(p.charAt((int)(len-1-dif)))-(int)'0');
		
		return res;
	}
	
	public int findDigit(int N) {
	   long i,j,k;
	   
	   // da gi zapisam za malite brojki rezultatite kako gotovi
	   
	   int totalsofar = 0;
	   int counter = 1;
	   int prev = 0;
	   int res = 0;
	   
	   while (true) {
		   if (totalsofar >= N) {
			   // we have found the solution
			   
			   //System.out.println(N+" "+totalsofar+" "+prev);
			   
			   res = findDigitPrev(N-prev);
			   
			   break;
		   }
		   
		   prev = totalsofar;
		   totalsofar += calculate(counter);
		   //System.out.println(counter);
		   
		   counter++;
		   
	   }
		
		
		return res;
	}

}