Saturday, April 27, 2013

Codeforces Round #179 (Div. 2) A Yaroslav and Permutations

//Codeforces Round #179 (Div. 2) A Yaroslav and Permutations


import java.io.*;
import java.io.ObjectInputStream.GetField;
import java.math.*;
import java.text.*;
import java.util.*;

//Codeforces
public class MainCodeforces1 {
    private static MyScanner in;
    private static PrintStream out;

    private static void solve() throws IOException
    {
        int[] cnt = new int[1001];
        for (int i = 0; i < cnt.length; i++) {
            cnt[i] = 0;
        }
        int n = in.nextInt();
        for (int j = 0; j < n; j++) {
            int x = in.nextInt();
            cnt[x] += 1;
        }

        int maxSame = 0;
        for (int i = 0; i < cnt.length; i++) {
            maxSame = Math.max(cnt[i], maxSame);
        }
        if (maxSame <= (n + 1) / 2)
            out.println("YES");
        else
            out.println("NO");
    }

    public static void main(String[] args) throws IOException {
        // helpers for input/output
        boolean LOCAL_TEST = false;// change to false before submitting
        out = System.out;
        if (LOCAL_TEST) {
            in = new MyScanner("E:\\zin.txt");
        }
        else {
            boolean usingFileForIO = false;
            if (usingFileForIO) {
                // using input.txt and output.txt as I/O
                in = new MyScanner("input.txt");
                out = new PrintStream("output.txt");
            }
            else {
                in = new MyScanner();
                out = System.out;
            }
        }

        solve();
    }

    // =====================================
    static class MyScanner {
        Scanner inp = null;

        public MyScanner() throws IOException
        {
            inp = new Scanner(System.in);
        }

        public MyScanner(String inputFile) throws IOException {
            inp = new Scanner(new FileInputStream(inputFile));
        }

        public int nextInt() throws IOException {
            return inp.nextInt();
        }

        public long nextLong() throws IOException {
            return inp.nextLong();
        }

        public double nextDouble() throws IOException {
            return inp.nextDouble();
        }

        public String nextString() throws IOException {
            return inp.next();
        }

    }

}

Friday, April 26, 2013

Google Code Jam Round 1A 2013 A Bullseye

// Google Code Jam Round 1A 2013 A Bullseye

import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;

//Google Code Jam
public class GoogleCode1c {
    private static MyScanner in;
    private static PrintStream out;
    private static PrintStream sysout = System.out;
    static int caseNum;

    private static void solve() throws IOException
    {
        PreCompute();
        int C = in.nextInt();
        for (int i = 0; i < C; i++) {
            caseNum = i + 1;
            out.print("Case #" + caseNum + ": ");
            solveCase();
        }
    }

    private static void PreCompute() {
    }

    private static void solveCase() throws IOException {
        long R = in.nextLong();
        long T = in.nextLong();
        long reqdPaint;
        long nL = 0;
        long nR = 1000000000;
        long nMid = 0;
        long ans = -1;
        while (true) {
            nMid = (nL + nR) / 2;
            reqdPaint = calcPaint(R, nMid, T);
            if (reqdPaint > T)
                nR = nMid - 1;
            else {
                ans = nMid;
                nL = nMid + 1;
            }
            if (nR < nL) {
                break;
            }
        }
        // ans = calcPaint(1, 2000000000L);
        out.println(ans);
    }

    static long calcPaint(long rad, long nring, long T)
    {
        long alpha;
        if (nring % 2 == 0)
            alpha = 2 * (nring - 1) * nring / 2;
        else
            alpha = 2 *
                    (
                    ((nring - 1) * (nring - 1) / 2) + ((nring - 1) / 2)
                    );

        BigInteger bn = new BigInteger(String.valueOf(nring));
        bn = bn.multiply(new BigInteger(String.valueOf(rad)));
        bn = bn.add(new BigInteger(String.valueOf(alpha)));
        bn = bn.multiply(new BigInteger("2"));
        bn = bn.add(new BigInteger(String.valueOf(nring)));
        BigInteger bT = new BigInteger(String.valueOf(T));
        if (bn.compareTo(bT) > 0)
            return T + 1;

        long ret = 2 * (nring * rad + alpha) + nring;
        return ret;
    }

    public static void main(String[] args) throws IOException {
        // helpers for input/output
        boolean usingFileForIO = true;
        if (usingFileForIO) {
            // using input.txt and output.txt as I/O
            in = new MyScanner("E:\\zin.txt");
            out = new PrintStream("E:\\zout.txt");
        }
        else {
            in = new MyScanner();
            out = System.out;
        }

        solve();
    }

    // =====================================
    static class MyScanner {
        Scanner inp = null;

        public MyScanner() throws IOException
        {
            inp = new Scanner(System.in);
        }

        public MyScanner(String inputFile) throws IOException {
            inp = new Scanner(new FileInputStream(inputFile));
        }

        public int nextInt() throws IOException {
            return inp.nextInt();
        }

        public long nextLong() throws IOException {
            return inp.nextLong();
        }

        public double nextDouble() throws IOException {
            return inp.nextDouble();
        }

        public String nextString() throws IOException {
            return inp.next();
        }

        public String nextLine() throws IOException {
            return inp.nextLine();
        }
    }

}

Google Code Jam Round 1A 2013 B Manage your Energy (small-input)

// Google Code Jam Round 1A 2013 B Manage your Energy (small-input)

import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;

//Google Code Jam
public class GoogleCode2 {
    private static MyScanner in;
    private static PrintStream out;
    static int caseNum;

    private static void solve() throws IOException
    {
        int C = in.nextInt();
        in.nextLine();
        for (int i = 0; i < C; i++) {
            caseNum = i + 1;
            out.print("Case #" + caseNum + ": ");
            solveCase();
        }
    }

    static long maxGain;

    private static void solveCase() throws IOException {
        long E = in.nextInt();
        long R = in.nextInt();
        if (R > E)
            R = E;
        int N = in.nextInt();
        long[] v = new long[N];
        for (int i = 0; i < N; i++) {
            v[i] = in.nextLong();
        }
        maxGain = 0;
        calcGain(E, E, R, v, 0, 0);
        out.println(maxGain);
    }

    private static void calcGain(long maxE, long curE, long R, long[] v,
            long lastGain, int idxv)
    {
        if (idxv == v.length - 1) {
            long g = curE * v[v.length - 1];
            long gain = lastGain + g;
            if (gain > maxGain)
                maxGain = gain;
            return;
        }

        for (long spent = 0; spent <= curE; spent++) {
            long g = spent * v[idxv];
            long gain = lastGain + g;
            long newE = curE - spent + R;
            newE = Math.min(newE, maxE);
            calcGain(maxE, newE, R, v, gain, idxv + 1);
        }
        return;
    }

    public static void main(String[] args) throws IOException {
        // helpers for input/output
        boolean usingFileForIO = true;
        if (usingFileForIO) {
            // using input.txt and output.txt as I/O
            in = new MyScanner("E:\\zin.txt");
            out = new PrintStream("E:\\zout.txt");
        }
        else {
            in = new MyScanner();
            out = System.out;
        }

        solve();
    }

    // =====================================
    static class MyScanner {
        Scanner inp = null;

        public MyScanner() throws IOException
        {
            inp = new Scanner(System.in);
        }

        public MyScanner(String inputFile) throws IOException {
            inp = new Scanner(new FileInputStream(inputFile));
        }

        public int nextInt() throws IOException {
            return inp.nextInt();
        }

        public long nextLong() throws IOException {
            return inp.nextLong();
        }

        public double nextDouble() throws IOException {
            return inp.nextDouble();
        }

        public String nextString() throws IOException {
            return inp.next();
        }

        public String nextLine() throws IOException {
            return inp.nextLine();
        }
    }

}

Google Code Jam Round 1A 2009 A Multi-base happiness (small input)

//Google Code Jam Round 1A 2009 A Multi-base happiness (small input)

import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;

//Google Code Jam
public class GoogleCode1 {
    private static MyScanner in;
    private static PrintStream out;

    static HashSet<Integer>[] happynums;
    static HashSet<Integer>[] unhappynums;

    private static void solve() throws IOException
    {
        PreCalculate();

        int C = in.nextInt();
        in.nextLine();
        for (int i = 0; i < C; i++) {
            out.print("Case #" + (i + 1) + ": ");
            solveCase();
        }
    }

    static boolean[][] hhh = new boolean[11][12000000];

    private static void PreCalculate() {
        happynums = new HashSet[11];
        unhappynums = new HashSet[11];
        for (int base = 2; base <= 10; base++) {
            happynums[base] = new HashSet<>();
            unhappynums[base] = new HashSet<>();
        }
        // limit: 11814485
        for (int n = 2; n < 11815000; n++) {
            for (int base = 2; base <= 10; base++) {
                if (n == 11814485)
                    n = n + 0;
                boolean hp = IsHappy(n, base);
                hhh[base][n] = hp;
            }
        }

    }

    private static boolean IsHappy(int n, int base) {
        if (base == 2)
            return true;
        if (happynums[base].contains(n)) {
            return true;
        }
        if (unhappynums[base].contains(n)) {
            return false;
        }
        int x = n;
        int sum = 0;
        HashSet<Integer> nums = new HashSet<>();
        boolean happy = false;
        while (true) {
            sum = 0;
            if (nums.contains(x)) {
                happy = false;
                break;
            }
            if (x < 1000)
                nums.add(x);
            while (x > 0) {
                int r = x % base;
                sum += r * r;
                x = x / base;
            }
            // out.println(sum);
            if (happynums[base].contains(sum)) {
                happy = true;
                break;
            }
            if (unhappynums[base].contains(sum)) {
                happy = false;
                break;
            }
            if (sum == 1) {
                happy = true;
                break;
            }
            x = sum;
        }
        if (happy) {
            happynums[base].addAll(nums);
        }
        else {
            unhappynums[base].addAll(nums);
        }
        return happy;
    }

    private static void solveCase() throws IOException {
        String line = in.nextLine();
        String[] sbases = line.split(" ");
        int len = sbases.length;
        int[] b = new int[len];
        for (int i = 0; i < sbases.length; i++) {
            b[i] = Integer.valueOf(sbases[i]);
        }

        int ans = 0;
        for (int n = 2; n < 11815000; n++) {
            boolean allHappy = true;
            for (int i = 0; i < b.length; i++) {
                int base = b[i];
                if (n == 11814485)
                    n = n + 0;
                // boolean hp = IsHappy(n, base);
                boolean hp = hhh[base][n];
                allHappy = allHappy & hp;
                if (!allHappy) {
                    break;
                }
            }
            if (allHappy) {
                ans = n;
                break;
            }
        }
        out.println(ans);
    }

    public static void main(String[] args) throws IOException {
        // helpers for input/output
        boolean usingFileForIO = true;
        if (usingFileForIO) {
            // using input.txt and output.txt as I/O
            in = new MyScanner("E:\\zin.txt");
            out = new PrintStream("E:\\zout.txt");
        }
        else {
            in = new MyScanner();
            out = System.out;
        }

        solve();
    }

    // =====================================
    static class MyScanner {
        Scanner inp = null;

        public MyScanner() throws IOException
        {
            inp = new Scanner(System.in);
        }

        public MyScanner(String inputFile) throws IOException {
            inp = new Scanner(new FileInputStream(inputFile));
        }

        public int nextInt() throws IOException {
            return inp.nextInt();
        }

        public long nextLong() throws IOException {
            return inp.nextLong();
        }

        public double nextDouble() throws IOException {
            return inp.nextDouble();
        }

        public String nextString() throws IOException {
            return inp.next();
        }

        public String nextLine() throws IOException {
            return inp.nextLine();
        }
    }

}

Monday, April 22, 2013

Google Code Jam Round 1A 2008 B Milkshakes

//Google Code Jam Round 1A 2008 B Milkshakes

import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;

//Google Code Jam
public class GoogleCode1 {
    private static MyScanner in;
    private static PrintStream out;

    private static void solve() throws IOException
    {
        int C = in.nextInt();
        for (int i = 0; i < C; i++) {
            out.print("Case #" + (i + 1) + ": ");
            solveCase();
        }
    }

    static int M;
    static HashMap<Integer, HashSet<Integer>> unmaltedPrefs;
    static int[] maltedPrefs;
    static HashSet<Integer> batchMalted;
    static HashSet<Integer> batchUnmalted;

    private static void solveCase() throws IOException {
        unmaltedPrefs = new HashMap<>();
        batchMalted = new HashSet<>();
        batchUnmalted = new HashSet<>();

        int N = in.nextInt();
        M = in.nextInt();
        maltedPrefs = new int[M];
        for (int i = 0; i < M; i++) {
            maltedPrefs[i] = -1;
        }

        for (int i = 0; i < M; i++) {
            int T = in.nextInt();
            HashSet<Integer> pref = new HashSet<>();
            for (int j = 0; j < T; j++) {
                int flav = in.nextInt();
                int malted = in.nextInt();
                if (malted == 1)
                    maltedPrefs[i] = flav;
                else
                    pref.add(flav);
            }
            unmaltedPrefs.put(i, pref);
        }

        batchMalted = new HashSet<>();
        batchUnmalted = new HashSet<>();
        for (int i = 1; i <= N; i++) {
            batchUnmalted.add(i);
        }

        boolean recheck = true;

        while (recheck) {
            recheck = false;
            for (int i = 0; i < M; i++) {
                if (checkCustSatisfied(i)) {
                    continue;
                }
                else {
                    int maltedPref = maltedPrefs[i];
                    if (maltedPref > 0) {
                        if (!batchMalted.contains(maltedPref)) {
                            batchMalted.add(maltedPref);
                            batchUnmalted.remove(maltedPref);
                            recheck = true;
                        }
                    }
                }
            }
        }

        boolean allSatisfied;
        allSatisfied = true;
        for (int i = 0; i < M; i++) {
            if (!checkCustSatisfied(i)) {
                allSatisfied = false;
                break;
            }
        }

        if (allSatisfied) {
            String ans = "";
            for (int i = 1; i <= N; i++) {
                if (batchMalted.contains(i))
                    ans += "1 ";
                else
                    ans += "0 ";
            }
            out.println(ans);
        }
        else
            out.println("IMPOSSIBLE");
    }

    public static boolean checkCustSatisfied(int cust)
    {
        HashSet<Integer> pref = unmaltedPrefs.get(cust);
        for (Integer p : pref) {
            if (batchUnmalted.contains(p)) {
                return true;
            }
        }
        int maltedPref = maltedPrefs[cust];
        if (maltedPref > 0 && batchMalted.contains(maltedPref))
            return true;
        return false;
    }

    public static void main(String[] args) throws IOException {
        // helpers for input/output
        boolean usingFileForIO = true;
        if (usingFileForIO) {
            // using input.txt and output.txt as I/O
            in = new MyScanner("E:\\zin.txt");
            out = new PrintStream("E:\\zout.txt");
        }
        else {
            in = new MyScanner();
            out = System.out;
        }

        solve();
    }

    // =====================================
    static class MyScanner {
        Scanner inp = null;

        public MyScanner() throws IOException
        {
            inp = new Scanner(System.in);
        }

        public MyScanner(String inputFile) throws IOException {
            inp = new Scanner(new FileInputStream(inputFile));
        }

        public int nextInt() throws IOException {
            return inp.nextInt();
        }

        public long nextLong() throws IOException {
            return inp.nextLong();
        }

        public double nextDouble() throws IOException {
            return inp.nextDouble();
        }

        public String nextString() throws IOException {
            return inp.next();
        }

        public String nextLine() throws IOException {
            return inp.nextLine();
        }
    }

}

Wednesday, April 17, 2013

Google Code Jam 2009, Qualification Round C Welcome to Code Jam

//Google Code Jam 2009, Qualification Round     C Welcome to Code Jam
import java.awt.Frame;
import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;

//Google Code Jam
public class GoogleCode1 {
    private static MyScanner in;
    private static PrintStream out;

    private static void solve() throws IOException
    {
        int C = in.nextInt();
        in.nextLine();
        for (int i = 0; i < C; i++) {
            out.print("Case #" + (i + 1) + ": ");
            solveCase();
        }
    }

    static String swcj = "welcome to code jam";
    static char[] wcj;

    private static void solveCase() throws IOException {
        wcj = swcj.toCharArray();
        String stext = in.nextLine();
        char[] cstext = stext.toCharArray();
        int wlen = wcj.length;
        int slen = cstext.length;
        int[][] f = new int[wlen][slen];
        for (int c = 0; c < wlen; c++) {
            for (int d = 0; d < slen; d++) {
                int left = 0;
                int above = 0;
                if (c > 0) {
                    left = f[c - 1][d];
                }
                if (d > 0) {
                    above = f[c][d - 1];
                }

                if (wcj[c] == cstext[d]) {
                    if (c > 0)
                        f[c][d] = left + above;
                    else
                        f[c][d] = left + above + 1;
                }
                else {
                    f[c][d] = above;
                }
                f[c][d] = f[c][d] % 10000;
            }
        }

        int cnt = f[wlen - 1][slen - 1];
        String result = String.format("%04d", cnt % 10000);
        out.println(result);
    }

    public static void main(String[] args) throws IOException {        // helpers for input/output
        boolean usingFileForIO = true;
        if (usingFileForIO) {
            // using input.txt and output.txt as I/O
            in = new MyScanner("E:\\zin.txt");
            out = new PrintStream("E:\\zout.txt");
        }
        else {
            in = new MyScanner();
            out = System.out;
        }

        solve();
    }

    // =====================================
    static class MyScanner {
        Scanner inp = null;

        public MyScanner() throws IOException
        {
            inp = new Scanner(System.in);
        }

        public MyScanner(String inputFile) throws IOException {
            inp = new Scanner(new FileInputStream(inputFile));
        }

        public int nextInt() throws IOException {
            return inp.nextInt();
        }

        public long nextLong() throws IOException {
            return inp.nextLong();
        }

        public double nextDouble() throws IOException {
            return inp.nextDouble();
        }

        public String nextString() throws IOException {
            return inp.next();
        }

        public String nextLine() throws IOException {
            return inp.nextLine();
        }
    }

}

Tuesday, April 16, 2013

Google Code Jam 2009, Qualification Round B Watersheds

//Google Code Jam 2009, Qualification Round B Watersheds

import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;

//Google Code Jam
public class GoogleCode1 {
    private static MyScanner in;
    private static PrintStream out;

    private static void solve() throws IOException
    {
        int C = in.nextInt();
        for (int i = 0; i < C; i++) {
            out.print("Case #" + (i + 1) + ":");
            solveCase();
        }
    }

    private static void solveCase() throws IOException {
        int H = in.nextInt();
        int W = in.nextInt();
        int[][] alt = new int[H + 2][W + 2];
        for (int i = 0; i <= H + 1; i++) {
            for (int j = 0; j <= W + 1; j++) {
                if (i == 0 || i == H + 1 || j == 0 || j == W + 1)
                    alt[i][j] = 10001;
                else
                    alt[i][j] = in.nextInt();
            }
        }
        char[][] basin = new char[H + 2][W + 2];
        for (int i = 0; i < H + 2; i++) {
            for (int j = 0; j < W + 2; j++) {
                basin[i][j] = '-';
            }
        }

        int cnt = 0;
        char lastbasin = 'a';
        while (cnt < W * H)
        {
            for (int i = 1; i <= H; i++) {
                for (int j = 1; j <= W; j++) {
                    if (basin[i][j] != '-')
                        continue;
                    int altc = alt[i][j];
                    int minAltN = altc;
                    minAltN = Math.min(minAltN, alt[i - 1][j]);
                    minAltN = Math.min(minAltN, alt[i + 1][j]);
                    minAltN = Math.min(minAltN, alt[i][j - 1]);
                    minAltN = Math.min(minAltN, alt[i][j + 1]);
                    if (altc == minAltN) {
                        basin[i][j] = lastbasin;
                        lastbasin++;
                        cnt++;
                    }
                    else {
                        if (alt[i - 1][j] == minAltN) {
                            basin[i][j] = basin[i - 1][j];
                        } else if (alt[i][j - 1] == minAltN) {
                            basin[i][j] = basin[i][j - 1];
                        } else if (alt[i][j + 1] == minAltN) {
                            basin[i][j] = basin[i][j + 1];
                        } else if (alt[i + 1][j] == minAltN) {
                            basin[i][j] = basin[i + 1][j];
                        }
                        if (basin[i][j] != '-')
                            cnt++;
                    }
                }
            }
        }

        // sort basins
        char[][] sortedbasin = new char[H + 2][W + 2];
        char lastchar = 'a';
        HashMap<Character, Character> map = new HashMap<>();
        for (int i = 1; i <= H; i++) {
            for (int j = 1; j <= W; j++) {
                char b = basin[i][j];
                if (!map.containsKey(b)) {
                    map.put(b, lastchar);
                    lastchar++;
                }
                sortedbasin[i][j] = map.get(b);
            }
        }

        out.println();
        for (int i = 1; i <= H; i++) {
            for (int j = 1; j <= W; j++) {
                out.print(sortedbasin[i][j]);
                out.print(" ");
            }
            out.println();
        }

    }

    public static void main(String[] args) throws IOException {
        // helpers for input/output
        boolean usingFileForIO = true;
        if (usingFileForIO) {
            // using input.txt and output.txt as I/O
            in = new MyScanner("E:\\zin.txt");
            out = new PrintStream("E:\\zout.txt");
        }
        else {
            in = new MyScanner();
            out = System.out;
        }

        solve();
    }

    // =====================================
    static class MyScanner {
        Scanner inp = null;

        public MyScanner() throws IOException
        {
            inp = new Scanner(System.in);
        }

        public MyScanner(String inputFile) throws IOException {
            inp = new Scanner(new FileInputStream(inputFile));
        }

        public int nextInt() throws IOException {
            return inp.nextInt();
        }

        public long nextLong() throws IOException {
            return inp.nextLong();
        }

        public double nextDouble() throws IOException {
            return inp.nextDouble();
        }

        public String nextString() throws IOException {
            return inp.next();
        }

        public String nextLine() throws IOException {
            return inp.nextLine();
        }
    }

}

Sunday, April 14, 2013

Google Code Jam 2009, Qualification Round A Alien Language

//Google Code Jam 2009, Qualification Round A Alien Language

import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;

//Google Code Jam
public class GoogleCode1 {
    private static MyScanner in;
    private static PrintStream out;

    private static void solve() throws IOException
    {
        L = in.nextInt();
        D = in.nextInt();
        int N = in.nextInt();
        words = new char[D][L];
        for (int i = 0; i < D; i++) {
            words[i] = in.nextString().toCharArray();
        }
        int C = N;
        for (int i = 0; i < C; i++) {
            out.print("Case #" + (i + 1) + ": ");
            solveCase();
        }
    }

    static int L;
    static int D;
    static char[][] words;

    private static void solveCase() throws IOException {
        String pat = in.nextString();
        HashSet<Character>[] token = new HashSet[L];
        boolean isgroup = false;
        int idx = 0;
        for (int i = 0; i < pat.length(); i++) {
            char c = pat.charAt(i);
            if (c == '(') {
                isgroup = true;
                token[idx] = new HashSet<Character>();
            }
            else if (c == ')') {
                isgroup = false;
                idx++;
            }
            else {
                if (isgroup) {
                    token[idx].add(c);
                }
                else {
                    token[idx] = new HashSet<Character>();
                    token[idx].add(c);
                    idx++;
                }
            }
        }

        int cnt = 0;
        for (int i = 0; i < D; i++) {
            boolean valid = true;
            for (int j = 0; j < L; j++) {
                if (!token[j].contains(words[i][j])) {
                    valid = false;
                    break;
                }
            }
            if (valid)
                cnt++;
        }

        out.println(cnt);
    }

    public static void main(String[] args) throws IOException {
        // helpers for input/output
        boolean usingFileForIO = true;
        if (usingFileForIO) {
            // using input.txt and output.txt as I/O
            in = new MyScanner("E:\\zin.txt");
            out = new PrintStream("E:\\zout.txt");
        }
        else {
            in = new MyScanner();
            out = System.out;
        }

        solve();
    }

    // =====================================
    static class MyScanner {
        Scanner inp = null;

        public MyScanner() throws IOException
        {
            inp = new Scanner(System.in);
        }

        public MyScanner(String inputFile) throws IOException {
            inp = new Scanner(new FileInputStream(inputFile));
        }

        public int nextInt() throws IOException {
            return inp.nextInt();
        }

        public long nextLong() throws IOException {
            return inp.nextLong();
        }

        public double nextDouble() throws IOException {
            return inp.nextDouble();
        }

        public String nextString() throws IOException {
            return inp.next();
        }

        public String nextLine() throws IOException {
            return inp.nextLine();
        }
    }

}

Friday, April 12, 2013

Google Code Jam Round 1A 2008 A Minimum Scalar Product

// Google Code Jam Round 1A 2008 A Minimum Scalar Product
import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;

//Google Code Jam
public class GoogleCode1 {
    private static MyScanner in;
    private static PrintStream out;

    private static void solve() throws IOException
    {
        int C = in.nextInt();
        in.nextLine();
        for (int i = 0; i < C; i++) {
            out.print("Case #" + (i + 1) + ": ");
            solveCase();
        }
    }

    private static void solveCase() throws IOException {
        int n = in.nextInt();
        long[] x = new long[n];
        long[] y = new long[n];
        for (int i = 0; i < n; i++) {
            x[i] = in.nextLong();
        }
        for (int i = 0; i < n; i++) {
            y[i] = in.nextLong();
        }
        Arrays.sort(x);
        Arrays.sort(y);
        long sum = 0;
        for (int i = 0; i < n; i++) {
            sum += x[i] * y[n - 1 - i];
        }
        out.println(sum);
    }

    public static void main(String[] args) throws IOException {
        // helpers for input/output
        boolean usingFileForIO = true;
        if (usingFileForIO) {
            // using input.txt and output.txt as I/O
            in = new MyScanner("E:\\zin.txt");
            out = new PrintStream("E:\\zout.txt");
        }
        else {
            in = new MyScanner();
            out = System.out;
        }

        solve();
    }

    // =====================================
    static class MyScanner {
        Scanner inp = null;

        public MyScanner() throws IOException
        {
            inp = new Scanner(System.in);
        }

        public MyScanner(String inputFile) throws IOException {
            inp = new Scanner(new FileInputStream(inputFile));
        }

        public int nextInt() throws IOException {
            return inp.nextInt();
        }

        public long nextLong() throws IOException {
            return inp.nextLong();
        }

        public double nextDouble() throws IOException {
            return inp.nextDouble();
        }

        public String nextString() throws IOException {
            return inp.next();
        }

        public String nextLine() throws IOException {
            return inp.nextLine();
        }
    }

}

Tuesday, April 9, 2013

Google Code Jam Qualification Round Africa 2010 C T9 Spelling

// Google Code Jam Qualification Round Africa 2010 C T9 Spelling

import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;

//Google Code Jam
public class GoogleCode1 {
    private static MyScanner in;
    private static PrintStream out;

    static String alpha = " abcdefghijklmnopqrstuvwxyz";
    static String digit = "022233344455566677778889999";
    static String times = "112312312312312312341231234";

    private static void solve() throws IOException
    {

        int C = in.nextInt();
        in.nextLine();
        for (int i = 0; i < C; i++) {
            out.print("Case #" + (i + 1) + ": ");
            solveCase();
        }
    }

    private static void solveCase() throws IOException {
        // TODO Auto-generated method stub
        String s = in.nextLine();
        int idx;
        char prevdig = '*';
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == ' ')
                idx = 0;
            else
                idx = 1 + c - 'a';
            char t = times.charAt(idx);
            int repeat = Integer.valueOf(String.valueOf(t));
            char dig = digit.charAt(idx);
            if (dig == prevdig)
                out.print(' ');
            for (int j = 0; j < repeat; j++) {
                out.print(dig);
            }
            prevdig = dig;
        }
        out.println();
    }

    public static void main(String[] args) throws IOException {
        // helpers for input/output
        boolean usingFileForIO = true;
        if (usingFileForIO) {
            // using input.txt and output.txt as I/O
            in = new MyScanner("E:\\zin.txt");
            out = new PrintStream("E:\\zout.txt");
        }
        else {
            in = new MyScanner();
            out = System.out;
        }

        solve();
    }

    // =====================================
    static class MyScanner {
        Scanner inp = null;

        public MyScanner() throws IOException
        {
            inp = new Scanner(System.in);
        }

        public MyScanner(String inputFile) throws IOException {
            inp = new Scanner(new FileInputStream(inputFile));
        }

        public int nextInt() throws IOException {
            return inp.nextInt();
        }

        public long nextLong() throws IOException {
            return inp.nextLong();
        }

        public double nextDouble() throws IOException {
            return inp.nextDouble();
        }

        public String nextString() throws IOException {
            return inp.next();
        }

        public String nextLine() throws IOException {
            return inp.nextLine();
        }
    }

}

Google Code Jam Qualification Round Africa 2010 B Reverse Words

//Google Code Jam Qualification Round Africa 2010 B Reverse Words

import java.io.*;
import java.io.ObjectInputStream.GetField;
import java.math.*;
import java.text.*;
import java.util.*;

//Google Code Jam
public class GoogleCode1 {
    private static MyScanner in;
    private static PrintStream out;

    private static void solve() throws IOException
    {
        int C = in.nextInt();
        in.nextLine();
        for (int i = 0; i < C; i++) {
            out.print("Case #" + (i + 1) + ": ");
            solveCase();
        }
    }

    private static void solveCase() throws IOException {
        // TODO Auto-generated method stub
        String s = in.nextLine();
        String[] ss = s.split(" ");
        for (int i = ss.length - 1; i > 0; i--) {
            out.print(ss[i] + " ");
        }
        out.println(ss[0]);
    }

    public static void main(String[] args) throws IOException {
        // helpers for input/output
        boolean usingFileForIO = true;
        if (usingFileForIO) {
            // using input.txt and output.txt as I/O
            in = new MyScanner("E:\\zin.txt");
            out = new PrintStream("E:\\zout.txt");
        }
        else {
            in = new MyScanner();
            out = System.out;
        }

        solve();
    }

    // =====================================
    static class MyScanner {
        Scanner inp = null;

        public MyScanner() throws IOException
        {
            inp = new Scanner(System.in);
        }

        public MyScanner(String inputFile) throws IOException {
            inp = new Scanner(new FileInputStream(inputFile));
        }

        public int nextInt() throws IOException {
            return inp.nextInt();
        }

        public long nextLong() throws IOException {
            return inp.nextLong();
        }

        public double nextDouble() throws IOException {
            return inp.nextDouble();
        }

        public String nextString() throws IOException {
            return inp.next();
        }

        public String nextLine() throws IOException {
            return inp.nextLine();
        }
    }

}

Google Code Jam Qualification Round Africa 2010 A Store Credit

//Google Code Jam Qualification Round Africa 2010 A Store Credit

import java.io.*;
import java.io.ObjectInputStream.GetField;
import java.math.*;
import java.text.*;
import java.util.*;

//Google Code Jam
public class GoogleCode1 {
    private static MyScanner in;
    private static PrintStream out;

    private static void solve() throws IOException
    {
        int C = in.nextInt();
        for (int i = 0; i < C; i++) {
            out.print("Case #" + (i + 1) + ": ");
            solveCase();
        }
    }

    private static void solveCase() throws IOException {
        // TODO Auto-generated method stub
        int C = in.nextInt();
        int I = in.nextInt();
        int[] P = new int[I];
        for (int j = 0; j < P.length; j++) {
            P[j] = in.nextInt();
        }
        for (int i = 0; i < P.length; i++) {
            int a = P[i];
            for (int j = i + 1; j < P.length; j++) {
                int b = P[j];
                if (a + b == C) {
                    out.println("" + (i + 1) + " " + (j + 1));
                    return;
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        // helpers for input/output
        boolean usingFileForIO = true;
        if (usingFileForIO) {
            // using input.txt and output.txt as I/O
            in = new MyScanner("E:\\zin.txt");
            out = new PrintStream("E:\\zout.txt");
        }
        else {
            in = new MyScanner();
            out = System.out;
        }

        solve();
    }

    // =====================================
    static class MyScanner {
        Scanner inp = null;

        public MyScanner() throws IOException
        {
            inp = new Scanner(System.in);
        }

        public MyScanner(String inputFile) throws IOException {
            inp = new Scanner(new FileInputStream(inputFile));
        }

        public int nextInt() throws IOException {
            return inp.nextInt();
        }

        public long nextLong() throws IOException {
            return inp.nextLong();
        }

        public double nextDouble() throws IOException {
            return inp.nextDouble();
        }

        public String nextString() throws IOException {
            return inp.next();
        }

    }

}

Monday, April 8, 2013

Codeforces Round #178 (Div. 2) A Shaass and Oskols

//Codeforces Round #178 (Div. 2) A Shaass and Oskols

import java.io.*;
import java.io.ObjectInputStream.GetField;
import java.math.*;
import java.text.*;
import java.util.*;

//Codeforces
public class MainCodeforces1 {
    private static MyScanner in;
    private static PrintStream out;

    private static void solve() throws IOException
    {
        int n = in.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < a.length; i++) {
            a[i] = in.nextInt();
        }
        int m = in.nextInt();
        int[] x = new int[m];
        int[] y = new int[m];
        for (int i = 0; i < y.length; i++) {
            x[i] = in.nextInt();
            y[i] = in.nextInt();
        }
        for (int i = 0; i < m; i++) {
            int px = x[i] - 1;
            int py = y[i] - 1;
            if (px > 0) {
                a[px - 1] += py;
            }
            if (px < n - 1) {
                a[px + 1] += a[px] - (py + 1);
            }
            a[px] = 0;
        }
        for (int i = 0; i < a.length; i++) {
            out.println(a[i]);
        }

    }

    public static void main(String[] args) throws IOException {
        // helpers for input/output
        boolean LOCAL_TEST = false;// change to false before submitting
        out = System.out;
        if (LOCAL_TEST) {
            in = new MyScanner("E:\\zin2.txt");
        }
        else {
            boolean usingFileForIO = false;
            if (usingFileForIO) {
                // using input.txt and output.txt as I/O
                in = new MyScanner("input.txt");
                out = new PrintStream("output.txt");
            }
            else {
                in = new MyScanner();
                out = System.out;
            }
        }

        solve();
    }

    // =====================================
    static class MyScanner {
        Scanner inp = null;

        public MyScanner() throws IOException
        {
            inp = new Scanner(System.in);
        }

        public MyScanner(String inputFile) throws IOException {
            inp = new Scanner(new FileInputStream(inputFile));
        }

        public int nextInt() throws IOException {
            return inp.nextInt();
        }

        public long nextLong() throws IOException {
            return inp.nextLong();
        }

        public double nextDouble() throws IOException {
            return inp.nextDouble();
        }

        public String nextString() throws IOException {
            return inp.next();
        }

    }

}

Sunday, April 7, 2013

Topcoder SRM 575 DIV 2 L2 TheNumberGameDivTwo

//Topcoder SRM 575 DIV 2 L2 TheNumberGameDivTwo

import java.util.*;
import java.math.*;

//rename the class name before submit
public class TheNumberGameDivTwo {
    public static void main(String[] args) {
        TheNumberGameDivTwo obj = new TheNumberGameDivTwo();
        System.out.println(
                obj.find(
                        128
                        ));
    }

    public String find(int n) {
        boolean[] prm = GetPrimeTable(1000);
        String[] winner = new String[1001];
        winner[1] = "Brus";
        for (int i = 2; i <= 1000; i++) {
            if (prm[i])
                winner[i] = "Brus";
            else {
                List<Integer> divs = GetDivisors(i);
                String cwin = "Brus";
                for (Integer div : divs) {
                    int rem = i - div;
                    if (winner[rem] == "Brus") {
                        cwin = "John";
                        break;
                    }
                }
                winner[i] = cwin;
            }
        }
        return winner[n];
    }

    private List<Integer> GetDivisors(int n) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                int j = n / i;
                list.add(i);
                if (j != i)
                    list.add(j);
            }
        }
        return list;
    }

    public static boolean[] GetPrimeTable(int maxNum) {
        boolean[] isPrime = new boolean[maxNum + 1];
        for (int i = 0; i < isPrime.length; i++) {
            isPrime[i] = true;
        }
        isPrime[0] = isPrime[1] = false;
        int sqrtMaxNum = (int) Math.sqrt(maxNum) + 1;
        for (int i = 2; i <= sqrtMaxNum; i++) {
            if (!isPrime[i])
                continue;
            int k = i * i;
            while (k <= maxNum) {
                isPrime[k] = false;
                k += i;
            }
        }
        return isPrime;
    }

}

Topcoder SRM 575 DIV 2 L1 TheSwapsDivTwo

//Topcoder SRM 575 DIV 2 L1 TheSwapsDivTwo

import java.util.*;
import java.math.*;

//rename the class name before submit
public class TheSwapsDivTwo {
    public static void main(String[] args) {
        TheSwapsDivTwo obj = new TheSwapsDivTwo();
        System.out.println(
                obj.find(
                        new int[] { 4, 7, 4 }
                        ));
    }

    public int find(int[] sequence) {
        HashSet<String> set = new HashSet<String>();
        for (int i = 0; i < sequence.length; i++) {
            for (int j = i + 1; j < sequence.length; j++) {
                int temp = sequence[i];
                sequence[i] = sequence[j];
                sequence[j] = temp;
                StringBuilder sb = new StringBuilder();
                for (int k = 0; k < sequence.length; k++) {
                    sb.append("-" + String.valueOf(sequence[k]));
                }
                if (!set.contains(sb)) {
                    set.add(sb.toString());
                }
                temp = sequence[i];
                sequence[i] = sequence[j];
                sequence[j] = temp;
            }
        }
        return set.size();
    }
}