Sunday, October 19, 2008

counting sort + bit operation

UVa problem: Bridge Hands

每一花色牌不超过13张,4种花色,用一个long long表示,每16位一组表示一个花色

#include <stdio.h>
#include <string.h>

long long player[4];
int p[90];
char ip[4] = {'C', 'D', 'S', 'H'};
int seat[90];
char iseat[4] = {'S','W','N','E'};
int idx[90];
char inverse_idx[15] = {'0','1','2','3','4','5','6','7','8','9','T','J','Q','K','A'};
//int __builtin_ctz(long long);
int main() {
char buff[60];
seat['S'] = p['C'] = 0;
seat['W'] = p['D'] = 1;
seat['N'] = p['S'] = 2;
seat['E'] = p['H'] = 3;
int i, j;
for(i = 2; i <= 9; ++i)
idx[i+48] = i;
idx['T'] = 10;
idx['J'] = 11;
idx['Q'] = 12;
idx['K'] = 13;
idx['A'] = 14;
char t;
while((t = getchar()) != '#') {
while(gets(buff) && strlen(buff)==0){};
int side = seat[t];
memset(player, 0, sizeof(player));
for(i = 0; i < 52; i += 2) {
if(++side == 4) side = 0;
/* get card, set its bit */
player[side] |= 1LL<< (p[buff[i]]<<4LL) + idx[buff[i+1]];
}
gets(buff);
for(i = 0; i < 52; i += 2) {
if(++side == 4) side = 0;
player[side] |= 1LL<< (p[buff[i]]<<4LL) + idx[buff[i+1]];
}

for(i = 0; i < 4; ++i) {
int printed = 0;
printf("%c: ", iseat[i]);
for(j = 0; j < 4; ++j) {
/* get current color */
int c = player[i] & 0xffff;
player[i] >>= 16; /* next color */
while(c) {
int pos = __builtin_ctz(c);
c ^= 1LL << pos; /* clear printed bit */
printf("%c%c", ip[j], inverse_idx[pos]);
if(++printed < 13) printf(" ");
}
}
printf("\n");
}
}
}
/* gcc has built in __builtin_ctz, vc not*/ 
/*
int __builtin_ctz(long long c) {

for(int i = 0; i < 64; ++i)
if(c & (1LL<<i)) return i;
}*/