Odd Man Out

Given an odd list of couples of numbers (each number appears twice), find the number that occurs only once.
The solution is a mere xor on all the numbers as:


Also, xor is commutative:

so if we have a sample input A, B, C, A, B:

C++ implementation:

#include <iostream>
#include <fstream>
#include <iomanip>
using namespace std;

#define N 1024
typedef unsigned long long int64;

int n, g;
int64 card, cardXor;
ofstream ofile;
ifstream ifile;

int main() {
	int i, j;
	ifile.open("in.txt");
	ofile.open("out.txt");
	ifile >> n;
	for (i = 0; i < n; ++i) {
		// init
		cardXor = 0;
		// in
		ifile >> g;
		for (j = 0; j < g; cardXor ^= card, ++j)
			ifile >> card;
		// out
		ofile << "Case #" << i + 1 << ": " << cardXor << endl;
	}
	return 0;
}

10344 – 23 Out Of 5

Generate all orders/permutations of 5 integers before getting any input (you can even generate them before compiling!). That’s (5! = 120) permutations.

• Get input and store it.
• Order the input according to the previously generated permutations.
• Brute-force attack all the possible operations on the 5 integers until you get 23. Those are (34 = 81) permutations.
• If no permutation of integers and operations give 23, that’s "Impossible".

Recursive C++ implementation, 175 rank.

#include <iostream>
using namespace std;

const int target = 23;

// generate permutations for 5 elements
int genUsed, perm[120], permI, nPerm, thisPerm;
void generatePermutations() {
	if (permI == 5)
		perm[nPerm++] = thisPerm;
	else
		for (int i = 0; i < 5; ++i)
			if (~genUsed & (1 << i)) {
				genUsed ^= (1 << i);
				thisPerm = thisPerm * 5 + i;
				permI++;
				generatePermutations();
				permI--;
				thisPerm /= 5;
				genUsed ^= (1 << i);
			}
}

// generate operation and calculate
int in[5], operand[5];
bool isGood(int result, int opI) {
	if (opI == 5)
		return result == target;
	else
		return isGood(result - operand[opI], opI + 1) || isGood(result * operand[opI], opI + 1) || isGood(result + operand[opI], opI + 1);
	return false;
}

int main() {
	// generate
	genUsed = 0, nPerm = 0;
	generatePermutations();
	// input
	while (cin >> in[0] >> in[1] >> in[2] >> in[3] >> in[4]) {
		if (in[0] == 0 && in[1] == 0 && in[2] == 0 && in[3] == 0 && in[4] == 0)
			break;
		// permute
		int p, i;
		for (i = 0; i < 120; ++i) {
			p = perm[i];
			for (int i = 0; i < 5; ++i) {
				operand[i] = in[p % 5];
				p /= 5;
			}
			if (isGood(operand[0], 1))
				break;
		}
		if (i < 120)
			cout << "Possible" << endl;
		else
			cout << "Impossible" << endl;
	}
}