USACO:msquare.

Problem:

Magic Squares
IOI'96
Following the success of the magic cube, Mr. Rubik invented its planar version, called magic squares. This is a sheet composed of 8 equal-sized squares:
 1 2 3 4 8 7 6 5
In this task we consider the version where each square has a different color. Colors are denoted by the first 8 positive integers. A sheet configuration is given by the sequence of colors obtained by reading the colors of the squares starting at the upper left corner and going in clockwise direction. For instance, the configuration of Figure 3 is given by the sequence (1,2,3,4,5,6,7,8). This configuration is the initial configuration.
Three basic transformations, identified by the letters `A', `B' and `C', can be applied to a sheet:
• 'A': exchange the top and bottom row,
• 'B': single right circular shifting of the rectangle,
• 'C': single clockwise rotation of the middle four squares.
Below is a demonstration of applying the transformations to the initial squares given above:
A:
 8 7 6 5 1 2 3 4
B:
 4 1 2 3 5 8 7 6
C:
 1 7 2 4 8 6 3 5
All possible configurations are available using the three basic transformations.
You are to write a program that computes a minimal sequence of basic transformations that transforms the initial configuration above to a specific target configuration.

INPUT FORMAT

A single line with eight space-separated integers (a permutation of (1..8)) that are the target configuration.

2 6 8 4 5 7 3 1

OUTPUT FORMAT

 Line 1: A single integer that is the length of the shortest transformation sequence. Line 2: The lexically earliest string of transformations expressed as a string of characters, 60 per line except possibly the last line.

7
BCABCCB

Solution:

This is a shortest path problem. Use BFS + Hash Table to go through every state.
The only problem here is if I use array to store and identify the state, that would exceed time limit. Since we only have 8 digits, we could represent it as an INT.

I think this problem could be solved with DFS using recursion and hash table.

Source Code:

/*
ID: ***
PROB: msquare
LANG: JAVA
*/
import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.PrintWriter;
import java.util.HashSet;
import java.util.Queue;

public class msquare {

public static void main(String[] args) throws Exception {
msquare main = new msquare();
main.run();
System.exit(0);
}

private void run() throws Exception {
PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter(
"msquare.out")));
String[] strs = in.readLine().split("\\s");
in.close();
// int[] src = { 1, 2, 3, 4, 5, 6, 7, 8 };
int src = 12345678;
int dst = 0;
for (int i = 0; i < 8; i++)
dst = dst * 10 + Integer.parseInt(strs[i]);

Queue<State> queue = new LinkedList<State>();
HashSet<Integer> set = new HashSet<Integer>();
State state = new State(src, "");

// System.out.println(state.transformA().number);
// System.out.println(state.transformC().number);
while (queue.isEmpty() == false) {
state = queue.poll();
if (state.number == dst) {
String tmp = state.ops;
out.write(String.format("%d\n%s\n", tmp.length(), tmp));
out.close();
return;
}
State stateA = null;

stateA = state.transformA();
if (set.contains(stateA.number) == false) {
}

stateA = state.transformB();
if (set.contains(stateA.number) == false) {
}

stateA = state.transformC();
if (set.contains(stateA.number) == false) {
}
}
out.close();
}
}

class State implements Comparable<State> {
public int number;
public String ops;

public State(int a, String prev) {
this.number = a;
this.ops = prev;
}

public State transformA() {
int ret = 0;
int cp = number;
for (; cp > 0;) {
int a = cp % 10;
cp /= 10;
ret = ret * 10 + a;
}

String prev = this.ops + "A";
State A = new State(ret, prev);
return A;
}

public State transformB() {
int n = (number / 100000 * 10000)
+ (((number / 10000) % 10) * 10000000) + ((number % 1000) * 10)
+ ((number / 1000) % 10);
String prev = this.ops + "B";
State B = new State(n, prev);
return B;
}

public State transformC() {
int result = 0;
result = number - number % 10000000;
result += (number % 100 - number % 10) * 100000;
result += (number % 10000000 - number % 1000000) / 10;
result += number % 100000 - number % 1000;
result += (number % 1000000 - number % 100000) / 1000;
result += (number % 1000 - number % 100) / 10;
result += number % 10;
String prev = this.ops + "C";
State C = new State(result, prev);
return C;
}

@Override
public int compareTo(State o) {
return this.number - o.number;
}

@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
State other = (State) obj;
if (this.number == other.number)
return true;
return false;
}

}

Thursday, February 21, 2013

USACO: Factorials

USACO:Factorials,

Problem:

Factorials
The factorial of an integer N, written N!, is the product of all the integers from 1 through N inclusive. The factorial quickly becomes very large: 13! is too large to store in a 32-bit integer on most computers, and 70! is too large for most floating-point variables. Your task is to find the rightmost non-zero digit of n!. For example, 5! = 1 * 2 * 3 * 4 * 5 = 120, so the rightmost non-zero digit of 5! is 2. Likewise, 7! = 1 * 2 * 3 * 4 * 5 * 6 * 7 = 5040, so the rightmost non-zero digit of 7! is 4.

INPUT FORMAT

A single positive integer N no larger than 4,220.

7

OUTPUT FORMAT

A single line containing but a single digit: the right most non-zero digit of N! .

4

Solution:

They only factor could result rear zeros is the product of 2 and 5,(10 could be handled as 2 * 5).
So we count the number of 2s and 5s, obviously 2s are much more than 5s as you can see.

We keep multiply numbers, resulted by removing 2s and 5s, while counting the number of 2s and 5s.
At last, get the final result with 2s and 5s. Check out the code for details.

Source Code:

/*
ID: ***
LANG: JAVA
*/
import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.PrintWriter;

public class fact4 {

public static void main(String[] args) throws Exception {
fact4 main = new fact4();
main.run();
System.exit(0);
}

private void run() throws Exception {
PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter(
"fact4.out")));

int N = Integer.parseInt(br.readLine());
br.close();
int cnt2 = 0;
int cnt5 = 0;
int prod = 1;
for (int i = 1; i <= N; i++) {
int tmp = i;
while (tmp % 2 == 0) {
tmp /= 2;
cnt2++;
}
while (tmp % 5 == 0) {
tmp /= 5;
cnt5++;
}
prod = (prod * tmp) % 10;
}

if (cnt2 == cnt5)
out.write(Integer.toString(prod));
else if (cnt2 > cnt5) {
for (int i = 0; i < cnt2 - cnt5; i++)
prod = (prod * 2) % 10;
out.write(Integer.toString(prod));
} else {
for (int i = 0; i < cnt5 - cnt2; i++)
prod = (prod * 5) % 10;
out.write(Integer.toString(prod));
}
out.write("\n");

out.close();
}
}

USACO: kimbits

Problem:

Stringsobits
Kim Schrijvers
Consider an ordered set S of strings of N (1 <= N <= 31) bits. Bits, of course, are either 0 or 1.
This set of strings is interesting because it is ordered and contains all possible strings of length N that have L (1 <= L <= N) or fewer bits that are `1'.
Your task is to read a number I (1 <= I <= sizeof(S)) from the input and print the Ith element of the ordered set for N bits with no more than L bits that are `1'.

INPUT FORMAT

A single line with three space separated integers: N, L, and I.

5 3 19

OUTPUT FORMAT

A single line containing the integer that represents the Ith element from the order set, as described.

10011

Solution:

First, I tried to solve this problem recursively, while data set #7 always make my code exceed time limit(ETL),

Source Code:

Code Got Passed.
/*
ID: ***
LANG: JAVA
*/
import java.io.FileWriter;
import java.io.PrintWriter;

/**
* @author antonio081014
* @time Feb 21, 2013, 7:37:09 PM
*/
public class kimbits {

private int N;
private int L;
private long I;
private long[][] mark;
private PrintWriter out;

public static void main(String[] args) throws Exception {
kimbits main = new kimbits();
main.run();
System.exit(0);
}

private void run() throws Exception {
out = new PrintWriter(new FileWriter("kimbits.out"));

String[] strs = br.readLine().split("\\s");
N = Integer.parseInt(strs);
L = Integer.parseInt(strs);
I = Long.parseLong(strs);
br.close();

mark = new long[N + 1][L + 1];
for (int i = 0; i <= N; i++)
mark[i] = 1L;
for (int i = 0; i <= L; i++) {
mark[i] = 1L;
}

for (int i = 1; i <= N; i++) {
for (int j = 1; j <= L; j++)
if (i >= j)
mark[i][j] = mark[i - 1][j - 1] + mark[i - 1][j];
else
mark[i][j] = mark[i][i];
}
// print(N, L, I);
printbit(N, L, I);
out.write('\n');
out.close();
}

private void print(int n, int l, int i) {
if (l > n)
l = n;
if (mark[n][l] == i) {
for (int j = 0; j < i; j++)
out.write('1');
for (int j = i; j < n; j++)
out.write('0');
} else {
if (i > mark[n - 1][l]) {
out.write('1');
print(n - 1, l - 1, (int) ((long) i - mark[n - 1][l]));
} else {
out.write('0');
}
}
}

void printbit(int i, int j, long K) {
if (j > i)
j = i;

if (K == mark[i][j]) {
for (int t = 1; t <= j; t++)
out.write('1');
for (int t = 1; t <= i - j; t++)
out.write('0');
} else {

if (K <= mark[i - 1][j]) {
out.write('0');
printbit(i - 1, j, K);
} else {
out.write('1');
printbit(i - 1, j - 1, K - mark[i - 1][j]);
}
}
}
}

/*
ID: ***
LANG: JAVA
*/
import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.PrintWriter;

public class kimbits {

private int L;
private int N;
private int I;
private String[] list;
private PrintWriter out;
private boolean flag;
private int top;

public static void main(String[] args) throws Exception {
kimbits main = new kimbits();
main.run();
System.exit(0);
}

private void run() throws Exception {
out = new PrintWriter(new BufferedWriter(new FileWriter("kimbits.out")));
String[] strs = br.readLine().split("\\s");
br.close();
flag = true;
N = Integer.parseInt(strs);
L = Integer.parseInt(strs);
I = Integer.parseInt(strs);
// System.out.println(String.format("N %d, L %d, I %d", N, L, I));
list = new String[I];
top = 0;
rec("", 0);
out.close();
}

private void rec(String s, int ones) {
if (s.length() == N) {
if (ones <= L && flag)
list[top++] = s;
if (top == I && flag) {
out.write(s + "\n");
flag = false;
}
return;
}
if (flag == false)
return;
rec(s + "0", ones);
rec(s + "1", ones + 1);
}
}

UVa10684,

Background

As Manuel wants to get rich fast and without too much work, he decided to make a career in gambling. Initially, he plans to study the gains and losses of players, so that, he can identify patterns of consecutive wins and elaborate a win-win strategy. But Manuel, as smart as he thinks he is, does not know how to program computers. So he hired you to write programs that will assist him in elaborating his strategy.

The Problem

Your first task is to write a program that identifies the maximum possible gain out of a sequence of bets. A bet is an amount of money and is either winning (and this is recorded as a positive value), or losing (and this is recorded as a negative value).

Input

The input set consists of a positive number N ≤ 10000 , that gives the length of the sequence, followed by N integers. Each bet is an integer greater than 0 and less than 1000.
The input is terminated with N = 0.

Output

For each given input set, the output will echo a line with the corresponding solution. If the sequence shows no possibility to win money, then the output is the message "Losing streak."

5
12 -4
-10 4
9
3
-2 -1 -2
0

Sample output

The maximum winning streak is 13.
Losing streak.

Solution:

Dynamic Programming.

Source Code:

import java.util.Scanner;

/**
*
*/

/**
* @author antonio081014
* @time Feb 10, 2013, 2:43:55 PM <br>
*
*       Problem: 10684 - The jackpot
*/
public class Main {

/**
* @param args
*/
public static void main(String[] args) {
Main main = new Main();
main.run();
System.exit(0);
}

private void run() {
Scanner sc = new Scanner(System.in);
int N;
while ((N = sc.nextInt()) != 0) {
int sum = 0;
int max = 0;
while (N-- > 0) {
sum += sc.nextInt();
if (sum < 0) {
sum = 0;
}
max = Math.max(sum, max);
}
if (max <= 0) {
System.out.println("Losing streak.");
} else {
System.out.println(String.format(
"The maximum winning streak is %d.", max));
}
}
}

}