Friday, May 31, 2013

Codeforces Round #184 (Div. 2) B Continued Fractions

// Codeforces Round #184 (Div. 2) B Continued Fractions

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

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

    private static void solve() throws IOException
    {
        long p = in.nextLong();
        long q = in.nextLong();
        int n = in.nextInt();
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = in.nextLong();
        }
        long fractiona = 1;
        long fractionb = 1;
        long xa = 1;
        long xb = 1;
        if (n == 1)
            fractiona = a[0];
        else {
            xa = 1;
            xb = a[n - 1];
            for (int i = n - 1; i >= 1; i--) {
                double xbd = (a[i - 1] * (double) xb) + xa;
                if (xbd > 1e18) {
                    out.println("NO");
                    return;
                }
                long oldxb = xb;
                xb = (a[i - 1] * xb) + xa;
                xa = oldxb;
            }
            fractiona = xb;
            fractionb = xa;
        }
        BigInteger bp = new BigInteger(String.valueOf(p));
        BigInteger bq = new BigInteger(String.valueOf(q));
        BigInteger bfa = new BigInteger(String.valueOf(fractiona));
        BigInteger bfb = new BigInteger(String.valueOf(fractionb));
        if (bp.multiply(bfb).equals(bq.multiply(bfa)))
            // if (p * fractionb == q * fractiona)
            out.println("YES");
        else
            out.println("NO");
        // out.println();
    }

    public static void main(String[] args) throws IOException {
        // helpers for input/output
        out = System.out;
        try {
            String cname = System.getenv("COMPUTERNAME");
            LOCAL_TEST = (cname.equals("ALPHA530"));
        } 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 {
        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();
        }

    }

}

Thursday, May 30, 2013

Codeforces Round #183 (Div. 2) C Lucky Permutation Triple

// Codeforces Round #183 (Div. 2) C Lucky Permutation Triple

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

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

    private static void solve() throws IOException
    {
        int N = in.nextInt();
        if (N % 2 == 0) {
            out.println(-1);
            return;
        }
        int[] a = new int[N];
        int[] b = new int[N];
        int[] c = new int[N];
        for (int i = 0; i < a.length; i++) {
            a[i] = i;
            b[i] = (a[i] + 1) % N;
            c[i] = (a[i] + b[i]) % N;
        }
        for (int i = 0; i < N; i++) {
            out.print("" + a[i] + " ");
        }
        out.println();
        for (int i = 0; i < N; i++) {
            out.print("" + b[i] + " ");
        }
        out.println();
        for (int i = 0; i < N; i++) {
            out.print("" + c[i] + " ");
        }
    }

    public static void main(String[] args) throws IOException {
        // helpers for input/output
        out = System.out;
        try {
            String cname = System.getenv("COMPUTERNAME");
            LOCAL_TEST = (cname.equals("ALPHA530"));
        } 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 {
        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();
        }

    }

}

Codeforces Round #183 (Div. 2) B Calendar

// Codeforces Round #183 (Div. 2) B Calendar

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

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

    private static void solve() throws IOException
    {
        String s1 = in.nextString();
        String s2 = in.nextString();
        String stemp;
        if (s1.compareTo(s2) > 0) {
            stemp = s1;
            s1 = s2;
            s2 = stemp;
        }
        String[] ss1 = s1.split(":");
        String[] ss2 = s2.split(":");
        int[] maxdate = new int[] { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30,
                31 };
        int[] date1 = new int[3];
        int[] date2 = new int[3];
        for (int i = 0; i < 3; i++) {
            date1[i] = Integer.valueOf(ss1[i]);
            date2[i] = Integer.valueOf(ss2[i]);
        }
        int i = 0;
        while (true) {
            boolean equal = true;
            for (int j = 0; j < 3; j++) {
                if (date1[j] != date2[j])
                    equal = false;
            }
            if (equal)
                break;

            i++;
            // inc date1
            boolean leapyear = false;
            if (date1[0] % 400 == 0)
                leapyear = true;
            else if (date1[0] % 100 == 0)
                leapyear = false;
            else if (date1[0] % 4 == 0)
                leapyear = true;
            int curMaxDate = maxdate[date1[1]];
            if (date1[1] == 2 && leapyear)
                curMaxDate = 29;

            if (date1[2] == curMaxDate)
                date1[2] = 1;
            else
                date1[2] += 1;
            if (date1[2] == 1) {
                if (date1[1] == 12)
                    date1[1] = 1;
                else
                    date1[1] += 1;
                if (date1[1] == 1)
                    date1[0]++;
            }

        }

        out.println(i);
    }

    public static void main(String[] args) throws IOException {
        // helpers for input/output
        out = System.out;
        try {
            String cname = System.getenv("COMPUTERNAME");
            LOCAL_TEST = (cname.equals("ALPHA530"));
        } 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 {
        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();
        }

    }

}

Codeforces Round #183 (Div. 2) A Pythagorean Theorem II

//Codeforces Round #183 (Div. 2) A Pythagorean Theorem II
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();
        int i = 0;
        for (int a = 1; a <= n; a++) {
            int bmax2 = (int) Math.sqrt(n * n - a * a) + 1;
            for (int b = a; b <= bmax2; b++) {
                int c2 = (a * a + b * b);
                int c = (int) Math.sqrt(c2);
                if (c <= n && c * c == c2) {
                    i++;
                    // out.println("" + i + ": " + a + " " + b + " " + c);
                }
            }
        }

        out.println(i);
    }

    public static void main(String[] args) throws IOException {
        // helpers for input/output
        out = System.out;
        try {
            String cname = System.getenv("COMPUTERNAME");
            LOCAL_TEST = (cname.equals("ALPHA530"));
        } 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 {
        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, May 28, 2013

Codeforces Round #182 (Div. 2) B Eugeny and Play List

// Codeforces Round #182 (Div. 2) B Eugeny and Play List

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();
        int M = in.nextInt();
        long[] c = new long[N + 1];
        long[] t = new long[N + 1];
        for (int i = 1; i <= N; i++) {
            c[i] = in.nextLong();
            t[i] = in.nextLong();
        }
        long[] tstart = new long[N + 1];
        long[] tend = new long[N + 1];
        tstart[1] = 1;
        tend[1] = 1 + (c[1] * t[1]) - 1;
        for (int i = 2; i <= N; i++) {
            tstart[i] = tend[i - 1] + 1;
            tend[i] = tstart[i] + (c[i] * t[i]) - 1;
        }

        int[] v = new int[M + 1];
        in.nextLine();
        String ln = in.nextLine();
        String[] s = ln.split(" ");
        for (int i = 1; i <= M; i++) {
            v[i] = Integer.valueOf(s[i - 1]);
        }

        StringBuilder sb = new StringBuilder("");
        for (int i = 1; i <= M; i++) {
            int L = 1;
            int R = N;
            int tm = v[i];
            while (L <= R) {
                int idx = (L + R) / 2;
                if (tm >= tstart[idx] && tm <= tend[idx]) {
                    sb.append(idx);
                    sb.append("\n");
                    break;
                }
                if (tm < tstart[idx]) {
                    R = idx - 1;
                }
                else {
                    L = idx + 1;
                }
            }
        }
        out.println(sb.toString());
    }

    public static void main(String[] args) throws IOException {
        // helpers for input/output
        out = System.out;
        try {
            String cname = System.getenv("COMPUTERNAME");
            LOCAL_TEST = (cname.equals("ALPHA530"));
        } 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 {
        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();
        }

    }

}

Codeforces Round #182 (Div. 2) A Eugeny and Array

// Codeforces Round #182 (Div. 2) A Eugeny and Array

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

import org.omg.CORBA.Environment;

//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();
        int M = in.nextInt();
        int numPos = 0;
        int numNeg = 0;
        String line = in.nextLine();
        String[] aline = line.split(" ");
        for (int i = 0; i < N; i++) {
            int x = Integer.valueOf(aline[i]);
            if (x == 1)
                numPos++;
            else
                numNeg++;
        }

        StringBuilder sb = new StringBuilder("");
        for (int i = 0; i < M; i++) {
            int l = in.nextInt();
            int r = in.nextInt();
            int num = r - l + 1;
            if (num % 2 == 0) {
                if (numPos >= num / 2 && numNeg >= num / 2)
                    sb.append("1\n");
                else
                    sb.append("0\n");
            }
            else {
                sb.append("0\n");
            }
        }
        out.println(sb.toString());
    }

    public static void main(String[] args) throws IOException {
        // helpers for input/output
        out = System.out;
        try {
            String cname = System.getenv("COMPUTERNAME");
            LOCAL_TEST = (cname.equals("ALPHA530"));
        } 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 {
        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 {
            inp.nextLine();
            return inp.nextLine();
        }

    }

}

Croc Champ 2013 - Round 2 (Div. 2 Edition) C Weird Game

// Croc Champ 2013 - Round 2 (Div. 2 Edition) C Weird Game

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();
        char[] s = in.nextString().toCharArray();
        char[] t = in.nextString().toCharArray();
        int n10 = 0;
        int n11 = 0;
        int n01 = 0;
        for (int i = 0; i < s.length; i++) {
            if (s[i] == '1' && t[i] == '0')
                n10++;
            else if (s[i] == '1' && t[i] == '1')
                n11++;
            else if (s[i] == '0' && t[i] == '1')
                n01++;
        }
        int ns = 0;
        if (n11 % 2 == 1)
            ns += 1;
        ns += n10 - n01;
        if (ns > 0)
            out.println("First");
        else if (ns >= -1)
            out.println("Draw");
        else
            out.println("Second");
    }

    public static void main(String[] args) throws IOException {
        // helpers for input/output
        out = System.out;
        try {
            String cname = System.getenv("COMPUTERNAME");
            LOCAL_TEST = (cname.equals("ALPHA530"));
        } 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 {
        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();
        }

    }

}

Croc Champ 2013 - Round 2 (Div. 2 Edition) B Ksusha the Squirrel

// Croc Champ 2013 - Round 2 (Div. 2 Edition) B Ksusha the Squirrel

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();
        int K = in.nextInt();
        char[] c = in.nextString().toCharArray();
        int maxAdjacentRocks = 0;
        int nRock = 0;
        if (c[0] == '#')
            nRock = 1;
        for (int i = 1; i < c.length; i++) {
            if (c[i - 1] == '#')
                nRock++;
            else
                nRock = 0;
            maxAdjacentRocks = Math.max(maxAdjacentRocks, nRock);
        }
        if (maxAdjacentRocks < K)
            out.println("YES");
        else
            out.println("NO");
    }

    public static void main(String[] args) throws IOException {
        // helpers for input/output
        out = System.out;
        try {
            String cname = System.getenv("COMPUTERNAME");
            LOCAL_TEST = (cname.equals("ALPHA530"));
        } 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 {
        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();
        }

    }

}

Croc Champ 2013 - Round 2 (Div. 2 Edition) A Ksusha and Array

//Croc Champ 2013 - Round 2 (Div. 2 Edition) A Ksusha and Array
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();
        int[] a = new int[N];
        for (int i = 0; i < a.length; i++) {
            a[i] = in.nextInt();
        }
        Arrays.sort(a);
        int num = a[0];
        for (int i = 1; i < a.length; i++) {
            if (a[i] % num != 0) {
                num = -1;
                break;
            }
        }
        out.println(num);
    }

    public static void main(String[] args) throws IOException {
        // helpers for input/output
        out = System.out;
        try {
            String cname = System.getenv("COMPUTERNAME");
            LOCAL_TEST = (cname.equals("ALPHA530"));
        } 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 {
        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();
        }

    }

}

Saturday, May 25, 2013

Codeforces Round #181 (Div. 2) B Coach

//Codeforces Round #181 (Div. 2) B Coach

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();
        int m = in.nextInt();
        int[] group = new int[n + 1];
        int grpid = 0;
        for (int i = 0; i < m; i++) {
            int a = in.nextInt();
            int b = in.nextInt();
            if (group[a] == 0 && group[b] == 0) {
                grpid++;
                group[a] = group[b] = grpid;
            }
            else {
                if (group[a] == 0)
                    group[a] = group[b];
                else if (group[b] == 0)
                    group[b] = group[a];
                else {
                    if (group[a] != group[b]) {
                        out.println(-1);
                        return;
                    }
                }
            }
        }
        ArrayList<Integer>[] grpMembers = new ArrayList[grpid + 1];
        for (int i = 1; i < grpMembers.length; i++) {
            grpMembers[i] = new ArrayList<Integer>();
        }
        ArrayList<Integer> anygroup = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            int grp = group[i];
            if (grp > 0)
                grpMembers[grp].add(i);
            else
                anygroup.add(i);
        }
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        int anyGroupTaken = 0;
        for (int i = 1; i < grpMembers.length; i++) {
            if (grpMembers[i].size() > 3) {
                out.println(-1);
                return;
            }
            else if (grpMembers[i].size() == 3) {
                result.add(grpMembers[i]);
            }
            else {
                if (anyGroupTaken >= anygroup.size()) {
                    out.println(-1);
                    return;
                }
                int addAny = 3 - grpMembers[i].size();
                for (int j = 0; j < addAny; j++) {
                    grpMembers[i].add(anygroup.get(anyGroupTaken++));
                }
                result.add(grpMembers[i]);
            }
        }
        while (anyGroupTaken < anygroup.size()) {
            ArrayList<Integer> g = new ArrayList<>();
            for (int i = 0; i < 3; i++) {
                g.add(anygroup.get(anyGroupTaken++));
            }
            result.add(g);
        }
        for (int i = 0; i < result.size(); i++) {
            out.println("" + result.get(i).get(0) +
                    " " + result.get(i).get(1) +
                    " " + result.get(i).get(2));
        }
        out.println();
    }

    public static void main(String[] args) throws IOException {
        // helpers for input/output
        out = System.out;
        try {
            String cname = System.getenv("COMPUTERNAME");
            LOCAL_TEST = (cname.equals("ALPHA530"));
        } 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 {
        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 #181 (Div. 2) A Array

// Codeforces Round #181 (Div. 2) A Array

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();
        ArrayList<Integer> zero = new ArrayList<>();
        ArrayList<Integer> pos = new ArrayList<>();
        ArrayList<Integer> neg = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int a = in.nextInt();
            if (a == 0)
                zero.add(0);
            else if (a < 0)
                neg.add(a);
            else
                pos.add(a);
        }

        out.println("1 " + neg.get(0));

        if (pos.size() > 0) {
            out.print(pos.size());
            for (int i = 0; i < pos.size(); i++) {
                out.print(" " + pos.get(i));
            }
            out.println();

            out.print(zero.size() + neg.size() - 1);
            for (int i = 0; i < zero.size(); i++) {
                out.print(" 0");
            }
            for (int i = 1; i < neg.size(); i++) {
                out.print(" " + neg.get(i));
            }
            out.println();
        }
        else {
            out.print("2");
            out.print(" " + neg.get(1));
            out.print(" " + neg.get(2));
            out.println();

            out.print(zero.size() + neg.size() - 3);
            for (int i = 0; i < zero.size(); i++) {
                out.print(" 0");
            }
            for (int i = 3; i < neg.size(); i++) {
                out.print(" " + neg.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");
            LOCAL_TEST = (cname.equals("ALPHA530"));
        } 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 {
        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, May 24, 2013

Codeforces Round #180 (Div. 2) C Parity Game

//Codeforces Round #180 (Div. 2) C Parity Game

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 boolean LOCAL_TEST = false;

    private static void solve() throws IOException
    {
        char[] a = in.nextString().toCharArray();
        char[] b = in.nextString().toCharArray();
        int num1a = 0;
        int num1b = 0;
        for (int i = 0; i < a.length; i++) {
            if (a[i] == '1') {
                num1a++;
            }
        }
        int maxNum1a = (num1a % 2 == 0) ? num1a : num1a + 1;
        for (int i = 0; i < b.length; i++) {
            if (b[i] == '1')
                num1b++;
        }

        boolean possible;
        if (num1a == 0)
            if (num1b > 0)
                possible = false;
            else
                possible = true;
        else if (num1b <= 2) {
            possible = true;
        }
        else {
            if (maxNum1a < num1b)
                possible = false;
            else {
                possible = true;
            }
        }

        out.println(possible ? "YES" : "NO");
    }

    public static void main(String[] args) throws IOException {
        // helpers for input/output
        out = System.out;
        try {
            String cname = System.getenv("COMPUTERNAME");
            LOCAL_TEST = (cname.equals("ALPHA530"));
        } 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 {
        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();
        }

    }

}

Tuesday, May 21, 2013

Codeforces Round #180 (Div. 2) B Sail

//Codeforces Round #180 (Div. 2) B Sail

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 boolean LOCAL_TEST = false;

    private static void solve() throws IOException
    {
        int t = in.nextInt();
        int sx = in.nextInt();
        int sy = in.nextInt();
        int ex = in.nextInt();
        int ey = in.nextInt();
        String dir = in.nextString();
        for (int i = 0; i < dir.length(); i++) {
            char c = dir.charAt(i);
            if (sx < ex && c == 'E')
                sx++;
            if (sx > ex && c == 'W')
                sx--;
            if (sy < ey && c == 'N')
                sy++;
            if (sy > ey && c == 'S')
                sy--;
            if (sx == ex && sy == ey) {
                out.println(i + 1);
                return;
            }
        }
        out.println("-1");
    }

    public static void main(String[] args) throws IOException {
        // helpers for input/output
        out = System.out;
        try {
            String cname = System.getenv("COMPUTERNAME");
            LOCAL_TEST = (cname.equals("ALPHA530"));
        } 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 {
        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, May 20, 2013

Codeforces Round #180 (Div. 2) A Snow Footprints

// Codeforces Round #180 (Div. 2) A Snow Footprints

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;
    // change to false before submitting
    private static boolean LOCAL_TEST = false;

    private static void solve() throws IOException
    {
        int N = in.nextInt();
        String road = in.nextString();
        int rFirst = -1;
        int rLast = -1;
        int lFirst = -1;
        int lLast = -1;
        for (int i = 0; i < N; i++) {
            if (road.charAt(i) == 'R') {
                if (rFirst == -1)
                    rFirst = i + 1;
                rLast = i + 1;
            }
            if (road.charAt(i) == 'L') {
                if (lFirst == -1)
                    lFirst = i + 1;
                lLast = i + 1;
            }
        }
        int start;
        int end;
        if (rFirst > 0)
            start = rFirst;
        else
            start = lLast;
        if (rLast > 0) {
            if (lFirst > 0)
                end = rLast;
            else
                end = rLast + 1;
        }
        else
            end = lFirst - 1;
        out.println("" + start + " " + end);
    }

    public static void main(String[] args) throws IOException {
        // helpers for input/output
        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, May 10, 2013

Croc Champ 2013 - Round 1 B Network Topology

// Croc Champ 2013 - Round 1 B Network Topology

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;
    // change to false before submitting
    private static boolean LOCAL_TEST = false;

    private static void solve() throws IOException
    {
        int N = in.nextInt();
        int M = in.nextInt();
        int[] nodeNumConnected = new int[N + 1];
        for (int i = 1; i < nodeNumConnected.length; i++) {
            nodeNumConnected[i] = 0;
        }
        for (int i = 0; i < M; i++) {
            int x = in.nextInt();
            int y = in.nextInt();
            nodeNumConnected[x] += 1;
            nodeNumConnected[y] += 1;
        }
        boolean isRing = true;
        boolean isBus = true;
        int maxCon = 0;
        int numCon1 = 0;
        int numConNot1 = 0;
        for (int i = 1; i < nodeNumConnected.length; i++) {
            maxCon = Math.max(maxCon, nodeNumConnected[i]);
            if (nodeNumConnected[i] == 1)
                numCon1++;
            else
                numConNot1++;
            if (nodeNumConnected[i] != 2)
                isRing = false;
            if (nodeNumConnected[i] > 2)
                isBus = false;
        }
        if (isBus && numCon1 == 2)
            out.print("bus topology");
        else if (isRing)
            out.print("ring topology");
        else if (numCon1 == N - 1 && numConNot1 == 1 && maxCon == (N - 1))
            out.print("star topology");
        else
            out.print("unknown topology");
    }

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

    }

}