# UVA 10855 – Rotated square

This problem has an interesting algorithm used it in. How to rotate a square matrix. Basically if you want to rotate a square matrix by 90 degress you can notice that 4 elements in the 2D array get changed in a cyclical manner. You can just repeat this for (almost) one quarter of the square that you are rotating.

```import java.io.BufferedReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.StringTokenizer;

/**
*
* @author Sanchit M. Bhatnagar
* @see http://uhunt.felix-halim.net/id/74004
*
*/
public class P10855 {

public static void main(String[] args) throws IOException {
PrintWriter out = new PrintWriter(System.out);
StringTokenizer st = null;

while (true) {

int N = Integer.parseInt(st.nextToken());
int n = Integer.parseInt(st.nextToken());
if (N + n == 0)
break;

char[][] big = new char[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
big[i][j] = line[j];
}
}

char[][] small = new char[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
small[i][j] = line[j];
}
}

out.print(check(big, small) + " ");
rotate(small);
out.print(check(big, small) + " ");
rotate(small);
out.print(check(big, small) + " ");
rotate(small);
out.println(check(big, small));
}

out.close();
br.close();
}

private static int check(char[][] big, char[][] small) {
int ans = 0;
for (int i = 0; i <= big.length - small.length; i++) {
for (int j = 0; j <= big.length - small.length; j++) {
if (big[i][j] == small[0][0]) {
boolean found = true;
for (int k = 0; k < small.length; k++) {
for (int l = 0; l < small.length; l++) {
if (big[i + k][j + l] != small[k][l]) {
found = false;
break;
}
}
}
if (found)
ans++;
}
}
}
return ans;
}

private static void rotate(char[][] m) {
int n = m.length;
for (int i = 0; i < n / 2; i++)
for (int j = 0; j < (n + 1) / 2; j++) {
char temp = m[i][j];
m[i][j] = m[n - 1 - j][i];
m[n - 1 - j][i] = m[n - 1 - i][n - 1 - j];
m[n - 1 - i][n - 1 - j] = m[j][n - 1 - i];
m[j][n - 1 - i] = temp;
}
}
}
```

# UVA 101 – The Blocks Problem

Basic simulation. Just need to follow the instructions in the question.

```import java.awt.Point;
import java.util.ArrayList;
import java.util.Scanner;

/**
*
* @author Sanchit M. Bhatnagar
* @see http://uhunt.felix-halim.net/id/74004
*
*/
public class P101 {

public static void main(String args[]) // entry point from OS
{
Scanner sc = new Scanner(System.in);
int size = sc.nextInt();
@SuppressWarnings("unchecked")
ArrayList<Integer>[] blocks = new ArrayList[size];
for (int i = 0; i < size; i++) {
blocks[i] = new ArrayList<Integer>();
}

// System.out.println(Arrays.deepToString(blocks));

while (sc.hasNext()) {
String t = sc.next();
if (t.equals("quit")) {
break;
} else {
int a = sc.nextInt();
String x = sc.next();
int b = sc.nextInt();

if (a == b)
continue;

Point posA = findBlock(a, blocks);
Point posB = findBlock(b, blocks);

if (posA.x == posB.x)
continue;

if (t.equals("move")) {
moveBack(posA, blocks);
if (x.equals("onto")) {
moveBack(posB, blocks);
blocks[posA.x].remove(posA.y);
} else {
blocks[posA.x].remove(posA.y);
}
} else if (t.equals("pile")) {
if (x.equals("onto")) {
moveBack(posB, blocks);
int removed = 0;
int tSize = blocks[posA.x].size();
for (int i = posA.y; i < tSize; i++) {
removed++;
}
} else {
int removed = 0;
int tSize = blocks[posA.x].size();
for (int i = posA.y; i < tSize; i++) {
removed++;
}
}
}
}
// System.out.println(Arrays.deepToString(blocks));
}

// System.out.println(Arrays.deepToString(blocks));

for (int i = 0; i < size; i++) {
System.out.print(i + ":");
int tSize = blocks[i].size();
for (int j = 0; j < tSize; j++) {
System.out.print(" " + blocks[i].remove(0));
}
System.out.println();
}
sc.close();
}

private static void moveBack(Point posA, ArrayList<Integer>[] blocks) {
int removed = 0;
int tSize = blocks[posA.x].size();
for (int i = posA.y + 1; i < tSize; i++) {
int x = (Integer) blocks[posA.x].remove(i - removed);
removed++;
}
}

private static Point findBlock(int a, ArrayList<Integer>[] blocks) {
for (int i = 0; i < blocks.length; i++) {
for (int j = 0; j < blocks[i].size(); j++) {
if ((Integer) blocks[i].get(j) == a) {
return new Point(i, j);
}
}
}
return null;
}
}
```

# UVA 12356 – Army Buddies

So this question is interesting. I was updating too much and was getting TLE. Once a buddy dies, there are obviously no more requests containing army members who are no more. We can therefore safely update only the end points of every given query.

```import java.io.BufferedReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.StringTokenizer;

/**
*
* @author Sanchit M. Bhatnagar
* @see http://uhunt.felix-halim.net/id/74004
*
*/
public class P12356 {

public static void main(String[] args) throws NumberFormatException, IOException {
PrintWriter out = new PrintWriter(System.out);
StringTokenizer st = null;

String line = null;
while ((line = br.readLine()) != null) {
st = new StringTokenizer(line);
int S = Integer.parseInt(st.nextToken());
int B = Integer.parseInt(st.nextToken());
if (S == 0 && B == 0)
break;
int[] leftBuddy = new int[S + 2];
int[] rightBuddy = new int[S + 2];
for (int i = 1; i <= S; i++) {
leftBuddy[i] = i - 1;
rightBuddy[i] = i + 1;
}
rightBuddy[S] = 0;
for (int i = 0; i < B; i++) {
int l = Integer.parseInt(st.nextToken());
int r = Integer.parseInt(st.nextToken());
if (leftBuddy[l] == 0)
out.print("* ");
else
out.print(leftBuddy[l] + " ");
if (rightBuddy[r] == 0)
out.println("*");
else
out.println(rightBuddy[r]);
leftBuddy[rightBuddy[r]] = leftBuddy[l];
rightBuddy[leftBuddy[l]] = rightBuddy[r];
}
out.println("-");
}
out.close();
br.close();
}
}
```

# UVA 10050 – Hartals

Simultaed all the holidays and then removed them from the list of total days.

```import java.io.BufferedReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.HashSet;

/**
*
* @author Sanchit M. Bhatnagar
* @see http://uhunt.felix-halim.net/id/74004
*
*/
public class P10050 {
public static void main(String[] args) throws NumberFormatException, IOException {
PrintWriter out = new PrintWriter(System.out);

for (int testCase = 1; testCase <= numTestCases; testCase++) {
HashSet<Integer> ans = new HashSet<Integer>();
for (int i = 0; i < P; i++) {
int max = N / tmp;
for (int j = 1; j <= max; j++) {
}
}
int max = N / 7 + 1;
for (int j = 1; j <= max; j++) {
int tmp = 7 * j;
if (ans.contains(tmp))
ans.remove(tmp);
if (ans.contains(tmp - 1))
ans.remove(tmp - 1);
}
out.println(ans.size());
}
out.close();
}
}
```

# UVA 10038 – Jolly Jumpers

Easy problem. Take all differences, put them in a HashSet and then check if all the requred numbers are in the HashSet or not.

```import java.io.BufferedReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.HashSet;
import java.util.StringTokenizer;

/**
*
* @author Sanchit M. Bhatnagar
* @see http://uhunt.felix-halim.net/id/74004
*
*/
public class P10038 {
public static void main(String[] args) throws NumberFormatException, IOException {
PrintWriter out = new PrintWriter(System.out);
StringTokenizer st;

String line = null;
while ((line = br.readLine()) != null) {
st = new StringTokenizer(line.trim());
int N = Integer.parseInt(st.nextToken());
if (N == 1) {
out.println("Jolly");
} else {
HashSet<Integer> ans = new HashSet<Integer>();
int last = 0;
for (int i = 0; i < N; i++) {
if (i == 0) {
last = Integer.parseInt(st.nextToken());
} else {
int tmp = Integer.parseInt(st.nextToken());
last = tmp;
}
}

if (ans.size() != N - 1) {
out.println("Not jolly");
} else {
boolean found = true;
for (int i = 1; i < N; i++) {
if (!ans.contains(i)) {
found = false;
break;
}
}
if (found) {
out.println("Jolly");
} else {
out.println("Not jolly");
}
}
}
}
out.close();
br.close();
}
}
```

# UVA 11340 – Newspaper

Super easy problem if you’re used to a bit of C++ and familiar to the printf method.

```import java.io.BufferedReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.HashMap;
import java.util.StringTokenizer;

/**
*
* @author Sanchit M. Bhatnagar
* @see http://uhunt.felix-halim.net/id/74004
*
*/
public class P11340 {

public static void main(String[] args) throws NumberFormatException, IOException {
PrintWriter out = new PrintWriter(System.out);

for (int zz = 0; zz < N; zz++) {
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
StringTokenizer st = null;
for (int yy = 0; yy < K; yy++) {
map.put(st.nextToken().charAt(0), Integer.parseInt(st.nextToken()));
}
double ans = 0;
for (int xx = 0; xx < M; xx++) {
for (Character c : line) {
if (map.containsKey(c)) {
ans += map.get(c);
}
}
}
ans /= 100;
out.printf("%.2f\$" + System.lineSeparator(), ans);
}

out.close();
sc.close();
}
}
```

# UVA 11459 – Snakes and Ladders

Simple simulation game. Don’t forget to read through the entire input if the game ends early! That cost me a couple of tries :[

```import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;

/**
*
* @author Sanchit M. Bhatnagar
* @see http://uhunt.felix-halim.net/id/74004
*
*/
public class P11459 {

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
PrintWriter out = new PrintWriter(System.out);

int cases = sc.nextInt();
while (cases > 0) {
int players = sc.nextInt();
int cheats = sc.nextInt();
int rolls = sc.nextInt();

int[] map = new int[101];
for (int i = 0; i < cheats; i++) {
map[sc.nextInt()] = sc.nextInt();
}

int playerIdx = 0;
int[] pos = new int[players];
Arrays.fill(pos, 1);
for (int i = 0; i < rolls; i++) {
pos[playerIdx] += sc.nextInt();
if (map[pos[playerIdx]] != 0)
pos[playerIdx] = map[pos[playerIdx]];
if (pos[playerIdx] >= 100) {
pos[playerIdx] = 100;
while (i + 1 < rolls) {
sc.nextInt();
i++;
}
break;
}
playerIdx++;
if (playerIdx == players)
playerIdx = 0;
}
for (int i = 0; i < players; i++) {
out.println("Position of player " + (i + 1) + " is " + pos[i] + ".");
}
cases--;
}

out.close();
sc.close();
}
}
```

# UVA 10189 – Minesweeper

This is a problem that I solved earlier for the Programming Challenges book. Pretty simple problem.

```import java.util.Scanner;

/**
*
* @author Sanchit M. Bhatnagar
* @see http://uhunt.felix-halim.net/id/74004
*
*/
public class P10189 {

private static int[] arr = { -1, 0, 1 };

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int count = 1;
while (sc.hasNextInt()) {
int y = sc.nextInt();
int x = sc.nextInt();
if (x == 0 && y == 0)
break;
if (count != 1)
System.out.println();
char[][] field = new char[y + 2][x + 2];
for (int i = 0; i < y; i++) {
String t = sc.next();
for (int j = 0; j < x; j++)
field[i + 1][j + 1] = t.charAt(j);
}

for (int i = 0; i < y; i++) {
for (int j = 0; j < x; j++) {
int mines = 0;
if (field[i + 1][j + 1] == '*')
continue;
if (field[i + 1][j + 1] == '.') {
for (int zz = 0; zz < arr.length; zz++)
for (int yy = 0; yy < arr.length; yy++)
if (zz == 1 && yy == 1)
continue;
else if (field[i + 1 + arr[zz]][j + 1 + arr[yy]] == '*')
mines++;

String zxc = "" + mines;
field[i + 1][j + 1] = (zxc.charAt(0));
}

}
}

System.out.println("Field #" + count + ":");
for (int i = 0; i < y; i++) {
for (int j = 0; j < x; j++) {
if (j != x - 1)
System.out.print(field[i + 1][j + 1]);
else
System.out.println(field[i + 1][j + 1]);
}
}
count++;
}
sc.close();
}
}
```

# UVA 489 – Hangman Judge

Pretty easy problem. The word to guess can be safely put into a HashSet and we can keep guessing until the set is empty or until we are done with (7) guesses that are allowed. One thing to note is that the order of the input matters but duplicates in the input do not matter. Therefore, I use an ArrayList as well as a HashSet to store the input and get AC.

```import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Scanner;

/**
*
* @author Sanchit M. Bhatnagar
* @see http://uhunt.felix-halim.net/id/74004
*
*/
public class P489 {

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
PrintWriter out = new PrintWriter(System.out);

while (sc.hasNextInt()) {
int N = sc.nextInt();
if (N == -1)
break;

char[] word = sc.next().toCharArray();
HashSet<Character> hax = new HashSet<Character>();
for (Character c : word) {
}

// Order Matters
char[] guesses = sc.next().toCharArray();
ArrayList<Character> hax3 = new ArrayList<Character>();
HashSet<Character> hax2 = new HashSet<Character>();
for (Character c : guesses) {
if (!hax2.contains(c)) {
}
}

int movesLeft = 7;
for (Character c : hax3) {
if (hax.contains(c)) {
hax.remove(c);
} else {
movesLeft--;
}
if (hax.size() == 0 || movesLeft == 0)
break;
}

out.println("Round " + N);
if (movesLeft < 1) {
out.println("You lose.");
} else if (hax.size() == 0) {
out.println("You win.");
} else {
out.println("You chickened out.");
}
}

out.close();
sc.close();
}
}
```

# UVA 10284 – Chessboard in FEN

This is an easy problem as long as you have done UVA 10196 – Check The Check. I added another “deathByKing” method and just basically used 99% of the old code to solve this problem. The time limit is 3 seconds so a lazy O(N^2) works great.

```import java.awt.Point;
import java.io.PrintWriter;
import java.util.Scanner;
import java.util.StringTokenizer;

/**
*
* @author Sanchit M. Bhatnagar
* @see http://uhunt.felix-halim.net/id/74004
*
*/
public class P10284 {

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
PrintWriter out = new PrintWriter(System.out);
while (sc.hasNext()) {
char[][] grid = new char[8][8];
StringTokenizer st = new StringTokenizer(sc.next(), "/");
for (int i = 0; i < 8; i++) {
char[] row = st.nextToken().trim().toCharArray();
int idx = 0;
for (Character c : row) {
if (Character.isDigit(c)) {
int tmp = c - '0';
for (int j = idx; j < idx + tmp; j++) {
grid[i][j] = '.';
}
idx += tmp;
} else {
grid[i][idx] = c;
idx++;
}
}
}
int ans = 0;
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
if (grid[i][j] == '.') {
Point tmp = new Point(i, j);
if (!deathByKing(tmp, grid)) {
int count = 0;
grid[i][j] = 'X';
if (!deathByBishop(tmp, grid) && !deathByKnight(tmp, grid) && !deathByPawn(tmp, grid) && !deathByRook(tmp, grid)) {
count++;
}
grid[i][j] = 'x';
if (!deathByBishop(tmp, grid) && !deathByKnight(tmp, grid) && !deathByPawn(tmp, grid) && !deathByRook(tmp, grid)) {
count++;
}
grid[i][j] = '.';
if (count == 2)
ans++;
}
}
}
}
out.println(ans);
}
out.close();
sc.close();
}

private static boolean deathByKing(Point king, char[][] grid) {
int i = king.x;
int j = king.y;
for (int n = i - 1; n <= i + 1; n++)
for (int m = j - 1; m <= j + 1; m++) {
if (n >= 0 && n < 8 && m >= 0 && m < 8 && (grid[n][m] == 'k' || grid[n][m] == 'K'))
return true;
}
return false;
}

private static boolean deathByBishop(Point king, char[][] grid) {
int i = king.x;
int j = king.y;
char thing = '\u000F';
char thing2 = '\u000F';
if (Character.isLowerCase(grid[i][j])) {
// Black King
thing = 'B';
thing2 = 'Q';
} else {
// White King
thing = 'b';
thing2 = 'q';
}

// NW
int idx = i - 1;
int idx2 = j - 1;
while (idx >= 0 && idx < 8 && idx2 >= 0 && idx2 < 8 && grid[idx][idx2] == '.') {
idx--;
idx2--;
}
if (idx >= 0 && idx < 8 && idx2 >= 0 && idx2 < 8 && (grid[idx][idx2] == thing || grid[idx][idx2] == thing2))
return true;

// NE
idx = i - 1;
idx2 = j + 1;
while (idx >= 0 && idx < 8 && idx2 >= 0 && idx2 < 8 && grid[idx][idx2] == '.') {
idx--;
idx2++;
}
if (idx >= 0 && idx < 8 && idx2 >= 0 && idx2 < 8 && (grid[idx][idx2] == thing || grid[idx][idx2] == thing2))
return true;

// SW
idx = i + 1;
idx2 = j - 1;
while (idx >= 0 && idx < 8 && idx2 >= 0 && idx2 < 8 && grid[idx][idx2] == '.') {
idx++;
idx2--;
}
if (idx >= 0 && idx < 8 && idx2 >= 0 && idx2 < 8 && (grid[idx][idx2] == thing || grid[idx][idx2] == thing2))
return true;

// RIGHT
idx = i + 1;
idx2 = j + 1;
while (idx >= 0 && idx < 8 && idx2 >= 0 && idx2 < 8 && grid[idx][idx2] == '.') {
idx++;
idx2++;
}
if (idx >= 0 && idx < 8 && idx2 >= 0 && idx2 < 8 && (grid[idx][idx2] == thing || grid[idx][idx2] == thing2))
return true;

return false;
}

private static boolean deathByRook(Point king, char[][] grid) {
int i = king.x;
int j = king.y;
char thing = '\u000F';
char thing2 = '\u000F';
if (Character.isLowerCase(grid[i][j])) {
// Black King
thing = 'R';
thing2 = 'Q';
} else {
// White King
thing = 'r';
thing2 = 'q';
}

// UP
int idx = i - 1;
while (idx >= 0 && grid[idx][j] == '.') {
idx--;
}
if (idx >= 0 && idx < 8 && (grid[idx][j] == thing || grid[idx][j] == thing2))
return true;

// DOWN
idx = i + 1;
while (idx < 8 && grid[idx][j] == '.') {
idx++;
}
if (idx >= 0 && idx < 8 && (grid[idx][j] == thing || grid[idx][j] == thing2))
return true;

// LEFT
idx = j - 1;
while (idx >= 0 && grid[i][idx] == '.') {
idx--;
}
if (idx >= 0 && idx < 8 && (grid[i][idx] == thing || grid[i][idx] == thing2))
return true;

// RIGHT
idx = j + 1;
while (idx < 8 && grid[i][idx] == '.') {
idx++;
}
if (idx >= 0 && idx < 8 && (grid[i][idx] == thing || grid[i][idx] == thing2))
return true;

return false;
}

private static boolean deathByKnight(Point king, char[][] grid) {
int i = king.x;
int j = king.y;
char thing = '\u000F';
if (Character.isLowerCase(grid[i][j])) {
// Black King
thing = 'N';
} else {
// White King
thing = 'n';
}
if (i + 2 < 8) {
if (j - 1 >= 0 && grid[i + 2][j - 1] == thing)
return true;
if (j + 1 < 8 && grid[i + 2][j + 1] == thing)
return true;
}
if (i - 2 >= 0) {
if (j - 1 >= 0 && grid[i - 2][j - 1] == thing)
return true;
if (j + 1 < 8 && grid[i - 2][j + 1] == thing)
return true;
}
if (j + 2 < 8) {
if (i - 1 >= 0 && grid[i - 1][j + 2] == thing)
return true;
if (i + 1 < 8 && grid[i + 1][j + 2] == thing)
return true;
}
if (j - 2 >= 0) {
if (i - 1 >= 0 && grid[i - 1][j - 2] == thing)
return true;
if (i + 1 < 8 && grid[i + 1][j - 2] == thing)
return true;
}

return false;
}

private static boolean deathByPawn(Point king, char[][] grid) {
int i = king.x;
int j = king.y;
char thing = '\u000F';
if (Character.isLowerCase(grid[i][j])) {
// Black King
i++;
thing = 'P';
} else {
// White King
i--;
thing = 'p';
}
if (i >= 0 && i < 8) {
if (j - 1 >= 0 && grid[i][j - 1] == thing)
return true;
if (j + 1 < 8 && grid[i][j + 1] == thing)
return true;
}
return false;
}
}
```