SRM 529

Div2 - 250 PairingPawns

public class PairingPawns {
    public int savedPawnCount(int[] start) {
        int n = start.length;
        for (int i = n - 1; i > 0; --i) {
            start[i - 1] += start[i] / 2;
        }
        return start[0];
     }
}

Div2 - 500, Div1 - 250 KingSort

import java.util.*;

public class KingSort implements Comparator<String> {
    Map<String, Integer> map = new HashMap<String, Integer>();

    public String[] getSortedList(String[] kings) {
        String s1[] = ",I,II,III,IV,V,VI,VII,VIII,IX,X".split(",");
        String s2[] = ",X,XX,XXX,XL,L".split(",");
        for (int i = 1; i <= 50; ++i) {
            map.put(s2[i / 10] + s1[i % 10], i);
        }
        Arrays.sort(kings, this);
        return kings;
    }
    public int compare(String s1, String s2) {
        String t1[] = s1.split(" ");
        String t2[] = s2.split(" ");
        if (!t1[0].equals(t2[0])) return t1[0].compareTo(t2[0]);
        return map.get(t1[1]).compareTo(map.get(t2[1]));
    }
}

Div2 - 1000 MinskyMysteryDiv2

public class MinskyMysteryDiv2 {
    long get(long N) {
        if (N < 2) return -1;
        long i = 2;
        while (i * i <= N && N % i != 0) ++i;
        if (i * i > N) i = N;
        return N / i + i;
    }
    public long computeAnswer(long N) {
        return get(N);
        
     }
}

Div1 - 600 MinskyMystery

import java.util.*;

public class MinskyMystery {

    final int MOD = 1000 * 1000 * 1000 + 9;

    long add(long r, long x) {
        x %= MOD;
        if (x < 0) x += MOD;
        return (r + x) % MOD;
    }

    // get sum N/i (i == 1..N)
    long clever(long N) {
        long res = 0;
        long t = (long)Math.sqrt(1.0 * N);
        long i;
        for (i = 1; i * i < N; ++i) {
            res += N / i;
            if (N / i > t) res += (N / i - N / (i + 1)) * i;
        }
        if (i * i == N) res += i;
        return res;
    }

    public int computeAnswer(long N) {
        if (N < 2) return -1;
        long r = 1;
        long j = 2;
        while (j * j <= N && N % j != 0) ++j;
        if (j * j > N) j = N;

        r = add(r, 2 * j - 3);
        r = add(r, (j - 1) % MOD * (N % MOD) % MOD * 3); 
        r = add(r, (j - 2) % MOD * (N % MOD) % MOD); 

        if (j == N) {
            r = add(r, clever(N) - N);
        } else {
            for (long i = 2; true; ++i) {
                r = add(r, N / i);
                if (N % i == 0) break; 
            }
        }
        return (int)r;
    }
}

Div1 - 900 BigAndSmallAirports