Competitions » Main CodeFu Competitons » CodeFu 2007 » Results

CodeFu 2007 Results

CodeFu Final Round Results

toroman's solution for 400: Square Count, written in Java

public class SquareCount {
	int[] kvadrat = new int[20000];
	int kcount = 0;
	boolean generated = false;
	void generate() {
		generated = true;
		final int GRANICA = 31622;
		boolean[] slozen = new boolean[GRANICA+1];
		slozen[2] = false;
		
		for (int i=2; i<= GRANICA; i++) {
			if (!slozen[i]) {
				kvadrat[kcount++] = i*i;
				for (int j=i+i; j<=GRANICA; j+=i)
					slozen[j] = true;
			}
		}
	}
	
	public int pos(int N) {
		if (!generated)
			generate();
		
		int l=1;
		int r=1644934081;
		int m;
		while(true) {
			
			m = (l + r)/2;
			//System.out.printf("L=%d R=%d M=%d\n", l, r, m);
			int dbr = dobroj(m);
			
			if (m - dbr > N) {
				r = m;
				continue;
			} else if (m - dbr < N) {
				l = m;
				continue;
			} else {
				//for (int i=0;)
				return m;
			}
			
		}
	}
	
	public int dobroj(int N) {
		int num = 0;
		for (int k=0; k<kcount; k++) {
			num += N/kvadrat[k];
		}
		return num;
	}
	
	public static void main(String[] args) {
		SquareCount sc = new SquareCount();
		
		System.out.println(sc.pos(9));
		//System.out.println(sc.dobroj(4));
		//for (int i=1; i<20; i++)
		//	System.out.print(", " + sc.pos(i));
		
	}
	//1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19
	//1, 2, 4, 5, 6, 7, 10, 11, 13, 14, 16, 17, 19, 21, 22, 25, 28, 29, 
	
}