Category Archives: Adhoc

UVA – 737 – Gleaming the Cubes – O(N)

#include <iostream>
using namespace std;

#define N 1<<12

struct Point3D {
	int x, y, z;
};

#define MN(x, y)  (y ^ ((x ^ y) & -(x < y)))
#define MX(x, y)  (x ^ ((x ^ y) & -(x < y)))

Point3D minmaxp(Point3D a, Point3D b, int mn) {
	if (mn)
		return Point3D { MN(a.x, b.x), MN(a.y, b.y), MN(a.z, b.z) };
	return Point3D { MX(a.x, b.x), MX(a.y, b.y), MX(a.z, b.z) };
}

int main() {
	Point3D vi1, vi2, v1, v2;
	int n, s;
	while ((cin >> n) && n) {
		for (int i = 0; i < n; i++) {
			cin >> v1.x >> v1.y >> v1.z >> s;
			v2 = Point3D { v1.x + s, v1.y + s, v1.z + s };
			if (!i)
				vi1 = v1, vi2 = v2;
			vi2 = minmaxp(v2, vi2, 1), vi1 = minmaxp(v1, vi1, 0);
		}
		int v = (vi2.x - vi1.x) * (vi2.y - vi1.y) * (vi2.z - vi1.z);
		cout << max(v, 0) << endl;
	}
}

UVA – 00719 – Glass Beads – [Suffix Array]

#include <cstdio>
#include <cstring>
#include <utility>
#include <iostream>
#include <algorithm>

using namespace std;

const int MAXN = 100100;

struct SuffixArray {
	pair<int, int> sf[MAXN];
	int sa[MAXN], r[MAXN], height[MAXN], h[MAXN];

	struct mycmp {
		pair<int, int> * suffix;
		mycmp(pair<int, int> * suffix_) :
			suffix(suffix_) {
		}
		bool operator()(int lhs, int rhs) {
			return suffix[lhs] < suffix[rhs];
		}
	};

	void init(int n, const char a[MAXN]) {
		sa[0] = 0; // n = 1
		for (int i = 0; i < n; ++i)
			r[i] = a[i];
		for (int i, m = 1; m < n; m <<= 1) {
			for (i = 0; i < n; sa[i] = i++)
				sf[i] = make_pair(r[i], r[(i + m) % n]);
			stable_sort(sa, sa + n, mycmp(sf));
			for (i = 1, r[sa[0]] = 0; i < n; ++i)
				r[sa[i]] = sf[sa[i]] != sf[sa[i - 1]] ? i : r[sa[i - 1]];
		}
	}
} sa;

int main() {
	char s[100003];
	int T;
	scanf("%d", &T);
	while (T--) {
		scanf("%s", s);
		int len = strlen(s);
		sa.init(len, s);
		printf("%d\n", sa.sa[0] + 1);

	}
}

USACO 3.2.3 – Spinning Wheels


#include <cstdio>
#include <cstring>

int main() {
	freopen("spin.in", "r", stdin), freopen("spin.out", "w", stdout);
	int v[5], nwidges[5], wd[5][5][2], open[360] = { 0 };
	for (int i = 0; i < 5; i++) {
		scanf("%d %d", v + i, nwidges + i);
		for (int j = 0; j < nwidges[i]; j++)
			scanf("%d %d", wd[i][j], wd[i][j] + 1);
	}
	for (int t = 0; t < 360; memset(open, 0, sizeof open), t++)
		for (int w = 0; w < 5; w++)
			for (int n = 0; n < nwidges[w]; n++)
				for (int p=t*v[w]+wd[w][n][0]; p<=t*v[w]+wd[w][n][0]+wd[w][n][1]; p++) {
					if (++open[p % 360] == 5) {
						printf("%d\n", t);
						return 0;
					}
				}

	puts("none");
}

USACO 2.2.4 – Party Lamps

#include <cstdio>
#include <iostream>
#include <set>

using namespace std;

int main() {
	set<string> s;
	int lamps, N, C, ON, OFF, on = 0, off = 0;
	freopen("lamps.in", "r", stdin), freopen("lamps.out", "w", stdout);
	cin >> N >> C;
	C = (C % 2) ? (C > 3 ? 3 : C) : (C > 4 ? 4 : C);
	while (cin >> ON && ON != -1)   on  |= 1 << (5 - ((ON  - 1) % 6));
	while (cin >> OFF && OFF != -1) off |= 1 << (5 - ((OFF - 1) % 6));

	for (int  m = 0; m < 16; m++) {
		if (C < __builtin_popcount(m)) continue;
		lamps  = (m & 1 ? 0 : 63) ^ (m & 2 ? 21 : 0) ^ (m & 4 ? 42 : 0) ^ (m& 8 ? 36 : 0);
		if ((lamps & off) == 0 && (~lamps & on) == 0) {
			string b = "";
			for (int i = 0; i < N; i++)
				b += (((lamps >> (5 - (i % 6))) & 1) ? "1" : "0");
			s.insert(b);
		}
	}
	if (!s.size())
		puts("IMPOSSIBLE");
	else
		for (set<string>::iterator i = s.begin(); i != s.end(); i++)
			cout << *i << endl;
	return 0;
}

USACO 2.2.3 – Runaround Numbers

#include <cstdio>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cmath>
typedef unsigned long long int LL;
using namespace std;

int main() {
	LL M, v, i, d, l, n;
	freopen("runround.in", "r", stdin), freopen("runround.out", "w", stdout);
	cin >> M;
	for (LL m = M + 1;; m++) {
		for (i = 0, v = 0, n = m; n; v |= (1 << (n % 10)), n /= 10, i++)
			if (!(n % 10) || (v & (1 << (n % 10))))
				break;
		if (!(v = 0) && n) continue;

		stringstream ss; ss << m ; string s = ss.str();

		for (d = (s[0] - '0') % s.size(), l = 0; l <= i; l++, v |= (1 << (s[d] - '0')), d = (d + (s[d] - '0')) % s.size())
			if (v & (1 << (s[d] - '0')))
				break;

		if (l >= i) {
			cout << m << endl;
			break;
		}
	}
	return 0;
}

USACO 2.2.1 – Preface Numbering

#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;
char s[10]=" IVXLCDM";
int n, c[10] = {0} ,delta[10][5] = {{},{-1,-10},{-1,-1,-10},{-1,-1,-1,-10},{0,-1,-10}, {0, -10},{0,-1,-10},{0,-1,-1,-10},{0,-1,-1,-1,-10},{1,-1,-10} };

int main() {
	freopen("preface.in", "r", stdin), freopen("preface.out", "w", stdout);
	scanf("%d", &n);
	for(int p=1; p<=n; p++)
		for(int e=1; e<=4; e++){
			int d = int(p/(round(pow(10, e-1))))%10;
			if(!d) continue;
			for(int i=0; delta[d][i]!=-10; i++)
				c[2*e +delta[d][i]]++;
		}
	for(int i=1; i<=7 && c[i]; i++)
		cout << s[i] << " " << c[i]<<endl;
	return 0;
}

USACO 2.1.5 – Hamming Codes

#include <algorithm>
#include <cstdio>
#include <vector>
#include <iostream>
#include <string>
#include <sstream>
#include <iterator>

using namespace std;

int main() {
	freopen("hamming.in", "r", stdin), freopen("hamming.out", "w", stdout);
	int B, D, a = -1;size_t i, N;
	scanf("%d %d %d", &N, &B, &D);
	vector<int> v;
	while (++a < (1 << B) && v.size() != N) {
		for (i = 0; i < v.size();  i++)
			if (__builtin_popcount(a ^ v[i]) < D)
				break;
		if (i == v.size())
			v.push_back(a);
	}
	for(i=0; i<v.size(); i+= 10){
		stringstream  s;
		copy(v.begin() +i ,v.begin()+i +min(10,int(v.size()-i)), ostream_iterator<int>(s," "));
		puts(s.str().erase(s.str().length()-1).c_str());
	}
	return 0;
}

USACO 1.5.1 – Number Triangles


#include <iostream>
#include <cstdio>
using namespace std;

#define fo(ii, i0, nn, dd) for(ii=i0; ii!=nn; ii+= dd)
#define fo2(ii, i0, in, id, jj, j0, jn, jd) fo(ii, i0, in, id) fo( jj, j0, jn, jd)

int main() {
	int i, j, R, a[1001][1001];
	freopen("numtri.in", "r", stdin), freopen("numtri.out", "w", stdout);
	scanf("%d", &R);

	fo2(i, 0, R, 1, j, 0, i+1, 1)
			scanf("%d", &a[i][j]);
	fo2(i, R-1, 0, -1, j, 0, i, 1)
			a[i - 1][j] += max(a[i][j], a[i][j + 1]);

	printf("%d\n", a[0][0]);

	return 0;
}

USACO 1.1.4 – Broken Necklace


int main_beads() {
	int r, N, color(0), cur(0), w(0), pre(0), best(0);
	string s;
	fin >> N >> s;
	s = s + s;
	for (r = 0; r < 2 * N && pre + cur < N; r++) {
		if (s[r] != 'w' && s[r] != color)
			color = s[r], best = max(best, pre + cur), pre = cur - w, cur = w;
		w = (s[r] == 'w') ? w + 1 : 0, cur++;
	}

	fout << max(best, pre + cur) << endl;
	return 0;
}

USACO 1.1.3 – Friday the Thirteenth



int isLeap(int y) {	return y % 4 == 0 && (y % 100 != 0 || (y % 100 == 0 && y % 400 == 0)); }

int main_friday() {
	ofstream fout("friday.out");
	ifstream fin("friday.in");

	int nm[][12] = { { 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 }, { 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 } };
	int sum[8] = { 0};
	int N, d = 0, md = 0, wd = 3, m = 0, y = 1900;
	fin >> N;

	while (y < 1900 + N && ++d && ++md) {
		if (md == 13)
			sum[wd]++;
		if (d == 365 + isLeap(y))
			y++, m = md = d = 0;
		if (md == nm[isLeap(y)][m])
			m++, md = 0;
		wd = (wd % 7) + 1;
	}

	for (int i = 1; i < 7; i++)
		fout << sum[i] << " ";
	fout << sum[7] << endl;
	return 0;
}