11959 – Dice

A brute-force problem.
Given two six-sided dice in a certain orientation, you have to determine whether they’re equal. The die is represented by an integer with each digit representing one face of the die as follows: top, bottom, front, left, back, right
To check whether d1 and d2 are equivalent, keep d1 in a fixed orientation and rotate d2 to all possible orientation. If they match in any orientation, they’re equal.
Now, we need to know how to get all possible orientations; If we rotate the die so that each face appears on top once, that’s 6 orientations. For each of these, we can spin the die along the y-axis to get 4 more positions. Summing up, that’s a total of 6x4 different orientations we have to check.
Time to actually implement those permutations. Here are two macros that we’ll rely on in generating the orientations. R(d): rotates the die d clockwise along the y-axis, F(d): rotates along the x-axis:

#define R(d) ( ((d) & 0x000F00) << 12 | ((d) & 0x00000F) << 16 | ((d) & 0x00F0F0) | ((d) & 0x0F0000) >> 8 | ((d) & 0xF00000) >> 20 )
#define F(d) ( ((d) & 0x0000F0) << 16 | ((d) & 0x00F000) << 4 | ((d) & 0xF00000) >> 8 | ((d) & 0x000F0F) | ((d) & 0x0F0000) >> 12 )

The rest should be easier. Coded in C++:

#include <cstdio>
using namespace std;

#define R(d) ( ((d) & 0x000F00) << 12 | ((d) & 0x00000F) << 16 | ((d) & 0x00F0F0) | ((d) & 0x0F0000) >> 8 | ((d) & 0xF00000) >> 20 )
#define F(d) ( ((d) & 0x0000F0) << 16 | ((d) & 0x00F000) << 4 | ((d) & 0xF00000) >> 8 | ((d) & 0x000F0F) | ((d) & 0x0F0000) >> 12 )

bool E(long long d1, long long d2) {
	return ((d1) == (d2) || (d1) == R((d2)) || (d1) == R(R((d2))) || (d1) == R(R(R((d2)))));
}

char ans[2][16] = { "Not Equal", "Equal" };

int main() {
	long long t, d1, d2;
	scanf("%lld", &t);
	while (t--) {
		bool out = false;
		scanf("%llx %llx", &d1, &d2);
		out = E(d1, d2) || E(d1, F(d2)) || E(d1, F(F(d2))) || E(d1, F(F(F(d2))))
				|| E(d1, F(R(d2))) || E(d1, F(R(R(R(d2)))));
		printf("%s\n", ans[out]);
	}
	return 0;
}

Rank 41.

199A – Hexadecimal’s theorem

The basic approach is:


Hence, if we generate the list of all Fibonacci numbers up to (input bound) the answer is just a binary-search-away.
C++ implementation:

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

typedef unsigned long long int64;
#define N 48

int64 fib[N];
int nFib;

int64 generate() {
	fib[0] = 0;
	fib[1] = 1;
	for (int i = 2; i < N; ++i)
		fib[i] = fib[i - 1] + fib[i - 2];
	return fib[N - 1];
}

int main(void) {
	generate();
	int64 n;
	cin >> n;
	int64 * p = upper_bound(fib, fib + N, n) - 1;
	if (p - 4 >= fib)
		cout << *(p - 4) << " " << *(p - 3) << " " << *(p - 1) << endl;
	else
		cout << "0 0 " << *p << endl;
	return EXIT_SUCCESS;
}

There’s an other naive (totally valid) solution. You noticed that 0 is a Fibonacci.

#include <stdio.h>
#include <stdlib.h>

int main(void) {
	int n;
	scanf("%d", &n);
	printf("0 0 %d\n", n);
	return EXIT_SUCCESS;
}

Ironic!!!

10067 – Playing With Wheels

A breadth first search problem.
You start with a sequence of four digits (start). You’re required to reach a certain sequence (end). Given you’re at a certain sequence (vertex), you’re allowed to spin 1 digit each time to move to another sequence (edge) forming a sequence of spins (path). You’re required to calculate the least number of spins (shortest path.
From here on, the solution is straight forward.
Caution

• Forbidden cases may forbid the start or the end. I don’t know if the judge cases cover that or not.
• Reset your variables after each case.

Instead of taking input as decimal digits, I handled them in hexadecimal. I thought operations on hexadecimal digits would be faster (bit-wise operations and shifting), but I still got a low rank.
C++ code rank 649:

#include <iostream>
#include <limits>
#include <cstring>
#include <queue>
using namespace std;

#define N (10)
#define M (8)
#define MAX (0x10000)

#define READ_DIGIT(x, t, i) { cin >> (t); (x) |= ((t) << (i)); }
#define READ_CONFIG(x) { x = 0; int t; READ_DIGIT(x, t, 12); READ_DIGIT(x, t, 8); READ_DIGIT(x, t, 4); READ_DIGIT(x, t, 0) }
#define ADD(p, m, s, i) (((((p) >> (i)) & 0x000F) s (((m) >> (i)) & 0x000F)) + N) % N
#define ADD_ALL(d, p, m, s) { d[0] = ADD(p, m, s, 0); d[1] = ADD(p, m, s, 4); d[2] = ADD(p, m, s, 8); d[3] = ADD(p, m, s, 12); }
#define SUM(d) (d[0]) + (d[1] << 4) + (d[2] << 8) + (d[3] << 12)
#define PUSH(p, newP, q, g) { if (g[newP] == -1) { g[newP] = g[p] + 1; q.push(newP); } }

unsigned int m[M] = { 0x0001, 0x0010, 0x0100, 0x1000 };
int g[MAX];
unsigned int start, end;

int bfs() {
	int d[4], newP;
	// init
	queue<unsigned int> q;
	if (g[start] == -1) {
		g[start] = 0;
		q.push(start);
	}
	// bfs
	while (q.size()) {
		// pop
		unsigned int p = q.front();
		q.pop();
		// end
		if (p == end)
			return g[p];
		// still
		else
			for (int i = 0; i < M; ++i) {
				// +ve
				ADD_ALL(d, p, m[i], +);
				newP = SUM(d);
				PUSH(p, newP, q, g);
				// -ve
				ADD_ALL(d, p, m[i], -);
				newP = SUM(d);
				PUSH(p, newP, q, g);
			}
	}
	return -1;
}

int main() {
	int nCases, nForbidden;
	cin >> nCases;
	for (int caseI = 0; caseI < nCases; ++caseI) {
		// reset
		memset(g, -1, sizeof(g));
		// start & end
		READ_CONFIG(start);
		READ_CONFIG(end);
		// forbidden
		cin >> nForbidden;
		for (int i = 0, f; i < nForbidden; ++i) {
			READ_CONFIG(f);
			g[f] = 0;
		}
		// solve
		cout << bfs() << endl;
	}
	return 0;
}