SRM526.5

	Level 1	Level 2	Level 3
Div 1	Level 1	Level 2	Level 3
Div 2	Level 1	Level 2	Level 3

SRM526.5

Tutorials:

---

Division One - Level Three:

Solution

Source Code:

---

Division One - Level Two:

Solution

Source Code:

---

Division One - Level One:

Solution

Source Code:

---

Sivision Two - Level Three:

Solution

Source Code:

---

Division Two - Level Two:

Solution

Source Code:

/**
 * Method 2: using dynamic programming, which will not work if n is large.
 * it will exceed the memory limit.
 */

/**
 * @author antonio081014
 * @since Dec 23, 2011, 6:07:14 PM
 */

public class MagicCandy {

    public int whichOne(int n) {
        int step = 0;
        while (n > 1) {
            step++;
            n -= (int) Math.sqrt(n);
        }
        int e = 1;
        for (int i = 0; i < step; i++)
            e += (int) Math.sqrt(e + Math.sqrt(e));
        return e;
    }

    public int[] map;
    public int[] counts;

    public int whichOne2(int n) {

        map = new int[n + 1];
        counts = new int[n + 1];
        int count = 0;
        for (int i = 1; i <= n; i++) {
            if (isMagic(i)) {
                count++;
                counts[i] = 1;
            }
            map[i] = count;
        }
        int ret = -1;
        int mmax = 0;
        for (int i = 1; i <= n; i++) {
            if (getDepth(i) > mmax) {
                mmax = counts[i];
                ret = i;
            }
        }
        return ret;
    }

    public int getDepth(int n) {
        if (counts[n] != 0)
            return counts[n];
        counts[n] = 1 + getDepth(n - map[n]);
        return counts[n];
    }

    public boolean isMagic(int n) {
        int x = (int) Math.sqrt(n);
        if (n == x * x)
            return true;
        return false;
    }

    // <%:testing-code%>
}
// Powered by [KawigiEdit] 2.0!

---

Division Two - Level One:

Solution

Source Code:

/**
 * There exists another easier method based on the observation.
 * Any none-one number could be represented by the combination of prime numbers.
 *
 */

/**
 * @author antonio081014
 * @since Dec 23, 2011, 6:02:46 PM
 */

public class MagicStonesStore {
    public String ableToDivide(int n) {
        for (int i = 1; i <= n; i++) {
            if (isPrime(i) && isPrime(2 * n - i))
                return "YES";
        }
        return "NO";
    }

    public boolean isPrime(int n) {
        if (n <= 1)
            return false;
        if (n == 2)
            return true;
        if (n % 2 == 0)
            return false;
        for (int i = 3; i * i <= n; i++)
            if (n % i == 0)
                return false;
        return true;
    }

    // <%:testing-code%>
}
// Powered by [KawigiEdit] 2.0!