Archive for the ‘ACM-ICPC’ Category

UVA – 1019 – Light Bulbs   Leave a comment


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.StringTokenizer;

public class LightBulbs {
	static String init, fin;
	static int len;
	static byte[][] dec;
	static int[][] dp;

	public static int go(int i, int mask) {
		if (i == len + 1)
			if ((mask >> 1 & 1) == fin.charAt(i - 1) - '0')
				return 0;
			else
				return 1000;

		if (dp[i][mask] != -1)
			return dp[i][mask];
		
		mask = mask << 1 | (init.charAt(i + 1) - '0');
		int min = 1000;
		if (((mask >> 2) & 1) == fin.charAt(i - 1) - '0' || i == 1) {
			min = Math.min(min, go(i + 1, mask & 3));
		}
		int mask2 = mask ^ 7;
		if (((mask2 >> 2) & 1) == fin.charAt(i - 1) - '0' || i == 1) {
			int v = 1 + go(i + 1, mask2 & 3);
			if (v < min) {
				min = v;
				dec[i][mask >> 1] = 1;
			}
		}
		return dp[i][mask >> 1] = min;
	}

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int cc = 1;
		while (true) {
			StringTokenizer strtok = new StringTokenizer(in.readLine());
			init = new BigInteger(strtok.nextToken()).toString(2);
			fin = new BigInteger(strtok.nextToken()).toString(2);
			if (init.equals("0") && fin.equals("0"))
				break;
			if (cc != 1)
				System.out.println();
			while (init.length() < fin.length())
				init = '0' + init;
			while (fin.length() < init.length())
				fin = '0' + fin;
			len = fin.length();
			init = '0' + init + '0';
			fin = '0' + fin + '0';
			dec = new byte[fin.length()][4];
			dp = new int[fin.length()][4];
			for (int i = 0; i < dp.length; i++)
				for (int j = 0; j < dp[i].length; j++)
					dp[i][j] = -1;
			int startMask = init.charAt(1) - '0';

			int min = go(1, startMask);

			char[] res = new char[len];
			int ind = 1;
			int mask = startMask;
			while (ind < len + 1) {
				int mask2 = mask << 1 | (init.charAt(ind + 1) - '0');
				if (dec[ind][mask] == 1) {
					res[ind - 1] = '1';
					mask2 ^= 7;
					mask2 &= 3;
				} else {
					res[ind - 1] = '0';
					mask2 &= 3;
				}
				mask = mask2;
				ind++;
			}
			System.out.printf("Case Number %d: %s\n", cc++,
					(min < 1000) ? new BigInteger(new String(res), 2)
							: "impossible");
		}
	}
}

Posted April 27, 2012 by epicrado in ACM-ICPC, Dynamic programming

UVA – 1096 – The Islands   Leave a comment


import java.io.*;
import java.util.*;

public class UVa1096 {
	static Double[][] dp;
	static int p1;
	static int p2;
	static Point[] inp;
	static byte[][] dec;

	static class Point {
		int x, y;

		Point(int x, int y) {
			this.x = x;
			this.y = y;
		}

		double distance(Point p) {
			return Math.sqrt((x - p.x) * (x - p.x) + (y - p.y) * (y - p.y));
		}

	}

	public static double go(int i, int j) {
		int ind = Math.max(i, j) + 1;
		if (dp[i][j] != null)
			return dp[i][j];
		if (ind == inp.length - 1)
			return dp[i][j] = inp[i].distance(inp[ind])
					+ inp[j].distance(inp[ind]);
		if (ind == p1) {
			dec[i][j] = -1;
			return dp[i][j] = inp[i].distance(inp[ind]) + go(p1, j);
		}
		if (ind == p2) {
			dec[i][j] = 1;
			return dp[i][j] = inp[j].distance(inp[ind]) + go(i, p2);
		}

		double d0 = inp[i].distance(inp[ind]) + go(ind, j);

		double d1 = inp[j].distance(inp[ind]) + go(i, ind);

		if (d0 < d1) {
			dec[i][j] = -1;
			return dp[i][j] = d0;
		} else {
			dec[i][j] = 1;
			return dp[i][j] = d1;
		}
	}

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int cc = 1;
		while (true) {
			StringTokenizer strtok = new StringTokenizer(in.readLine());
			int n = Integer.parseInt(strtok.nextToken());
			p1 = Integer.parseInt(strtok.nextToken());
			p2 = Integer.parseInt(strtok.nextToken());
			if (n == 0 && p1 == 0 && p2 == 0)
				break;
			dp = new Double[n][n];
			inp = new Point[n];
			for (int i = 0; i < n; i++) {
				strtok = new StringTokenizer(in.readLine());
				inp[i] = new Point(Integer.parseInt(strtok.nextToken()),
						Integer.parseInt(strtok.nextToken()));
			}
			dec = new byte[n][n];
			go(0, 0);
			LinkedList<Integer> r0 = new LinkedList<Integer>();
			r0.add(0);
			Stack<Integer> r1 = new Stack<Integer>();
			r1.push(0);
			int i = 0, j = 0, ind = 1;
			while (ind != n - 1) {
				if (dec[i][j] == 1) {
					r1.push(ind);
					j = ind;
					ind++;
				} else {
					r0.add(ind);
					i = ind;
					ind++;
				}
			}
			r0.add(n - 1);
			while (!r1.isEmpty())
				r0.add(r1.pop());
			int[] res = new int[r0.size()];
			int top = 0;
			for (int x : r0)
				res[top++] = x;
			double tot = 0;
			for (int a = 1; a < res.length; a++)
				tot += inp[res[a - 1]].distance(inp[res[a]]);

			StringBuilder out = new StringBuilder("");
			if (res[1] == 1) {
				out.append(res[0]);
				for (int k = 1; k < res.length; k++)
					out.append(" " + res[k]);
			} else {
				out.append(res[res.length - 1]);
				for (int k = res.length - 2; k >= 0; k--)
					out.append(" " + res[k]);
			}

			System.out.printf("Case %d: %.2f\n", cc++, tot);
			System.out.println(out);
		}
	}
}

Posted March 28, 2012 by epicrado in ACM-ICPC, Dynamic programming, UVA

Africa and the Middle East – Africa and Arab – 2010/2011   Leave a comment


4964 – What’s Next?

import java.util.Scanner;

public class WhatsNext {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int a, b, c;
		a = in.nextInt();
		b = in.nextInt();
		c = in.nextInt();
		while (a != 0 || b != 0 || c != 0) {
			if (c - b == b - a)
				System.out.println("AP " + (c + b - a));
			else
				System.out.println("GP " + (c * (b / a)));
			a = in.nextInt();
			b = in.nextInt();
			c = in.nextInt();
		}
	}
}

4967 – Tri graphs

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class TriGraphs {

	public static void main(String[] args) throws IOException {
		BufferedReader buf = new BufferedReader(
				new InputStreamReader(System.in));
		int count = 1;

		while (true) {
			int m = Integer.parseInt(buf.readLine().trim());
			if (m == 0)
				break;
			int n = m * 3;
			int j = 0;
			long[] costs = new long[n];
			for (int i = 0; i < m; i++) {
				String input = buf.readLine().trim();
				String[] line = input.split(" ");
				costs[j++] = Long.parseLong(line[0]);
				costs[j++] = Long.parseLong(line[1]);
				costs[j++] = Long.parseLong(line[2]);
			}
			costs[n - 1] = Integer.MAX_VALUE;
			costs[n - 3] += costs[n - 2];
			for (int i = n - 4; i >= 0; i--) {
				if (i % 3 == 0)
					costs[i] += Math.min(costs[i + 1], Math.min(costs[i + 3],
							costs[i + 4]));
				if (i % 3 == 1) {
					costs[i] += Math.min(Math.min(costs[i + 1], costs[i + 2]),
							Math.min(costs[i + 3], costs[i + 4]));
				}
				if (i % 3 == 2) {
					costs[i] += Math.min(costs[i + 2], costs[i + 3]);
				}
			}
			System.out.println((count++) + ". " + costs[1]);
		}
	}
}

I will update this when we get more AC

Posted September 4, 2011 by epicrado in ACM-ICPC