EvbCFfp1XB

problem and my answer.

January 2013

problem TopCoder SRM565 MonstersValley

how to solve Dynamic Programming

source code

public class MonstersValley {
public int minimumPrice(long[] dread, int[] price) {
int n = dread.length;
int maxprice = 2 * n + 1;
long[][] maxdread = new long[n][maxprice];
maxdread[0][price[0]] = dread[0];
for (int i = 1; i < n; i++) {
int prev = i - 1;
for (int j = 0; j < maxprice; j++) {
if (maxdread[prev][j] == 0) {
continue;
}
if (maxdread[prev][j] >= dread[i]) {
maxdread[i][j] = Math.max(maxdread[i][j], maxdread[prev][j]);
}
maxdread[i][j + price[i]] = Math.max(maxdread[i][j + price[i]], maxdread[prev][j] + dread[i]);
}
}

int min = 0;
for (int i = 0; i < maxdread[n - 1].length; i++) {
if (maxdread[n - 1][i] > 0) {
min = i;
break;
}
}
return min;
}

public static void main(String[] args) {
test0();
test1();
test2();
test3();
}

private static void test0() {
test("0", new long[] { 8, 5, 10 }, new int[] { 1, 1, 2 }, 2);
}

private static void test1() {
test("1", new long[] { 1, 2, 4, 1000000000 }, new int[] { 1, 1, 1, 2 }, 5);
}

private static void test2() {
test("2", new long[] { 200, 107, 105, 206, 307, 400 }, new int[] { 1, 2, 1, 1, 1, 2 }, 2);
}

private static void test3() {
test("3", new long[] { 5216, 12512, 613, 1256, 66, 17202, 30000, 23512, 2125, 33333 }, new int[] { 2, 2, 1, 1, 1, 1, 2, 1, 2, 1 }, 5);
}

private static void test(String id, long[] input0, int[] input1, int output) {
long start = System.nanoTime();
int result = new MonstersValley().minimumPrice(input0, input1);
double time = (System.nanoTime() - start) / 1e9;
System.out.format("(%s)", output == result ? id : id + " expected:<" + output + "> but was:<" + result + ">");
System.out.format("[%.2f]\n", time);
}
}

problem AOJ 1072:   Rearranging Seats

how to solve Seats can be rearranged when the number of seats is even.

source code

import java.util.Scanner;

public class RearrangingSeats {
public static void main(String[] args) {
run();
}

private static void run() {
Scanner sc = new Scanner(System.in);
for (; sc.hasNext();) {
int r = sc.nextInt();
int c = sc.nextInt();
if (r == 0 && c == 0) {
break;
}
String result = solve(r, c);
System.out.print(result + "\n");
}
sc.close();
}

private static String solve(int r, int c) {
return (r * c) % 2 == 0 ? "yes" : "no";
}
}

console

0.1415926536
0.1415926536
0.0415926536
0.1000000000


source code

public class Remainder {
public static void main(String[] args) {
System.out.format("%.10f\n", Math.PI % 1);
System.out.format("%.10f\n", Math.PI % 1d);
System.out.format("%.10f\n", Math.PI % 0.1);
System.out.format("%.10f\n", 123 % 0.1);
}
}

It is a template of a double loop.

source code

for (int ${index1:newName(int)} = 0; ${index1} < ${array}.length; ${index1}++) {
    for (int ${index2:newName(int)} = 0; ${index2} < ${array}[${index1}].length; ${index2}++) {
        ${array}[${index1}][${index2}] = ${line_selection}${cursor};
    }
}

problem AOJ 1100:   Area of Polygons

how to solve If three points clockwise, I add the area of the triangle, if not, I subtract. I ignore this triangle. I repeat this to next triangle. Finally, I return the absolute value.

source code

import java.awt.Canvas;
import java.awt.Frame;
import java.awt.Graphics;
import java.text.NumberFormat;
import java.util.Scanner;
import java.util.concurrent.TimeUnit;

public class AreaofPolygons {
private static boolean test = !true;

public static void main(String[] args) {
if (test) {
testA();
testB();
testC();
for (;;)
testZ();
} else {
run();
}
}

private static void testA() {
test("A", "3\n" + "1 1\n" + "3 4\n" + "6 0\n", "1 8.5");
}

private static void testB() {
test("B", "7\n" + "0 0\n" + "10 10\n" + "0 20\n" + "10 30\n" + "0 40\n"
+ "100 40\n" + "100 0\n", "1 3800.0");
}

private static void testC() {
test("C", "7\n" + "0 0\n" + "10 10\n" + "5 20\n" + "10 30\n" + "0 40\n"
+ "100 40\n" + "100 0\n", "1 3750.0");
}

private static void testZ() {
StringBuilder sb = new StringBuilder();
int n = 10;
sb.append(n + "\n");
int[][] p = new int[n][2];
A: for (int i = 0; i < n; i++) {
p[i][0] = randomInt(0, 5);
p[i][1] = randomInt(0, 5);
for (int j = 1; j <= i; j++) {
int j2 = (j - 1) % n;
int j3 = j % n;
while ((j2 != i - 1 && j3 != i - 1 && j2 != i && j3 != i && intersect(
p[j2][0], p[j2][1], p[j3][0], p[j3][1], p[i - 1][0],
p[i - 1][1], p[i][0], p[i][1]))
|| (j2 != i && j3 != i && j2 != 0 && j3 != 0 && intersect(
p[j2][0], p[j2][1], p[j3][0], p[j3][1],
p[i][0], p[i][1], p[0][0], p[0][1]))) {
i = -1;
continue A;
}
}
}
for (int i = 0; i < n; i++) {
sb.append(p[i][0] + " " + p[i][1] + "\n");
}
test("Z", sb.toString(), "I'm not sure.");
}

private static int randomInt(int min, int max) {
return min + (int) (((max + 1) - min) * Math.random());
}

private static void test(String id, String input, String output) {
long start = System.nanoTime();
String result = run(input);
double time = (System.nanoTime() - start) / 1e9;
System.out.format("(%s)", output.equals(result) ? id : id
+ " expected:<" + output + "> but was:<" + result + ">");
System.out.format("[%.2f]\n", time);
}

private static class ACanvas extends Canvas {
int[][] a;

public ACanvas() {
}

@Override
public void paint(Graphics g) {
int c = 30;
for (int i = 1; i < a.length + 1; i++) {
int j = i % a.length;
int k = (i - 1) % a.length;
g.drawString("" + j + " (" + a[j][0] + "," + a[j][1] + ")", c
* a[j][0], getHeight() - c * a[j][1]);
g.drawLine(c * a[j][0], getHeight() - c * a[j][1], c * a[k][0],
getHeight() - c * a[k][1]);
}
}
}

private static void showFrame(int[][] a) {
Frame frame = new Frame();
ACanvas comp = new ACanvas();
comp.a = a;
frame.add(comp);
frame.setSize(400, 400);
frame.setVisible(true);
try {
TimeUnit.MILLISECONDS.sleep(60 * 1000);
} catch (InterruptedException e) {
e.printStackTrace();
}
frame.dispose();
}

private static String run(String input) {
Scanner sc = new Scanner(input);
int n = sc.nextInt();

int[][] p = new int[n][2];
for (int i = 0; i < p.length; i++) {
for (int j = 0; j < p[i].length; j++) {
p[i][j] = sc.nextInt();
}
}
String result = solve(n, p);
sc.close();
return "1 " + result;
}

private static void run() {
Scanner sc = new Scanner(System.in);
for (int test = 1; sc.hasNext(); test++) {
int n = sc.nextInt();
if (n == 0) {
break;
}

int[][] p = new int[n][2];
for (int i = 0; i < p.length; i++) {
for (int j = 0; j < p[i].length; j++) {
p[i][j] = sc.nextInt();
}
}

String result = solve(n, p);
System.out.print(test + " " + result + "\n");
}
sc.close();
}

private static String solve(int n, int[][] p) {
double area = 0;
for (int i = 2; i < p.length; i++) {
int x0 = p[0][0];
int y0 = p[0][1];
int x1 = p[i - 1][0];
int y1 = p[i - 1][1];
int x2 = p[i][0];
int y2 = p[i][1];
int ccw = ccw5(x0, y0, x1, y1, x2, y2);
if (ccw == -1) {
area += heronsFormula(distance(x0, y0, x1, y1),
distance(x1, y1, x2, y2), distance(x2, y2, x0, y0));
} else if (ccw == 1) {
area -= heronsFormula(distance(x0, y0, x1, y1),
distance(x1, y1, x2, y2), distance(x2, y2, x0, y0));
}
}
NumberFormat nf = NumberFormat.getInstance();
nf.setMinimumFractionDigits(1);
nf.setMaximumFractionDigits(1);
nf.setGroupingUsed(false);
return "" + nf.format(Math.abs(area));
}

private static double distance(double x1, double y1, double x2, double y2) {
x1 -= x2;
y1 -= y2;
return Math.sqrt(x1 * x1 + y1 * y1);
}

private static double heronsFormula(double a, double b, double c) {
double s = (a + b + c) / 2d;
return Math.sqrt(s * (s - a) * (s - b) * (s - c));
}

private static int ccw5(int x0, int y0, int x1, int y1, int x2, int y2) {
int dx1 = x1 - x0;
int dy1 = y1 - y0;
int dx2 = x2 - x0;
int dy2 = y2 - y0;
if (dx1 * dy2 > dy1 * dx2) {
return 1;
}
if (dx1 * dy2 < dy1 * dx2) {
return -1;
}
if ((dx1 * dx2 < 0) || (dy1 * dy2 < 0)) {
return -2;
}
if ((dx1 * dx1 + dy1 * dy1) < (dx2 * dx2 + dy2 * dy2)) {
return 2;
}
return 0;
}

private static boolean intersect(int l1p1x, int l1p1y, int l1p2x,
int l1p2y, int l2p1x, int l2p1y, int l2p2x, int l2p2y) {
return (ccw5(l1p1x, l1p1y, l1p2x, l1p2y, l2p1x, l2p1y)
* ccw5(l1p1x, l1p1y, l1p2x, l1p2y, l2p2x, l2p2y) <= 0)
&& (ccw5(l2p1x, l2p1y, l2p2x, l2p2y, l1p1x, l1p1y)
* ccw5(l2p1x, l2p1y, l2p2x, l2p2y, l1p2x, l1p2y) <= 0);
}
}


このページのトップヘ