#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int MAX_VAL = 1024 * 4 + 1023 * 3 + 1022 * 2 + 1021;
const int UNI_16 = 0xFFFF;

struct Node {
int comb;
int cnt;
Node* next;

Node(int c, Node* n) {
comb = c;
cnt = 1;
next = n;
}
};

Node* g_value[MAX_VAL + 1];
int g_num[16];
int g_cnt8[UNI_16];

void addValue(int value, int comb);
bool card4(int set, int* num);
void clear();
void getAllCnts8();
void getAllValues4();

void addValue(int value, int comb) {
Node*& head = g_value[value];
if (head != NULL && head->comb == comb) {
head->cnt++;
}
else {
Node* node = new Node(comb, head);
head = node;
}
}

//If the cardinality of the set is 4,
//then put the 4 numbers in to array num and return true.
bool card4(int set, int* num) {
int card = 0;
int mask = 1;
for (int i = 0; i < 16; i++) {
if (mask & set) {
if (card == 4) {
card = 0;
break;
}
num[card] = g_num[i];
card++;
}
mask <<= 1;
}
return card == 4;
}

void clear() {//Free all the linked lists.
for (int i = 0; i <= MAX_VAL; i++) {
if (g_value[i] != NULL) {
Node* p = g_value[i];
while (p != NULL) {
Node* pre = p;
p = p->next;
delete pre;
}
g_value[i] = NULL;
}
}
}

void getAllCnts8() {
memset(g_cnt8, 0, sizeof(g_cnt8));
for (int val = 0; val <= MAX_VAL; val++) {
if (g_value[val] != NULL) {
for (Node* i = g_value[val]; i != NULL; i = i->next) {
for (Node* j = i->next; j != NULL; j = j->next) {
if ((i->comb & j->comb) == 0) {
g_cnt8[i->comb | j->comb] += i->cnt * j->cnt;
}
}
}
}
}
}

void getAllValues4() {
sort(g_num, g_num + 16);//Must sort, or "next_permutation()" won't work.
int num[4];
for (int comb = 0xF; comb <= 0xF000; comb++) {
if (card4(comb, num)) {
do {
int value = num[0] * 4 + num[1] * 3 + num[2] * 2 + num[3];
addValue(value, comb);
} while (next_permutation(num, num + 4));
}
}
}

bool input() {
bool hasNext = false;
cin >> g_num[0];
if (g_num[0] != 0) {
hasNext = true;
for (int i = 1; i < 16; i++) {
cin >> g_num[i];
}
}
return hasNext;
}

int solve() {
getAllValues4();
getAllCnts8();
int cnt = 0;
for (int comb8 = 0xFF; comb8 <= 0xFF00; comb8++) {
cnt += g_cnt8[comb8] * g_cnt8[comb8 ^ UNI_16];
}
return cnt / 2;
}

int main() {
memset(g_value, 0, sizeof(g_value));
int i = 1;
while (input()) {
cout << "Case " << i << ": " << solve() << endl;
clear();
i++;
}
return 0;
}

  回復(fù)  更多評(píng)論