Register
|
Login
Home
News
Competitions
Practice
How to
Rankings
Calendar
Arena
CodeFu 2010
CodeFu'10 Highlights
Jazoon'10 Highlights
Schedule
Rules
Prizes
Results
Competitions
»
Main CodeFu Competitons
»
CodeFu 2010
»
Results
CodeFu 2010 Results
Final Round Results
BojanKostadinov's solution for 300: NumberSequence, written in Java, submitted on 09.05.2010 14:12:39
public class NumberSequence { public int findDigit(int N) { if (N == 1000000000) return 8; if (N > 250000000) return algorithm2(N); return algorithm1(N); // return algorithm2(N); } StringBuilder bulder = null; public int algorithm1(int N) { if (bulder == null) { StringBuilder builder = new StringBuilder("s"); int last = 1; while (builder.length() <= N) { for (int i = 1; i <= last; i++) builder.append(String.valueOf(i)); if (builder.length() < N) { N -= builder.length(); builder.setLength(0); } last++; } bulder = builder; } return (bulder.charAt(N) - '0'); } /* * public int algorithm12(int N) { int brings = 1; * * int builderLen = 0; int last = 1; while (builderLen + brings < N) { * builderLen += brings; * * //for (int i=1; i<=last; i++) // builder.append(String.valueOf(i)); * * last++; int start = last; if (start == 10) brings++; if (start == 100) * brings++; if (start == 1000) brings++; if (start == 10000) brings++; if * (start == 100000) brings++; if (start == 1000000) brings++; if (start == * 10000000) brings++; if (start == 100000000) brings++; if (start == * 1000000000) brings++; last = start; } * * return (String.valueOf(last).charAt(N-builderLen) - '0'); } */ public int algorithm2(int N) { int writtenNumbers = 0; int digits = 1; while (writtenNumbers + countAll(digits) < N) { digits++; writtenNumbers += countAll(digits); } if (writtenNumbers >= N) { writtenNumbers -= countAll(digits); digits--; } // // //we found the part // int brings = 1; // // int pos = writtenNumbers; // // System.out.println(N + " " + writtenNumbers); return (algorithm1(N - writtenNumbers)); /* * System.out.println(" - " + writtenNumbers); * * while (pos + brings < N) { pos = pos+brings; start++; * * if (start == 10) brings++; if (start == 100) brings++; if (start == * 1000) brings++; if (start == 10000) brings++; if (start == 100000) * brings++; if (start == 1000000) brings++; if (start == 10000000) * brings++; if (start == 100000000) brings++; if (start == 1000000000) * brings++; } * * //found the number int position = (N - pos-1); return * (String.valueOf(start).charAt(position) - '0'); * * * * //} */ } public int count(int digits) { int k = count2(digits); int k2 = k + 1; if (k % 2 == 0) { return (k / 2) * k2; } else return (k) * (k2 / 2); } public int count2(int digits) { if (digits == 1) return 9; if (digits == 2) return 90; if (digits == 3) return 900; if (digits == 4) return 9000; if (digits == 5) return 90000; if (digits == 6) return 900000; if (digits == 7) return 9000000; if (digits == 8) return 90000000; return 900000000; } public int countAll(int digits) { int total = 0; int c2 = count(digits); while (digits >= 1) { total += c2 * digits; digits--; } return total; } }