Saturday, December 3, 2011

Dec 03, 2011.
Tutorial

Problem: 133A.

Source Code:

/**
* Implementation.
*/

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

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

}

Solution:

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

Source Code:

/**
* @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 {
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;
}
}
}

Solution:

Problem: 132A.
Do what the statement say.

Source Code:

/**
* 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 {
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;
}
}

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.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 {
program = new ArrayList<String>();
x = 0;
y = 0;
int DP = 0;
int CP = (DP + 3) % 4;
N = Integer.parseInt(strLine.split(" ")[0]);
int K = Integer.parseInt(strLine.split(" ")[1]);
for (int i = 0; i < N; i++)
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;
}