Codeforces Round #223 (Div. 2) B Sereja and Stairs

// Codeforces Round #223 (Div. 2) B Sereja and Stairs
// Problem: http://codeforces.com/contest/381/problem/B

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

//Codeforces
public class MainCodeforces1 {
private static MyScanner in;
private static PrintStream out;
private static boolean LOCAL_TEST = false;

private static void solve() throws IOException
{
int n = in.nextInt();
Integer[] x = new Integer[n];
for (int i = 0; i < x.length; i++) {
x[i] = in.nextInt();
}
Arrays.sort(x, Collections.reverseOrder());
ArrayList<Integer> list2 = new ArrayList<Integer>();
HashSet<Integer> set1 = new HashSet<Integer>();
list2.add(x[0]);
for (int i = 1; i < x.length; i++) {
if (x[i] < x[i - 1]) {
list2.add(x[i]);
}
else {
if (!x[i].equals(x[0])) {
set1.add(x[i]);
}
}
}
ArrayList<Integer> list1 = new ArrayList<Integer>();
list1.addAll(set1);
Collections.sort(list1);
list1.addAll(list2);
out.println(list1.size());
for (int i = 0; i < list1.size(); i++) {
if (i > 0)
out.print(" ");
out.print(list1.get(i));
}
out.println();
}

public static void main(String[] args) throws IOException {
// helpers for input/output
out = System.out;
try {
String cname = System.getenv("COMPUTERNAME");
if (!cname.equals(""))
LOCAL_TEST = true;
} catch (Exception e) {
}
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 {
BufferedReader bufReader;
StringTokenizer strTok;

public MyScanner() throws IOException
{
bufReader = new BufferedReader(new InputStreamReader(System.in));
strTok = new StringTokenizer("");
}

public MyScanner(String inputFile) throws IOException {
bufReader = new BufferedReader(new InputStreamReader(new FileInputStream(
inputFile)));
strTok = new StringTokenizer("");
}

String GetNextToken() throws IOException {
if (!strTok.hasMoreTokens())
strTok = new StringTokenizer(bufReader.readLine());
return strTok.nextToken();
}

public int nextInt() throws IOException {
return Integer.valueOf(GetNextToken());
}

public long nextLong() throws IOException {
return Long.valueOf(GetNextToken());
}

public double nextDouble() throws IOException {
return Double.valueOf(GetNextToken());
}

public String nextString() throws IOException {
return GetNextToken();
}

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

public int countTokens() {
return strTok.countTokens();
}

public boolean hasMoreTokens() {
return strTok.hasMoreTokens();
}
}

}

Topcoder SRM 586 DIV 2 L1 TeamsSelection

// Topcoder SRM 586 DIV 2 L1 TeamsSelection

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

//rename the class name before submitting
public class TeamsSelection {
public static void main(String[] args) {
TeamsSelection obj = new TeamsSelection();
System.out.println(
obj.simulate(
null,
null
));
}

public String simulate(int[] preference1, int[] preference2) {
String result = "";
HashSet<Integer> selected = new HashSet<Integer>();
HashSet<Integer> selectedBy1 = new HashSet<Integer>();
int N = preference1.length;
for (int i = 0; i < N; i++) {
for (int j1 = 0; j1 < N; j1++) {
if (!selected.contains(preference1[j1])) {
selected.add(preference1[j1]);
selectedBy1.add(preference1[j1]);
break;
}
}
for (int j2 = 0; j2 < N; j2++) {
if (!selected.contains(preference2[j2])) {
selected.add(preference2[j2]);
break;
}
}
}
for (int i = 1; i <= N; i++) {
if (selectedBy1.contains(i))
result += "1";
else
result += "2";
}
return result;
}
}

Topcoder SRM 584 DIV 2 L1 TopFox

// Topcoder SRM 584 DIV 2 L1 TopFox

import java.util.*;

//rename the class name before submitting
public class TopFox {
    public static void main(String[] args) {
        TopFox obj = new TopFox();
        System.out.println(obj.possibleHandles(
                "ab",
                "cd"
                ));
    }

    public int possibleHandles(String familyName, String givenName) {
        HashSet<String> names = new HashSet<String>();
        for (int i = 1; i <= familyName.length(); i++) {
            String s1 = familyName.substring(0, i);
            for (int j = 1; j <= givenName.length(); j++) {
                String s2 = givenName.substring(0, j);
                String s = s1 + s2;
                names.add(s);
            }
        }

        return names.size();
    }
}

Codeforces Round #188 (Div. 2) B Strings of Power

// Codeforces Round #188 (Div. 2) B Strings of Power

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

//Codeforces
public class Codeforces1 {
private static MyScanner in;
private static PrintStream out;
private static boolean LOCAL_TEST = false;

private static void solve() throws IOException {
String s = in.nextString();
long cnt = 0;
ArrayList<Integer> heavyPos = new ArrayList<Integer>();
ArrayList<Integer> metalPos = new ArrayList<Integer>();
int fromIndex = 0;
while (fromIndex < s.length()) {
int pos = s.indexOf("heavy", fromIndex);
if (pos == -1)
break;
else {
heavyPos.add(pos);
fromIndex = pos + 5;
}
}
fromIndex = 0;
while (fromIndex < s.length()) {
int pos = s.indexOf("metal", fromIndex);
if (pos == -1)
break;
else
metalPos.add(pos);
fromIndex = pos + 5;
}
HashMap<Integer, Integer> firstMetalPosLargerThanHeavyPos = new HashMap<Integer, Integer>();
int lastMetalIdx = 0;
for (int i = 0; i < heavyPos.size(); i++) {
int hpos = heavyPos.get(i);
firstMetalPosLargerThanHeavyPos.put(hpos, -1);
for (int j = lastMetalIdx; j < metalPos.size(); j++) {
if (metalPos.get(j) > heavyPos.get(i)) {
firstMetalPosLargerThanHeavyPos.put(hpos, metalPos.get(j));
lastMetalIdx = j;
break;
}
}
}

HashMap<Integer, Integer> cntMetalsLargerThanPos = new HashMap<Integer, Integer>();
for (int i = 0; i < metalPos.size(); i++) {
int pos = metalPos.get(i);
cntMetalsLargerThanPos.put(pos, metalPos.size() - 1 - i);
}

for (int i = 0; i < heavyPos.size(); i++) {
int hpos = heavyPos.get(i);
int firstMetalLarger = firstMetalPosLargerThanHeavyPos.get(hpos);
if (firstMetalLarger < 0)
continue;
long cntMetalLarger = cntMetalsLargerThanPos.get(firstMetalLarger);
cnt += cntMetalLarger + 1;
}

out.println(cnt);
}

public static void main(String[] args) throws IOException {
// helpers for input/output
out = System.out;
try {
String cname = System.getenv("COMPUTERNAME");
if (cname != null)
LOCAL_TEST = true;
} catch (Exception e) {
}
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 {
BufferedReader bufReader;
StringTokenizer strTok;

public MyScanner() throws IOException {
bufReader = new BufferedReader(new InputStreamReader(System.in));
strTok = new StringTokenizer("");
}

public MyScanner(String inputFile) throws IOException {
bufReader = new BufferedReader(new InputStreamReader(new FileInputStream(
inputFile)));
strTok = new StringTokenizer("");
}

String GetNextToken() throws IOException {
if (!strTok.hasMoreTokens())
strTok = new StringTokenizer(bufReader.readLine());
return strTok.nextToken();
}

public int nextInt() throws IOException {
return Integer.valueOf(GetNextToken());
}

public long nextLong() throws IOException {
return Long.valueOf(GetNextToken());
}

public double nextDouble() throws IOException {
return Double.valueOf(GetNextToken());
}

public String nextString() throws IOException {
return GetNextToken();
}

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

public int countTokens() {
return strTok.countTokens();
}

public boolean hasMoreTokens() {
return strTok.hasMoreTokens();
}
}

}

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();
        }
    }

}

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();
        }
    }

}

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();
    }
}

Codeforces Round #177 (Div. 2) E Polo the Penguin and XOR operation

//Codeforces Round #177 (Div. 2) E Polo the Penguin and XOR operation

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;

    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();
    }

    private static void solve() throws IOException
    {
        int n = in.nextInt();
        long sum = 0;
        List<Integer> nums = new ArrayList<Integer>();
        HashSet<Integer> used = new HashSet<Integer>();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i <= n; i++) {
            int x = 1048575;
            int p = ~i & x;
            while (p > n || used.contains(p)) {
                x = x >> 1;
                p = ~i & x;
            }
            int num = p ^ i;
            sum += num;
            nums.add(p);
            used.add(p);
            if (i > 0)
                sb.append(" ");
            sb.append(p);
        }
        out.println(sum);
        out.println(sb);
    }

    // =====================================
    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();
        }

    }

}

Topcoder SRM 574 DIV 2 L2 TheNumberGameDiv2

//Topcoder SRM 574 DIV 2 L2 TheNumberGameDiv2

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

import javax.crypto.spec.PSource;

public class TheNumberGameDiv2 {
    public static void main(String[] args) {
        System.out.println(
                //
                new TheNumberGameDiv2().minimumMoves(
                        218181918,
                        9181
                        ));
    }

    HashSet<Integer> nums = new HashSet<Integer>();
    int minmov;

    public int minimumMoves(int A, int B) {
        if (A == B)
            return 0;
        minmov = Integer.MAX_VALUE;
        dfs(A, B, 0);

        if (minmov == Integer.MAX_VALUE)
            return -1;
        else
            return minmov;
    }

    private void dfs(int a, int b, int mov) {
        if (a == b) {
            minmov = Math.min(minmov, mov);
            return;
        }
        if (a == 0)
            return;
        nums.add(a);
        String rev = new StringBuffer(String.valueOf(a)).reverse().toString();
        int arev = Integer.valueOf(rev);
        if (!nums.contains(arev)) {
            dfs(arev, b, mov + 1);
        }
        dfs(a / 10, b, mov + 1);
    }
}

Codeforces Round #166 (Div. 2) A Beautiful Year

//Codeforces Round #166 (Div. 2) A Beautiful Year

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

//Codeforces
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;// 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();
    }

    private static void solve() throws IOException
    {
        int y = in.nextInt();
        int yy = y + 1;
        HashSet<Character> hs = new HashSet<Character>();
        while (true) {
            boolean distinct = true;
            hs.clear();
            char[] cc = String.valueOf(yy).toCharArray();
            for (char c : cc) {
                if (hs.contains(c)) {
                    distinct = false;
                    break;
                }
                else {
                    hs.add(c);
                }
            }

            if (distinct)
                break;
            yy++;
        }

        out.println(yy);
    }

    static long compare(long a1, long b1, long a2, long b2) {
        // compare a1/b1 with a2/b2
        return (a1 * b2) - (a2 * b1);
    }

    // =====================================
    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();
        }

    }

}

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;
        }
    }

}