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");
		}
	}
}

Advertisements

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: