Codeforces Beta Round #96

Dec 03, 2011.

Tutorial

Problem 1:

Solution:

Problem: 133A.

Source Code:

import java.io.BufferedReader;
import java.io.InputStreamReader;

/**
 * Implementation.
 */

/**
 * @author antonio081014
 * @since Dec 3, 2011, 6:48:07 AM
 */
public class A {

    /**
     * @param args
     */
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String strLine = br.readLine();
        if (strLine.contains("H") || strLine.contains("Q")
                || strLine.contains("9")) {
            System.out.println("YES");
        } else
            System.out.println("NO");
    }

}

Problem 2:

Solution:

Problem: 133B.
Here, the property of module is important.

Source Code:

import java.io.BufferedReader;
import java.io.InputStreamReader;

/**
 * @author antonio081014
 * @since Dec 3, 2011, 6:49:18 AM
 */
public class B {

    public static final long mod = 1000003;

    /**
     * @param args
     */
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String strLine = br.readLine();
        long hex = 1;
        long sum = 0;
        for (int i = strLine.length() - 1; i >= 0; i--) {
            sum += ((get(strLine.charAt(i)) * hex) % mod);
            sum %= mod;
            hex *= 16;
            hex %= mod;
        }
        System.out.println(sum);
    }

    public static long get(char c) {
        switch (c) {
        case '>':
            return 8;
        case '<':
            return 9;
        case '+':
            return 10;
        case '-':
            return 11;
        case '.':
            return 12;
        case ',':
            return 13;
        case '[':
            return 14;
        case ']':
            return 15;
        default:
            return 0;
        }
    }
}

Problem 3:

Solution:

Problem: 132A.
Do what the statement say.

Source Code:

import java.io.BufferedReader;
import java.io.InputStreamReader;

/**
 * String, implementation.
 */

/**
 * @author antonio081014
 * @since Dec 3, 2011, 6:49:34 AM
 */
public class C {

    /**
     * @param args
     */
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String strLine = br.readLine();
        int result = 0;

        for (int i = 0; i < strLine.length(); i++) {
            result = translate(result, strLine.charAt(i));
        }
    }

    public static int translate(int result, char c) {
        int n = (int) c;
        int num = reverse(n);
        int ret = (result - num + 256) % 256;
        System.out.println(ret);
        // ret = reverse(ret);
        return num;
    }

    public static int reverse(int number) {
        String tmp = Integer.toBinaryString(number);
        int sum = 0;
        while (number > 0) {
            sum = sum * 2 + number % 2;
            number /= 2;
        }
        if (tmp.length() < 8)
            sum *= (int) Math.pow(2, 8 - tmp.length());
        return sum;
    }
}

Problem 4:

Solution:

Implement the steps statement stated.
BTW, my current solution will get the TLE, which is caused by those two while loops.
This could be reduced by data compression, which could be implemented by data pre-processing.

Source Code:

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

/**
 * Problem: 132B;
 * This problem takes me hours to debug on the logic error I made.
 * However, program still got TLE on some cases,
 * thus I still need to preprocess the data before I go through each step.
 */

/**
 * @author antonio081014
 * @since Dec 3, 2011, 2:18:49 PM
 */
public class B {

    public static int x;
    public static int y;
    public static List<String> program;
    public static final int[] dx = { 1, 0, -1, 0 };
    public static final int[] dy = { 0, 1, 0, -1 };

    public static Rect[][] mem;

    public static int N;
    public static int M;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        program = new ArrayList<String>();
        x = 0;
        y = 0;
        int DP = 0;
        int CP = (DP + 3) % 4;
        String strLine = br.readLine();
        N = Integer.parseInt(strLine.split(" ")[0]);
        int K = Integer.parseInt(strLine.split(" ")[1]);
        for (int i = 0; i < N; i++)
            program.add(br.readLine());
        M = program.get(0).length();
        while (K-- > 0) {
            // move to pixel boundary;
            int xx = x;
            int yy = y;
            while (inBoundary(xx, yy)
                    && program.get(yy).charAt(xx) == program.get(y).charAt(x)) {
                xx += dx[DP];
                yy += dy[DP];
            }
            xx -= dx[DP];
            yy -= dy[DP];

            // move to furthest;
            while (inBoundary(xx, yy)
                    && program.get(yy).charAt(xx) == program.get(y).charAt(x)) {
                xx += dx[CP];
                yy += dy[CP];
            }
            xx -= dx[CP];
            yy -= dy[CP];

            boolean flag = inBoundary(xx + dx[DP], yy + dy[DP]);
            if (!flag
                    || (flag && program.get(yy + dy[DP]).charAt(xx + dx[DP]) == '0')) {
                if (CP == (DP + 3) % 4)
                    CP = (DP + 1) % 4;
                else if (CP == (DP + 1) % 4) {
                    DP = (DP + 1) % 4;
                    CP = (DP + 3) % 4;
                }
            } else {
                x = xx + dx[DP];
                y = yy + dy[DP];
            }
            // System.out.println("DP:" + DP + ", CP:" + CP);
            // System.out.println(flag + " " + xx + " " + yy);
            // System.out.println(program.get(y).charAt(x));
        }
        System.out.println(program.get(y).charAt(x));
    }

    public static void preProcess() {
        mem = new Rect[N][M];
    }

    public static boolean inBoundary(int x, int y) {
        if (x >= 0 && x < M && y >= 0 && y < N)
            return true;
        return false;
    }

}

class Rect {
    public int x1;
    public int y1;
    public int x2;
    public int y2;
}

Problem 5:

Solution:

Source Code:

Problem 6:

Solution:

Source Code:

Problem 7:

Solution:

Source Code: