EvbCFfp1XB

problem and my answer.

September 2012

problem 1035:   Sleeping Cats

how to solve It's easy to solve, isn't it?

source code

import java.util.Scanner;

public class SleepingCats {
private static final int CAN_SLEEP = -1;

public static void main(String[] args) {
boolean test = !true;
if (test) {
testA();
testB();
} else {
run();
}
}

private static void testA() {
long start = System.nanoTime();
String s = run("4 6\n" + "s 0 2\n" + "s 1 3\n" + "s 2 1\n" + "w 0\n"
+ "s 3 3\n" + "s 4 2\n");
System.out.format("(%s)", ("0\n" + "impossible\n" + "2\n"
+ "impossible\n" + "0\n" + "END").equals(s) ? "A" : s);
System.out.format("[%.2f]\n", (System.nanoTime() - start) / 1e9);
}

private static void testB() {
long start = System.nanoTime();
String s = run("3 3\n" + "s 0 1\n" + "s 1 1\n" + "s 2 1\n");
System.out.format("(%s)",
("0\n" + "1\n" + "2\n" + "END").equals(s) ? "B" : s);
System.out.format("[%.2f]\n", (System.nanoTime() - start) / 1e9);
}

private static String run(String s) {
Scanner sc = new Scanner(s);
int width = sc.nextInt();
int n = sc.nextInt();
Data[] diary = new Data[n];
for (int i = 0; i < diary.length; i++) {
diary[i] = new Data();
diary[i].isSleep = "s".equals(sc.next());
diary[i].id = sc.nextInt();
if (diary[i].isSleep) {
diary[i].width = sc.nextInt();
}
}
String solve = solve(width, diary);
return solve;
}

private static void run() {
Scanner sc = new Scanner(System.in);
for (; sc.hasNext();) {
int width = sc.nextInt();
int n = sc.nextInt();
if (width == 0 && n == 0) {
break;
}
Data[] diary = new Data[n];
for (int i = 0; i < diary.length; i++) {
diary[i] = new Data();
diary[i].isSleep = "s".equals(sc.next().trim());
diary[i].id = sc.nextInt();
if (diary[i].isSleep) {
diary[i].width = sc.nextInt();
}
}
String solve = solve(width, diary);
System.out.print(solve + "\n");
}
}

private static String solve(int width, Data[] diary) {
int[] fence = new int[width];
for (int i = 0; i < fence.length; i++) {
fence[i] = CAN_SLEEP;
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < diary.length; i++) {
if (diary[i].isSleep) {
sb.append(canSleep(fence, diary[i]) + "\n");
} else {
wakeup(fence, diary[i]);
}
}
sb.append("END");
return sb.toString();
}

private static void wakeup(int[] fence, Data data) {
for (int i = 0; i < fence.length; i++) {
if (fence[i] == data.id) {
fence[i] = CAN_SLEEP;
}
}
}

private static String canSleep(int[] fence, Data diary) {
int canSleepi = CAN_SLEEP;
A: for (int fi = 0; fi < fence.length; fi++) {
if (fi + diary.width - 1 < fence.length) {
} else {
break;
}
for (int fi2 = diary.width - 1; fi2 >= 0; fi2--) {
if (fence[fi + fi2] == CAN_SLEEP) {
} else {
fi = fi + fi2;
continue A;
}
}
canSleepi = fi;
break;
}
if (canSleepi != CAN_SLEEP) {
for (int fi2 = diary.width - 1; fi2 >= 0; fi2--) {
fence[canSleepi + fi2] = diary.id;
}
return "" + canSleepi;
} else {
return "impossible";
}
}

private static class Data {
public int width;
public int id;
public boolean isSleep;
}
}

problem 1029:   Traffic Analysis

how to solve This problem is easy, right?

source code

import java.util.Scanner;

public class TrafficAnalysis {
public static void main(String[] args) {
boolean test = !true;
if (test) {
testA();
testB();
testC();
testD();
} else {
run();
}
}

private static void testA() {
long start = System.nanoTime();
String s = run("4 5\n" + "20 35 60 70\n" + "15 30 40 80 90\n");
System.out.format("(%s)", ("20").equals(s) ? "A" : s);
System.out.format("[%.2f]\n", (System.nanoTime() - start) / 1e9);
}

private static void testB() {
long start = System.nanoTime();
String s = run("3 2\n" + "10 20 30\n" + "42 60\n");
System.out.format("(%s)", ("18").equals(s) ? "B" : s);
System.out.format("[%.2f]\n", (System.nanoTime() - start) / 1e9);
}

private static void testC() {
long start = System.nanoTime();
String s = run("0 1\n" + "100\n");
System.out.format("(%s)", ("100").equals(s) ? "C" : s);
System.out.format("[%.2f]\n", (System.nanoTime() - start) / 1e9);
}

private static void testD() {
long start = System.nanoTime();
String s = run("1 1\n" + "10\n" + "50\n");
System.out.format("(%s)", ("40").equals(s) ? "D" : s);
System.out.format("[%.2f]\n", (System.nanoTime() - start) / 1e9);
}

private static String run(String s) {
Scanner sc = new Scanner(s);
int n = sc.nextInt();
int m = sc.nextInt();
int[] time0 = new int[n];
for (int i = 0; i < time0.length; i++) {
time0[i] = sc.nextInt();
}
int[] time1 = new int[m];
for (int i = 0; i < time1.length; i++) {
time1[i] = sc.nextInt();
}
String solve = solve(time0, time1);
return solve;
}

private static void run() {
Scanner sc = new Scanner(System.in);
for (; sc.hasNext();) {
int n = sc.nextInt();
int m = sc.nextInt();
if (n == 0 && m == 0) {
break;
}
int[] time0 = new int[n];
for (int i = 0; i < time0.length; i++) {
time0[i] = sc.nextInt();
}
int[] time1 = new int[m];
for (int i = 0; i < time1.length; i++) {
time1[i] = sc.nextInt();
}
String solve = solve(time0, time1);
System.out.print(solve + "\n");
}
}

private static String solve(int[] time0, int[] time1) {
int[] time = new int[time0.length + time1.length];
mergeAB(time, 0, time.length - 1, time0, 0, time0.length - 1, time1, 0,
time1.length - 1);
int max = time[0];
for (int i = 1; i < time.length; i++) {
max = Math.max(max, time[i] - time[i - 1]);
}
return "" + max;
}

private static void mergeAB(int[] c, int cl, int cr, int[] a, int al,
int ar, int[] b, int bl, int br) {
for (int ai = al, bi = bl, ci = cl; ci <= cr; ci++) {
if (ai > ar) {
c[ci] = b[bi++];
} else if (bi > br) {
c[ci] = a[ai++];
} else {
c[ci] = a[ai] <= b[bi] ? a[ai++] : b[bi++];
}
}
}
}

problem 1027:   A Piece of Cake

how to solve It's easy to solve.

source code

import java.util.Scanner;

public class APieceofCake {
public static void main(String[] args) {
boolean test = !true;
if (test) {
testA();
testB();
} else {
run();
}
}

private static void testA() {
long start = System.nanoTime();
String s = run("2\n" + "2\n");
System.out.format("(%s)", ("2").equals(s) ? "A" : s);
System.out.format("[%.2f]\n", (System.nanoTime() - start) / 1e9);
}

private static void testB() {
long start = System.nanoTime();
String s = run("3\n" + "5 4 3\n");
System.out.format("(%s)", ("6").equals(s) ? "B" : s);
System.out.format("[%.2f]\n", (System.nanoTime() - start) / 1e9);
}

private static String run(String s) {
Scanner sc = new Scanner(s);
int n = sc.nextInt();
int[] cake = new int[n * (n - 1) / 2];
for (int i = 0; i < cake.length; i++) {
cake[i] = sc.nextInt();
}
String solve = solve(n, cake);
return solve;
}

private static void run() {
Scanner sc = new Scanner(System.in);
for (;;) {
int n = sc.nextInt();
if (n == 0) {
break;
}
int[] cake = new int[n * (n - 1) / 2];
for (int i = 0; i < cake.length; i++) {
cake[i] = sc.nextInt();
}
String solve = solve(n, cake);
System.out.print(solve + "\n");
}
}

private static String solve(int n, int[] cake) {
int sum = 0;
for (int i = 0; i < cake.length; i++) {
sum += cake[i];
}
return "" + (sum / (n - 1));
}
}

problem 1020:   Cleaning Robot

how to solve It's easy to solve.

source code

import java.util.Scanner;

public class CleaningRobot {
public static void main(String[] args) {
boolean test = !true;
if (test) {
testA();
testB();
testC();
} else {
run();
}
}

private static void testA() {
long start = System.nanoTime();
String s = run("1\n" + "E A C\n");
System.out.format(
"(%s)",
Math.abs(Double.parseDouble("0.00000000")
- Double.parseDouble(s)) <= 0.000001 ? "A" : s);
System.out.format("[%.2f]\n", (System.nanoTime() - start) / 1e9);
}

private static void testB() {
long start = System.nanoTime();
String s = run("1\n" + "E B C\n");
System.out.format(
"(%s)",
Math.abs(Double.parseDouble("0.25000000")
- Double.parseDouble(s)) <= 0.000001 ? "B" : s);
System.out.format("[%.2f]\n", (System.nanoTime() - start) / 1e9);
}

private static void testC() {
long start = System.nanoTime();
String s = run("2\n" + "E A B\n");
System.out.format(
"(%s)",
Math.abs(Double.parseDouble("0.06250000")
- Double.parseDouble(s)) <= 0.000001 ? "C" : s);
System.out.format("[%.2f]\n", (System.nanoTime() - start) / 1e9);
}

private static String run(String s) {
Scanner sc = new Scanner(s);
int battery = sc.nextInt();
String start = sc.next();
String goal = sc.next();
String close = sc.next();
String solve = solve(battery, start, goal, close);
return solve;
}

private static void run() {
Scanner sc = new Scanner(System.in);
for (;;) {
int battery = sc.nextInt();
if (battery == 0) {
break;
}
String start = sc.next();
String goal = sc.next();
String close = sc.next();
String solve = solve(battery, start, goal, close);
System.out.print(solve + "\n");
}
}

private static String[][] room = new String[][] { { "A", "B", "C", },
{ "D", "E", "F", }, { "G", "H", "I", }, };

private static String solve(int battery, String start, String goal,
String close) {
int si = 0;
int sj = 0;
int gi = 0;
int gj = 0;
int ci = 0;
int cj = 0;
for (int i = 0; i < room.length; i++) {
for (int j = 0; j < room[i].length; j++) {
if (room[i][j].equals(start)) {
si = i;
sj = j;
}
if (room[i][j].equals(goal)) {
gi = i;
gj = j;
}
if (room[i][j].equals(close)) {
ci = i;
cj = j;
}
}
}
double[][] probability = new double[3][3];
double[][] probability2 = new double[3][3];
probability[si][sj] = 1d;
for (int i = battery; i > 0; i--) {
for (int pi = 0; pi < probability.length; pi++) {
for (int pj = 0; pj < probability[pi].length; pj++) {
double d = probability[pi][pj] / 4d;
probability[pi][pj] = 0d;
if (pi - 1 >= 0 && (pi - 1 != ci || pj != cj)) {
probability2[pi - 1][pj] += d;
} else {
probability2[pi][pj] += d;
}
if (pj - 1 >= 0 && (pi != ci || pj - 1 != cj)) {
probability2[pi][pj - 1] += d;
} else {
probability2[pi][pj] += d;
}
if (pi + 1 < probability.length
&& (pi + 1 != ci || pj != cj)) {
probability2[pi + 1][pj] += d;
} else {
probability2[pi][pj] += d;
}
if (pj + 1 < probability[pi].length
&& (pi != ci || pj + 1 != cj)) {
probability2[pi][pj + 1] += d;
} else {
probability2[pi][pj] += d;
}
}
}
for (int pi = 0; pi < probability2.length; pi++) {
for (int pj = 0; pj < probability2[pi].length; pj++) {
probability[pi][pj] = probability2[pi][pj];
probability2[pi][pj] = 0;
}
}
}
return "" + probability[gi][gj];
}
}

problem 1017:   Riffle Shuffle

how to solve It's easy to solve.

source code

import java.util.Scanner;

public class RiffleShuffle {
public static void main(String[] args) {
boolean test = !true;
if (test) {
testA();
testB();
} else {
run();
}
}

private static void testA() {
long start = System.nanoTime();
String s = run("9 1\n" + "3\n");
System.out.format("(%s)", ("3").equals(s) ? "A" : s);
System.out.format("[%.2f]\n", (System.nanoTime() - start) / 1e9);
}

private static void testB() {
long start = System.nanoTime();
String s = run("9 4\n" + "1 2 3 4\n");
System.out.format("(%s)", ("0").equals(s) ? "B" : s);
System.out.format("[%.2f]\n", (System.nanoTime() - start) / 1e9);
}

private static String run(String s) {
Scanner sc = new Scanner(s);
int n = sc.nextInt();
int riffle = sc.nextInt();
int[] c = new int[riffle];
for (int i = 0; i < c.length; i++) {
c[i] = sc.nextInt();
}
String solve = solve(n, riffle, c);
return solve;
}

private static void run() {
Scanner sc = new Scanner(System.in);
for (; sc.hasNext();) {
int n = sc.nextInt();
int riffle = sc.nextInt();
int[] c = new int[riffle];
for (int i = 0; i < c.length; i++) {
c[i] = sc.nextInt();
}
String solve = solve(n, riffle, c);
System.out.print(solve + "\n");
}
}

private static String solve(int n, int riffle, int[] c) {
int[] card = new int[n];
for (int i = 0; i < card.length; i++) {
card[i] = i;
}

for (int i = 0; i < c.length; i++) {
riffleshuffle(card, c[i]);
}

return "" + card[card.length - 1];
}

private static void riffleshuffle(int[] card, int c) {
int[] deckA = new int[card.length % 2 == 0 ? (card.length / 2)
: (card.length / 2 + 1)];
int[] deckB = new int[card.length / 2];
for (int i = 0; i < deckB.length; i++) {
deckB[i] = card[i];
}
for (int ai = 0, i = deckB.length; i < card.length; ai++, i++) {
deckA[ai] = card[i];
}
int[] deckC = new int[card.length];
int ai = 0;
int bi = 0;
int ci = 0;
for (;;) {
if (ai >= deckA.length && bi >= deckB.length) {
break;
}
for (int i = 0; i < c && ai < deckA.length; i++, ai++, ci++) {
deckC[ci] = deckA[ai];
}
for (int i = 0; i < c && bi < deckB.length; i++, bi++, ci++) {
deckC[ci] = deckB[bi];
}
}

for (int i = 0; i < deckC.length; i++) {
card[i] = deckC[i];
}
}

}

このページのトップヘ