Tuesday, December 18, 2012

Codeforces Round #150 (Div. 2) : C - The Brand New Function

// Codeforces Round #150 (Div. 2) : C - The Brand New Function

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

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

    public static void main(String[] args) throws IOException {
        // helpers for input/output
        boolean LOCAL_TEST = false;
        // LOCAL_TEST = true;// comment it 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();
    }

    private static void solve() throws IOException
    {
        int N = in.nextInt();
        int[] nums = new int[N];
        for (int i = 0; i < N; i++) {
            nums[i] = in.nextInt();
        }
        Set<Integer> set = new HashSet<Integer>();
        Set<Integer> tmp = new HashSet<Integer>();
        Set<Integer> tmpset;
        int k = nums[0];
        set.add(k);
        tmp.add(k);
        for (int i = 1; i < N; i++) {
            k = nums[i];
            tmpset = new HashSet<Integer>();
            tmpset.add(k);
            for (Integer x : tmp) {
                tmpset.add(x | k);
            }
            tmp = tmpset;
            for (Integer xx : tmpset) {
                set.add(xx);
            }
        }
        int cnt = set.size();
        out.print(cnt);
    }

    static class MyScanner {
        StreamTokenizer in;

        public MyScanner() throws IOException
        {
            Reader r = new BufferedReader(new InputStreamReader(System.in));
            in = new StreamTokenizer(r);
        }

        public MyScanner(String inputFile) throws IOException {
            Reader r;
            r = new BufferedReader(new FileReader(inputFile));
            in = new StreamTokenizer(r);
        }

        public int nextInt() throws IOException {
            in.nextToken();
            return (int) in.nval;
        }

        public long nextLong() throws IOException {
            in.nextToken();
            return (long) in.nval;
        }

        public double nextDouble() throws IOException {
            in.nextToken();
            return in.nval;
        }

        public String nextString() throws IOException {
            in.nextToken();
            return in.sval;
        }
    }

}

Sunday, December 16, 2012

Codeforces Round #150 (Div. 2): B. Undoubtedly Lucky Numbers

// Codeforces Round #150 (Div. 2):    B. Undoubtedly Lucky Numbers

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

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

    public static void main(String[] args) throws IOException {
        // helpers for input/output
        boolean LOCAL_TEST = false;
        // LOCAL_TEST = true;// comment it 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();
    }

    private static void solve() throws IOException
    {
        int N = in.nextInt();
        cnt = 0;
        dfs(0, N);
        out.print(cnt);
    }

    static int cnt;
    static Set<Integer> set = new HashSet<Integer>();

    private static void dfs(int x, int N) {
        if (x > N)
            return;
        for (int i = 0; i <= 9; i++) {
            int xx = x * 10 + i;
            if (xx > 0 && xx <= N) {
                int test = xx;
                set.clear();
                while (test > 0) {
                    set.add(test % 10);
                    test = test / 10;
                    if (set.size() > 2)
                        break;
                }
                if (set.size() <= 2) {
                    cnt++;
                    dfs(xx, N);
                }
            }
        }
    }

    static class MyScanner {
        StreamTokenizer in;

        public MyScanner() throws IOException
        {
            Reader r = new BufferedReader(new InputStreamReader(System.in));
            in = new StreamTokenizer(r);
        }

        public MyScanner(String inputFile) throws IOException {
            Reader r;
            r = new BufferedReader(new FileReader(inputFile));
            in = new StreamTokenizer(r);
        }

        public int nextInt() throws IOException {
            in.nextToken();
            return (int) in.nval;
        }

        public long nextLong() throws IOException {
            in.nextToken();
            return (long) in.nval;
        }

        public double nextDouble() throws IOException {
            in.nextToken();
            return in.nval;
        }

        public String nextString() throws IOException {
            in.nextToken();
            return in.sval;
        }
    }

}

Saturday, December 15, 2012

Codeforces Round #150 (Div. 2): A - Dividing Orange

// Codeforces Round #150 (Div. 2): A - Dividing Orange

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

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

    public static void main(String[] args) throws IOException {
        // helpers for input/output
        boolean LOCAL_TEST = false;
        // LOCAL_TEST = true;// comment it 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();
    }

    private static void solve() throws IOException
    {
        int N = in.nextInt();
        int K = in.nextInt();
        // int[] nums = new int[K];
        boolean[] used = new boolean[N * K + 1];
        for (int i = 1; i <= N * K; i++) {
            used[i] = false;
        }
        Map<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
        for (int i = 1; i <= K; i++) {
            int x = in.nextInt();
            List<Integer> l = new ArrayList<Integer>();
            l.add(x);
            used[x] = true;
            map.put(i, l);
        }
        int iused = 1;
        for (int i = 1; i <= K; i++) {
            List<Integer> ls = map.get(i);
            while (ls.size() < N) {
                while (used[iused]) {
                    iused++;
                }
                used[iused] = true;
                ls.add(iused);
            }
            map.put(i, ls);
        }
        for (int i = 1; i <= K; i++) {
            List<Integer> ls = map.get(i);
            for (int j = 0; j < ls.size(); j++) {
                if (j > 0)
                    out.print(" ");
                out.print(ls.get(j));
            }
            out.println();
        }
    }

    static class MyScanner {
        StreamTokenizer in;

        public MyScanner() throws IOException
        {
            Reader r = new BufferedReader(new InputStreamReader(System.in));
            in = new StreamTokenizer(r);
        }

        public MyScanner(String inputFile) throws IOException {
            Reader r;
            r = new BufferedReader(new FileReader(inputFile));
            in = new StreamTokenizer(r);
        }

        public int nextInt() throws IOException {
            in.nextToken();
            return (int) in.nval;
        }

        public long nextLong() throws IOException {
            in.nextToken();
            return (long) in.nval;
        }

        public double nextDouble() throws IOException {
            in.nextToken();
            return in.nval;
        }

        public String nextString() throws IOException {
            in.nextToken();
            return in.sval;
        }
    }

}

Friday, December 14, 2012

Codeforces Round #154 (Div. 2): A. Cards with Numbers

// Codeforces Round #154 (Div. 2): A. Cards with Numbers

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

//codeforces
public class Main2 {
    private static MyScanner in;
    private static PrintStream out = System.out;

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

    private static void solve() throws IOException
    {
        int N = in.nextInt();
        List<Integer>[] mm = new ArrayList[5001];
        for (int i = 0; i <= 5000; i++) {
            mm[i] = new ArrayList<Integer>();
        }
        for (int i = 0; i < 2 * N; i++) {
            int k = in.nextInt();
            mm[k].add(i + 1);
        }

        boolean flag = false;
        for (List<Integer> list : mm) {
            if (list.size() % 2 == 1) {
                flag = true;
                break;
            }
        }

        if (flag) {
            out.println(-1);
        }
        else {
            StringBuilder sb = new StringBuilder("");
            for (List<Integer> list : mm) {
                for (int j = 0; j < list.size(); j += 2) {
                    sb.append(list.get(j));
                    sb.append(" ");
                    sb.append(list.get(j + 1));
                    sb.append("\n");
                }
            }
            out.println(sb);
        }
    }
}

class MyScanner {
    StreamTokenizer in;

    public MyScanner() throws IOException
    {
        this("input.txt");
    }

    public MyScanner(String inputFile) throws IOException {
        Reader r;
        r = new BufferedReader(new FileReader(inputFile));
        in = new StreamTokenizer(r);
    }

    public MyScanner(boolean usingStdin)
    {
        if (usingStdin)
        {
            Reader r;
            r = new BufferedReader(new InputStreamReader(System.in));
            in = new StreamTokenizer(r);
        }
    }

    public int nextInt() throws IOException {
        in.nextToken();
        return (int) in.nval;
    }

    public long nextLong() throws IOException {
        in.nextToken();
        return (long) in.nval;
    }

    public double nextDouble() throws IOException {
        in.nextToken();
        return in.nval;
    }

    public String nextString() throws IOException {
        in.nextToken();
        return in.sval;
    }
}

Thursday, December 13, 2012

Topcoder SRM 564 DIV 2, L1: FauxPalindromes

// Topcoder SRM 564 DIV 2, L1: FauxPalindromes

import java.util.*;

class TopcoderSolution {
    public static void main(String[] args) {
        FauxPalindromes obj = new FauxPalindromes();
        System.out.println(
                // obj.numPairs(numbers)
                );
    }
}

// change to public before submit
public class FauxPalindromes {
    public String classifyIt(String word) {
        String rev = (new StringBuffer(word)).reverse().toString();
        if (word.equals(rev))
            return "PALINDROME";
        String word2 = word.substring(0, 1);
        for (int i = 1; i < word.length(); i++) {
            if (word.charAt(i) == word.charAt(i - 1))
                continue;
            else
                word2 = word2 + String.valueOf(word.charAt(i));
        }
        if (word2.equals((new StringBuffer(word2)).reverse().toString()))
            return "FAUX";

        return "NOT EVEN FAUX";
    }

}

Tuesday, December 11, 2012

Codeforces Round #154 (Div. 2): B - Physics Practical

// Codeforces Round #154 (Div. 2): B - Physics Practical 

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

//codeforces
public class Main2 {
    private static Scanner in;
    private static PrintStream out = System.out;

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

    private static void solve()
    {
        int N = in.nextInt();
        int[] c = new int[N];
        for (int i = 0; i < N; i++) {
            c[i] = in.nextInt();
        }
        Arrays.sort(c);
        Map<Integer, Integer> cntGreaterThanX = new HashMap<Integer, Integer>();
        Map<Integer, Integer> cntLessThanX = new HashMap<Integer, Integer>();

        int lastnum = c[0];
        cntLessThanX.put(c[0], 0);
        for (int i = 1; i < N; i++) {
            if (c[i] != lastnum) {
                cntLessThanX.put(c[i], i);
                cntGreaterThanX.put(c[i - 1], N - i);
                lastnum = c[i];
            }
        }
        cntGreaterThanX.put(c[N - 1], 0);

        int minRemove = Integer.MAX_VALUE;
        for (int istart = 0; istart < N; istart++) {
            if (istart > 0 && c[istart] == c[istart - 1])
                continue;
            int remove = cntLessThanX.get(c[istart]);
            // binary search
            int L = istart;
            int R = N - 1;
            int iend = (L + R + 1) / 2;
            while (L < R) {
                iend = (L + R + 1) / 2;
                if (c[iend] == 2 * c[istart]) {
                    break;
                }
                if (c[iend] < 2 * c[istart]) {
                    L = iend + 1;
                }
                else {
                    R = iend - 1;
                }
            }
            while (c[iend] < 2 * c[istart] && iend < N - 1) {
                iend++;
            }
            while (c[iend] > 2 * c[istart]) {
                iend--;
            }
            remove += cntGreaterThanX.get(c[iend]);
            minRemove = Math.min(minRemove, remove);
        }
        out.println(minRemove);
    }
}

Codeforces Round #154 (Div. 2): A - Boys and Girls

// Codeforces Round #154 (Div. 2): A - Boys and Girls

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

//codeforces
public class Main2 {
    private static Scanner in;
    private static PrintStream out = System.out;

    public static void main(String[] args) throws IOException {
        // helpers for input/output
        boolean LOCAL_TEST = false;
        // LOCAL_TEST = true;// comment it before submitting
        in = new Scanner(System.in);
        if (LOCAL_TEST) {
            in = new Scanner(new FileInputStream("E:\\zin2.txt"));
        }

        in = new Scanner(new FileInputStream("input.txt"));
        out = new PrintStream("output.txt");
        solve();
    }

    private static void solve()
    {
        int N = in.nextInt();
        int M = in.nextInt();
        boolean moreBoys = false;
        if (N >= M)
            moreBoys = true;
        while (N > 0 || M > 0) {
            if (moreBoys) {
                if (N > 0) {
                    out.print("B");
                    N--;
                }
                if (M > 0) {
                    out.print("G");
                    M--;
                }
            }
            else {
                if (M > 0) {
                    out.print("G");
                    M--;
                }
                if (N > 0) {
                    out.print("B");
                    N--;
                }
            }
        }
        System.out.println("");
    }

}

Monday, December 10, 2012

Codeforces Round #153 (Div. 2): C - Points on Line

//  Codeforces Round #153 (Div. 2): C - Points on Line

import java.io.FileInputStream;
import java.io.IOException;
import java.math.*;
import java.util.*;

public class Main2 {
    private static Scanner in;

    public static void main(String[] args) throws IOException {
        // helpers for input/output
        boolean LOCAL_TEST = false;
        // LOCAL_TEST = true;// comment it before submitting
        in = new Scanner(System.in);
        if (LOCAL_TEST) {
            in = new Scanner(new FileInputStream("E:\\zin2.txt"));
        }

        Integer N = in.nextInt();
        Long D = in.nextLong();
        Long[] nums = new Long[N];
        for (int i = 0; i < N; i++) {
            nums[i] = in.nextLong();
        }

        long[] plusplus = new long[100001];
        plusplus[0] = 0;
        for (int i = 1; i < plusplus.length; i++) {
            plusplus[i] += plusplus[i - 1] + i;
        }
        Long cnt = 0L;
        for (int i = 0; i < N - 2; i++) {
            int iendMin = i + 2;
            int iendMax = N - 1;
            int iL = iendMin;
            int iR = iendMax;
            int iend = (iL + iR) / 2;
            while (iL < iR) {
                if (nums[iend] - nums[i] > D)
                    iR = iend - 1;
                else
                    iL = iend + 1;
                iend = (iL + iR) / 2;
            }
            if (nums[iend] - nums[i] > D)
                iend--;
            int nn = iend - i - 1;
            // calc 1+2+3+...+nn
            if (nn > 0)
            {
                long add = plusplus[nn];
                cnt += add;
            }
        }
        System.out.println(cnt);

    }

}

Friday, December 7, 2012

Codeforces Round #153 (Div. 2): B - Unsorting Array

// Codeforces Round #153 (Div. 2): B - Unsorting Array

import java.io.FileInputStream;
import java.io.IOException;
import java.math.*;
import java.util.*;

public class Main2 {
    private static Scanner in;

    public static void main(String[] args) throws IOException {
        // helpers for input/output
        boolean LOCAL_TEST = false;
        // LOCAL_TEST = true;// comment it before submitting
        in = new Scanner(System.in);
        if (LOCAL_TEST) {
            in = new Scanner(new FileInputStream("E:\\zin2.txt"));
        }

        int N = in.nextInt();
        int[] nums = new int[N];
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < N; i++) {
            nums[i] = in.nextInt();
            if (nums[i] < min) {
                min = nums[i];
            }
            if (nums[i] > max) {
                max = nums[i];
            }
            if (!map.containsKey(nums[i]))
                map.put(nums[i], 1);
            else
                map.put(nums[i], map.get(nums[i]) + 1);
        }
        if (N <= 2) {
            System.out.println(-1);
            return;
        }
        if (map.size() == 1) {
            System.out.println(-1);
            return;
        }

        // for
        boolean isSortedAsc = isAscending(nums);
        boolean isSortedDesc = isDescending(nums);
        if (isSortedAsc || isSortedDesc) {
            for (int i = 0; i < N - 1; i++) {
                if (nums[i] != nums[i + 1]) {
                    System.out.println((i + 1) + " " + (i + 2));
                    return;
                }
            }
        }
        else {
            for (int i = 1; i < N - 1; i++) {
                int x = nums[i];
                if (x != min && x != max && x != nums[0]) {
                    System.out.println((i + 1) + " " + 1);
                    return;
                }
                if (x != min && x != max && x != nums[N - 1]) {
                    System.out.println((i + 1) + " " + (N));
                    return;
                }
            }
            for (int i = 0; i < N - 1; i++) {
                for (int j = i + 1; j < N; j++) {
                    if (nums[i] != nums[j]) {
                        int tmp = nums[i];
                        nums[i] = nums[j];
                        nums[j] = tmp;
                        if (!isSorted(nums)) {
                            System.out.println((i + 1) + " " + (j + 1));
                            return;
                        }
                        else {
                            tmp = nums[i];
                            nums[i] = nums[j];
                            nums[j] = tmp;
                        }
                    }
                }
            }
        }
        System.out.println(-1);
    }

    static boolean isSorted(int[] n)
    {
        return (isAscending(n) || isDescending(n));
    }

    static boolean isAscending(int[] n) {
        boolean isSortedAscending = true;
        for (int i = 1; i < n.length; i++) {
            if (n[i] < n[i - 1])
                isSortedAscending = false;
        }
        return isSortedAscending;
    }

    static boolean isDescending(int[] n) {
        boolean isSortedDescending = true;
        for (int i = 1; i < n.length; i++) {
            if (n[i] > n[i - 1])
                isSortedDescending = false;
        }
        return isSortedDescending;
    }
}

Tuesday, December 4, 2012

Topcoder SRM 466 DIV 2, L2: LotteryCheating

// Topcoder SRM 466 DIV 2, L2: LotteryCheating

import java.util.*;

class TopcoderSolution {
    public static void main(String[] args) {
        LotteryCheating obj = new LotteryCheating();
        System.out.println(
                obj.minimalChange("7654321")
                );
    }
}

// change to public before submit
public class LotteryCheating {
    List<String> winnums;

    public int minimalChange(String ID) {
        int len = ID.length();
        winnums = new ArrayList<String>();
        for (long i = 0; i <= 100000; i++) {
            long sqr = i * i;
            String sn = String.valueOf(sqr);
            if (sn.length() > len)
                break;
            String s = "0000000000" + sn;
            s = s.substring(s.length() - len);
            winnums.add(s);
        }
        int min = Integer.MAX_VALUE;
        for (String s : winnums) {
            min = Math.min(min, CountDiff(s, ID));
        }

        return min;
    }

    private int CountDiff(String s, String id) {
        int cnt = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) != id.charAt(i))
                cnt++;
        }
        return cnt;
    }

}

Topcoder SRM 466 DIV 2, L1: LotteryTicket

// Topcoder SRM 466 DIV 2, L1: LotteryTicket

import java.util.*;

class TopcoderSolution {
    public static void main(String[] args) {
        LotteryTicket obj = new LotteryTicket();
        System.out.println(
                obj.buy(10, 1, 5, 10, 50)
                );
    }
}

// change to public before submit
class LotteryTicket {
    public String buy(int price, int b1, int b2, int b3, int b4) {
        int[] b = new int[] { b1, b2, b3, b4 };
        for (int i = 0; i < 16; i++) {
            int sum = 0;
            for (int j = 0; j < 4; j++) {
                if ((i >> j & 1) == 1) {
                    sum += b[j];
                }
            }
            if (sum == price) {
                return "POSSIBLE";
            }
        }
        return "IMPOSSIBLE";
    }

}

Topcoder SRM 467 DIV 2, L1: ShorterSuperSum

// Topcoder SRM 467 DIV 2, L1: ShorterSuperSum

import java.util.*;

class TopcoderSolution {
    public static void main(String[] args) {
        ShorterSuperSum obj = new ShorterSuperSum();
        System.out.println(
                obj.calculate(14, 14)
                );
    }
}

// change to public before submit
class ShorterSuperSum {
    public int calculate(int k, int n) {
        return SuperSum(k, n);
    }

    private int SuperSum(int k, int n) {
        if (k == 0)
            return n;
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            sum += SuperSum(k - 1, i);
        }
        return sum;
    }

}

Monday, December 3, 2012

CodeEval Ugly Numbers

// CodeEval Ugly Numbers

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.*;

class Main {
    public static void main(String[] args) {
        ugly_numbers.main(args);
    }
}

class ugly_numbers {
    public static void main(String[] args) {
        boolean LOCAL_TEST = false;
        // LOCAL_TEST = true;// comment it before submitting
        if (LOCAL_TEST)
            CodeEvalGetInput("e:\\zin.txt");
        else
            CodeEvalGetInput(args[0]);
    }

    public static void CodeEvalGetInput(String arg) {
        try {
            File file = new File(arg);
            BufferedReader in = new BufferedReader(new FileReader(file));
            Initialize();
            String line;
            while ((line = in.readLine()) != null) {
                String[] lineArray = line.split(",");
                if (lineArray.length > 0) {
                    // Process line of input Here
                    Process(lineArray);
                }
            }
        } catch (IOException e) {
            System.out.println("File Read Error: " + e.getMessage());
        }
    }

    private static void Initialize() {
    }

    static long totUgly;

    private static void Process(String[] lineArray) {
        String s0 = lineArray[0].trim();
        long lastPart = Long.valueOf(s0.substring(0, 1));
        totUgly = 0;
        Generate('+', lastPart, s0, 1, lastPart);
        System.out.println(totUgly);
    }

    private static boolean IsUgly(long n) {
        if (n == 0 || n % 2 == 0 || n % 3 == 0
                || n % 5 == 0 || n % 7 == 0)
            return true;
        return false;
    }

    private static void Generate(char lastSign, long lastPart, String s, int xc,
            long currentSum) {
        if (xc == s.length()) {
            if (IsUgly(currentSum))
                totUgly++;
            return;
        }
        else {
            String firstChar = String.valueOf(s.charAt(xc));
            long newLastPart;
            long newCurSum;
            // concat
            newLastPart = (Math.abs(lastPart) * 10) + Long.valueOf(firstChar);
            if (lastSign == '+')
                newCurSum = currentSum - lastPart + newLastPart;
            else
                newCurSum = currentSum + lastPart - newLastPart;
            Generate(lastSign, newLastPart, s, xc + 1, newCurSum);
            // +
            newLastPart = Long.valueOf(firstChar);
            newCurSum = currentSum + newLastPart;
            Generate('+', newLastPart, s, xc + 1, newCurSum);
            // -
            newLastPart = Long.valueOf(firstChar);
            newCurSum = currentSum - newLastPart;
            Generate('-', newLastPart, s, xc + 1, newCurSum);
        }
    }
}

CodeEval String List

// CodeEval String List

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.*;

class Main {
    public static void main(String[] args) {
        string_list.main(args);
    }
}

class string_list {
    public static void main(String[] args) {
        boolean LOCAL_TEST = false;
        // LOCAL_TEST = true;// comment it before submitting
        if (LOCAL_TEST)
            CodeEvalGetInput("e:\\zin.txt");
        else
            CodeEvalGetInput(args[0]);
    }

    public static void CodeEvalGetInput(String arg) {
        try {
            File file = new File(arg);
            BufferedReader in = new BufferedReader(new FileReader(file));
            Initialize();
            String line;
            while ((line = in.readLine()) != null) {
                String[] lineArray = line.split(",");
                if (lineArray.length > 0) {
                    // Process line of input Here
                    Process(lineArray);
                }
            }
        } catch (IOException e) {
            System.out.println("File Read Error: " + e.getMessage());
        }
    }

    private static void Initialize() {
    }

    private static void Process(String[] lineArray) {
        Integer n = Integer.valueOf(lineArray[0]);
        String s0 = lineArray[1];
        char[] cs0 = s0.toCharArray();
        Set<Character> cset = new TreeSet<Character>();
        for (int i = 0; i < cs0.length; i++) {
            cset.add(cs0[i]);
        }
        String s = "";
        for (Character c : cset) {
            s += c.toString();
        }
        Integer slen = s.length();
        Set<String> set = new LinkedHashSet<String>();
        FillSet("", s, set, n);
        String[] ss = set.toArray(new String[set.size()]);
        for (int i = 0; i < ss.length; i++) {
            if (i > 0)
                System.out.print(",");
            System.out.print(ss[i]);
        }
        System.out.println();
    }

    private static void FillSet(String pre, String s, Set<String> set, int n) {
        if (pre.length() == n) {
            set.add(pre);
        }
        else {
            for (int i = 0; i < s.length(); i++) {
                String s2 = pre + s.substring(i, i + 1);
                FillSet(s2, s, set, n);
            }
        }
    }

}

CodeEval String Permutations

// CodeEval String Permutations

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.*;

class Main {
    public static void main(String[] args) {
        str_perm.main(args);
    }
}

class str_perm {
    public static void main(String[] args) {
        boolean LOCAL_TEST = false;
        // LOCAL_TEST = true;// comment it before submitting
        if (LOCAL_TEST)
            CodeEvalGetInput("e:\\zin.txt");
        else
            CodeEvalGetInput(args[0]);
    }

    public static void CodeEvalGetInput(String arg) {
        try {
            File file = new File(arg);
            BufferedReader in = new BufferedReader(new FileReader(file));
            Initialize();
            String line;
            while ((line = in.readLine()) != null) {
                String[] lineArray = line.split(";");
                if (lineArray.length > 0) {
                    // Process line of input Here
                    Process(lineArray);
                }
            }
        } catch (IOException e) {
            System.out.println("File Read Error: " + e.getMessage());
        }
    }

    private static void Initialize() {
    }

    private static void Process(String[] lineArray) {
        String s = lineArray[0];
        List<String> ss = GetPermutation(s);
        Collections.sort(ss);
        System.out.print(ss.get(0));
        for (int i = 1; i < ss.size(); i++) {
            System.out.print("," + ss.get(i));
        }
        System.out.println();
    }

    public static List<String> GetPermutation(String s) {
        List<String> result = new ArrayList<String>();
        Permutation("", s, result);
        return result;
    }

    private static void Permutation(String prefix, String s, List<String> result) {
        int n = s.length();
        if (n == 0)
            result.add(prefix);
        else {
            for (int i = 0; i < n; i++)
                Permutation(prefix + s.charAt(i),
                        s.substring(0, i) + s.substring(i + 1), result);
        }
    }
}

Sunday, December 2, 2012

Topcoder SRM 471 DIV 2, L1 PrimeContainers

// Topcoder PrimeContainers

import java.util.*;

class TopcoderSolution {
    public static void main(String[] args) {
        PrimeContainers obj = new PrimeContainers();
        System.out.println(
                obj.containerSize(47)
                );
    }
}

// change to public before submit
public class PrimeContainers {
    public int containerSize(int N)
    {
        boolean[] primes = GetPrimeTable(1000000);
        int div = 1;
        int cnt = 0;
        while (true) {
            if (N / div == 0)
                break;
            if (primes[N / div])
                cnt++;
            div *= 2;
        }
        return cnt;
    }

    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 562 DIV 2, L1: CucumberMarket

// Topcoder SRM 562 DIV 2, L1: CucumberMarket

import java.util.*;

class TopcoderSolution {
    public static void main(String[] args) {
        CucumberMarket obj = new CucumberMarket();
        System.out.println(obj.check(new int[] { 1, 2, 3, 4, 5 },
                10, 3));
    }
}

// change to public before submit
class CucumberMarket {
    public String check(int[] price, int budget, int k) {
        Arrays.sort(price);
        ReversePrimitiveArray(price);
        int sum = 0;
        for (int i = 0; i < k; i++) {
            sum += price[i];
        }
        if (sum <= budget)
            return "YES";
        else
            return "NO";
    }

    public static void ReversePrimitiveArray(int[] a) {
        for (int l = 0, r = a.length - 1; l < r; l++, r--) {
            int temp = a[l];
            a[l] = a[r];
            a[r] = temp;
        }
    }

}

CodeEval Prefix expressions

// CodeEval Prefix expressions

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.*;

class Main {
    public static void main(String[] args) {
        prefix.main(args);
    }
}

class prefix {
    public static void main(String[] args) {
        boolean LOCAL_TEST = false;
        // LOCAL_TEST = true;// comment it before submitting
        if (LOCAL_TEST)
            CodeEvalGetInput("e:\\zin.txt");
        else
            CodeEvalGetInput(args[0]);
    }

    public static void CodeEvalGetInput(String arg) {
        try {
            File file = new File(arg);
            BufferedReader in = new BufferedReader(new FileReader(file));
            Initialize();
            String line;
            while ((line = in.readLine()) != null) {
                String[] lineArray = line.split("\\s");
                if (lineArray.length > 0) {
                    // Process line of input Here
                    Process(lineArray);
                }
            }
        } catch (IOException e) {
            System.out.println("File Read Error: " + e.getMessage());
        }
    }

    private static void Initialize() {
    }

    private static void Process(String[] lineArray) {
        Stack<String> stk = new Stack<String>();
        for (int i = 0; i < lineArray.length; i++) {
            String s = lineArray[i];
            if (IsOperator(s))
                stk.push(s);
            else {
                if (IsOperator(stk.peek())) {
                    stk.push(s);
                } else {
                    double operand1 = Double.valueOf(stk.pop());
                    double operand2 = Double.valueOf(s);
                    String operator = stk.pop();
                    double result = 0;
                    if (operator.equals("+"))
                        result = operand1 + operand2;
                    if (operator.equals("*"))
                        result = operand1 * operand2;
                    if (operator.equals("/"))
                        result = operand1 / operand2;
                    stk.push(String.valueOf(result));
                }
            }
        }
        System.out.println(Double.valueOf(stk.pop()).intValue());
    }

    static boolean IsOperator(String s) {
        return ("+*/".contains(s));
    }
}

CodeEval Longest Common Subsequence

// CodeEval Longest Common Subsequence

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;

class Main {
    public static void main(String[] args) {
        lcs.main(args);
    }
}

class lcs {
    public static void main(String[] args) {
        boolean LOCAL_TEST = false;
        // LOCAL_TEST = true;// comment it before submitting
        if (LOCAL_TEST)
            CodeEvalGetInput("e:\\zin.txt");
        else
            CodeEvalGetInput(args[0]);
    }

    public static void CodeEvalGetInput(String arg) {
        try {
            File file = new File(arg);
            BufferedReader in = new BufferedReader(new FileReader(file));
            Initialize();
            String line;
            while ((line = in.readLine()) != null) {
                if (line.trim().equals(""))
                    continue;
                String[] lineArray = line.split(";");
                if (lineArray.length > 0) {
                    // Process line of input Here
                    Process(lineArray);
                }
            }
        } catch (IOException e) {
            System.out.println("File Read Error: " + e.getMessage());
        }
    }

    private static void Initialize() {
    }

    private static void Process(String[] lineArray) {
        String S1 = lineArray[0].trim();
        String S2 = lineArray[1].trim();
        String lcs = LCSAsString(S1, S2);
        System.out.println(lcs.trim());
    }

    public static String LCSAsString(String X, String Y) {
        int M = X.length();
        int N = Y.length();
        int[][] lcs = new int[M + 1][N + 1];
        String[][] lcsString = new String[M + 1][N + 1];
        for (int i = 0; i <= M; i++) {
            lcs[i][0] = 0;
            lcsString[i][0] = "";
        }
        for (int j = 0; j <= N; j++) {
            lcs[0][j] = 0;
            lcsString[0][j] = "";
        }
        for (int i = 1; i <= M; i++)
            for (int j = 1; j <= N; j++) {
                if (X.charAt(i - 1) == Y.charAt(j - 1)) {
                    lcs[i][j] = lcs[i - 1][j - 1] + 1;
                    lcsString[i][j] = lcsString[i - 1][j - 1]
                            + String.valueOf(X.charAt(i - 1));
                } else {
                    lcs[i][j] = Math.max(lcs[i - 1][j], lcs[i][j - 1]);
                    if (lcs[i - 1][j] > lcs[i][j - 1])
                        lcsString[i][j] = lcsString[i - 1][j];
                    else
                        lcsString[i][j] = lcsString[i][j - 1];
                }
            }
        return lcsString[M][N];
    }

}

Saturday, December 1, 2012

CodeEval Cash Register

// CodeEval Cash Register

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;

class Main {
    public static void main(String[] args) {
        cash_register.main(args);
    }
}

class cash_register {
    public static void main(String[] args) {
        boolean LOCAL_TEST = false;
        // LOCAL_TEST = true;// comment it before submitting
        if (LOCAL_TEST)
            CodeEvalGetInput("e:\\zin.txt");
        else
            CodeEvalGetInput(args[0]);
    }

    public static void CodeEvalGetInput(String arg) {
        try {
            File file = new File(arg);
            BufferedReader in = new BufferedReader(new FileReader(file));
            Initialize();
            String line;
            while ((line = in.readLine()) != null) {
                String[] lineArray = line.split(";");
                if (lineArray.length > 0) {
                    // Process line of input Here
                    Process(lineArray);
                }
            }
        } catch (IOException e) {
            System.out.println("File Read Error: " + e.getMessage());
        }
    }

    static Map<Double, String> coins;
    static List<Double> coinvals;

    private static void Initialize() {
        coins = new LinkedHashMap<Double, String>();
        coins.put(100.0d, "ONE HUNDRED");
        coins.put(50.0d, "FIFTY");
        coins.put(20.0d, "TWENTY");
        coins.put(10.0d, "TEN");
        coins.put(5.0d, "FIVE");
        coins.put(2.0d, "TWO");
        coins.put(1.0d, "ONE");
        coins.put(0.5d, "HALF DOLLAR");
        coins.put(0.25d, "QUARTER");
        coins.put(0.1d, "DIME");
        coins.put(0.05d, "NICKEL");
        coins.put(0.01d, "PENNY");
        coinvals = new ArrayList<Double>();
        Set<Double> v = coins.keySet();
        for (Double d : v) {
            coinvals.add(d);
        }
    }

    private static void Process(String[] lineArray) {
        double PP = Double.valueOf(lineArray[0]);
        double CH = Double.valueOf(lineArray[1]);
        // System.out.println(PP + ";" + CH + "  :  " + (PP - CH));
        if (CH < PP) {
            System.out.println("ERROR");
            return;
        } else if (CH - PP < 0.001) {
            System.out.println("ZERO");
            return;
        } else {
            List<String> chg = new ArrayList<String>();
            double money = CH - PP + 0.001;
            while (money > 0.005) {
                for (Double val : coinvals) {
                    if (money >= val) {
                        money -= val;
                        String c = coins.get(val);
                        chg.add(c);
                        break;
                    }
                }
            }
            String[] achg = chg.toArray(new String[chg.size()]);
            Arrays.sort(achg);
            for (int i = 0; i < chg.size(); i++) {
                if (i > 0)
                    System.out.print(",");
                System.out.print(achg[i]);
            }
            System.out.println();
        }
    }
}