[World Final 2007][Uva Live Archive] 3736 - Consanguine Calculations

題目網址: http://goo.gl/uAp2A5

題意: 給定血型的種類及關係，問已知父、母及小孩之血型但其中一人未知，求未知的人其血型。



解法: 考慮所有血型的關係，然後建成對應表。

TAG: ad hoc

注意: 有用到狀態壓縮來方便計算

程式碼:

	/* Author: Cheng-Shih Wong
	* Prob. name: Consanguine Calculations
	* Prob. source: World Final 2007
	* Prob. URL: http://goo.gl/uAp2A5
	* Prob. catogory: ad hoc
	* Date: 2014/05/18
	*/
	#include <iostream>
	#include <cstdio>
	#include <cstring>
	using namespace std;
	#define N 10
	struct BloodType {
	int bt;
	int sign;
	BloodType( int _bt = 0, int _sign = 0 ):
	bt(_bt), sign(_sign) {}
	BloodType( char *s ) {
	if( s[0] == 'A' && s[1] == 'B' ) {
	bt = 2;
	sign = ( s[2]=='+' ? 0:1 );
	} else {
	switch( s[0] ) {
	case 'A': bt = 0; break;
	case 'B': bt = 1; break;
	case 'O': bt = 3; break;
	}
	sign = ( s[1]=='+' ? 0:1 );
	}
	}
	void withPar( const BloodType &op, int &btPossible, int &signPossible ) {
	if( !sign ) {
	signPossible = 3;
	} else {
	if( !op.sign ) signPossible = 3;
	else signPossible = 2;
	}
	if( bt == 0 ) {
	if( op.bt == 0 ) btPossible = 9;
	else if( op.bt == 1 ) btPossible = 15;
	else if( op.bt == 2 ) btPossible = 7;
	else btPossible = 9;
	} else if( bt == 1 ) {
	if( op.bt == 0 ) btPossible = 15;
	else if( op.bt == 1 ) btPossible = 10;
	else if( op.bt == 2 ) btPossible = 7;
	else btPossible = 10;
	} else if( bt == 2 ) {
	if( op.bt == 0 ) btPossible = 7;
	else if( op.bt == 1 ) btPossible = 7;
	else if( op.bt == 2 ) btPossible = 7;
	else btPossible = 3;
	} else {
	if( op.bt == 0 ) btPossible = 9;
	else if( op.bt == 1 ) btPossible = 10;
	else if( op.bt == 2 ) btPossible = 3;
	else btPossible = 8;
	}
	}
	void withChi( const BloodType &op, int &btPossible, int &signPossible ) {
	if( !sign ) {
	signPossible = 3;
	} else {
	if( !op.sign ) signPossible = 1;
	else signPossible = 3;
	}
	if( bt == 0 ) {
	if( op.bt == 0 ) btPossible = 15;
	else if( op.bt == 1 ) btPossible = 6;
	else if( op.bt == 2 ) btPossible = 6;
	else btPossible = 11;
	} else if( bt == 1 ) {
	if( op.bt == 0 ) btPossible = 5;
	else if( op.bt == 1 ) btPossible = 15;
	else if( op.bt == 2 ) btPossible = 5;
	else btPossible = 11;
	} else if( bt == 2 ) {
	if( op.bt == 0 ) btPossible = 15;
	else if( op.bt == 1 ) btPossible = 15;
	else if( op.bt == 2 ) btPossible = 7;
	else btPossible = 0;
	} else {
	if( op.bt == 0 ) btPossible = 5;
	else if( op.bt == 1 ) btPossible = 6;
	else if( op.bt == 2 ) btPossible = 0;
	else btPossible = 11;
	}
	}
	};
	char par1[N], par2[N], chi[N];
	bool p1f;
	BloodType p1, p2, c;
	void init( void )
	{
	static int i;
	if( par1[0] == '?' ) { swap( par1, par2 ); p1f = true; }
	else p1f = false;
	}
	int cntBit( int val )
	{
	int ret = 0;
	while( val ) {
	if( val&1 ) ++ret;
	val >>= 1;
	}
	return ret;
	}
	void printBTPossible( const int btPossible, const int signPossible )
	{
	static int i, j;
	static bool f, mul;
	static char *bt;
	f = false;
	if( (i = (cntBit(btPossible)*cntBit(signPossible))) == 0 ) {
	printf("IMPOSSIBLE");
	return;
	} else if( i == 1 ) mul = false;
	else mul = true;
	if( mul ) putchar('{');
	for( i = 1; i <= 8; i <<= 1 ) if( i&btPossible ) {
	switch( i ) {
	case 1: bt = "A"; break;
	case 2: bt = "B"; break;
	case 4: bt = "AB"; break;
	case 8: bt = "O"; break;
	}
	for( j = 1; j <= 2; j <<= 1 ) if( j&signPossible ) {
	if( !f ) {
	printf( "%s%c", bt, (j==1 ? '+':'-') );
	f = true;
	} else {
	printf( ", %s%c", bt, (j==1 ? '+':'-') );
	}
	}
	}
	if( mul ) putchar('}');
	}
	void solve( void )
	{
	static int i, btp, signp;
	if( par2[0] == '?' ) {
	p1 = BloodType( par1 );
	c = BloodType( chi );
	p1.withChi( c, btp, signp );
	if( p1f ) {
	printBTPossible( btp, signp );
	printf( " %s %s\n", par1, chi );
	} else {
	printf( "%s ", par1 );
	printBTPossible( btp, signp );
	printf( " %s\n", chi );
	}
	//printf( "(%d,%d) (%d,%d)\n", p1.bt, p1.sign, c.bt, c.sign );
	} else {
	p1 = BloodType( par1 );
	p2 = BloodType( par2 );
	printf( "%s %s ", par1, par2 );
	p1.withPar( p2, btp, signp );
	printBTPossible( btp, signp );
	putchar('\n');
	}
	}
	int main( void )
	{
	int i = 1;
	while( scanf( "%s %s %s", par1, par2, chi ) == 3 && (par1[0]!='E'||par2[0]!='N'||chi[0]!='D') ) {
	printf( "Case %d: ", i++ );
	init();
	solve();
	}
	return 0;
	}

view raw Consanguine Calculations.cpp hosted with ❤ by GitHub