USACO 1.4.2 – Clocks

convert to base 4 then run through the power set of the possible moves “00…01” to “33…33” , pre-compute when would each clock change. seek for minimum solution.

*this problem has various other solution methods.


/*
 ID: mohmdad5
 PROG: clocks
 LANG: C++
 */

#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
using namespace std;

string s, best = "999999999";

string itoa(int val, int base) {
	string buf;
	do {
		buf.push_back("0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"[val % base]);
		val /= base;
	} while (val);
	while (buf.size() != 9)
		buf.append("0");
	return buf;
}

int main() {

	ofstream fout("clocks.out");
	ifstream fin("clocks.in");
	int t[10], change[10][10] = { { 0 }, { 1, 2, 4, 0 }, { 1, 2, 3, 5, 0 }, {2, 3, 6, 0 }, { 1, 4, 5, 7, 0 }, { 1, 3, 5, 7, 9, 0 }, { 3, 5, 6, 9, 0 }, { 4, 7, 8, 0 }, { 5, 7, 8, 9, 0 }, { 6, 8, 9, 0 } };
	vector<int> c, v;

	c.push_back(0);
	for (int i = 1, a; i <= 9; i++) {
		fin >> a;
		c.push_back(a);
	}

	for (int j, mask = 0, sum, i; mask < 262144; mask++) {
		s = itoa(mask, 4);
		copy(c.begin(), c.end(), t);
		for (sum = 0, i = 1; i < 10;sum+= t[i]%12, i++)
			for (j = 0; change[i][j]; j++)
				t[i] += 3 * (s[change[i][j] - 1] - '0');

			best = (!sum && s < best) ? s : best;
	}

	int started = 0;
	for (size_t i = 0; i < best.size(); i++)
		for (int j = 0; j < best[i] - '0'; j++)
				fout << (started++ ? " " : "") << (i + 1);
	fout << endl;
	return 0;
}
Advertisements

One thought on “USACO 1.4.2 – Clocks

  1. Raman Gupta says:

    I am confused in two test cases that is “when all the clocks are already at 12” and “if there is no possible solution” , what should I print.Please help .

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: