UVA Consanguine Calculations (UVALive 3736, World Finals >> 2007 - Tokyo)

///     Raihan Ruhin
///     CSE, Jahangirnagar University.
///     Dhaka-Bangladesh.
///     id: raihanruhin (topcoder / codeforces / codechef / uva / uvalive / spoj), 3235 (lightoj)
///     mail: raihanruhin@ (yahoo / gmail / facebook)
///     blog: ruhinraihan.blogspot.com

#include<bits/stdc++.h>
using namespace std;

#define SET(a) memset(a,-1,sizeof(a))
#define CLR(a) memset(a,0,sizeof(a))
#define PI acos(-1.0)

#define MOD 1000000007
#define MX 100010

bool possible(string f, string m, string c)
{
    int fl=f.size()-1, ml=m.size()-1, cl=c.size()-1;

    if(f[fl]=='-' && m[ml]=='-' && c[cl]=='+') return false;
    bool A1=false, A2=false, B1=false, B2=false, O1=false, O2=false;

    if(f[0]=='A')
        if(f[1]=='B') A1=true, B1=true;
        else A1=true, O1=true;
    if(m[0]=='A')
        if(m[1]=='B') A2=true, B2=true;
        else A2=true, O2=true;

    if(f[0]=='B') B1=true, O1=true;
    if(m[0]=='B') B2=true, O2=true;

    if(f[0]=='O') O1=true;
    if(m[0]=='O') O2=true;

    if(c[0]=='A' && c[1]=='B')  return ((A1 && B2) || (A2 && B1));
    if(c[0]=='A') return (A1 || A2);
    if(c[0]=='B') return (B1 || B2);
    if(c[0]=='O') return (O1 && O2);

return false;
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    int tc, kk=1, n;
    string f, m, c, s[]={"A+", "A-", "B+", "B-", "AB+", "AB-", "O+", "O-"};
    char ch;
    while(cin>>f>>m>>c && f!="E")
    {
        vector<string>ans;
        //cout<<f<<" "<<m<<" "<<c<<endl;
        cout<<"Case "<<kk++<<": ";
        if(f=="?")
        {
            for(int i=0;i<8;i++)
                if(possible(s[i], m, c))
                    ans.push_back(s[i]);
            if(ans.size()==0)   cout<<"IMPOSSIBLE";
            else if(ans.size()==1) cout<<ans[0];
            else
            {
                cout<<"{";
                for(int i=0;i<ans.size();i++)
                {
                    if(i) cout<<", ";
                    cout<<ans[i];
                }
                cout<<"}";
            }
            cout<<" "<<m<<" "<<c;
        }
        else if(m=="?")
        {
            for(int i=0;i<8;i++)
                if(possible(f, s[i], c))
                    ans.push_back(s[i]);
            cout<<f<<" ";
            if(ans.size()==0)   cout<<"IMPOSSIBLE";
            else if(ans.size()==1) cout<<ans[0];
            else
            {
                cout<<"{";
                for(int i=0;i<ans.size();i++)
                {
                    if(i) cout<<", ";
                    cout<<ans[i];
                }
                cout<<"}";
            }
            cout<<" "<<c;
        }
        else
        {
            for(int i=0;i<8;i++)
                if(possible(f, m, s[i]))
                    ans.push_back(s[i]);
            cout<<f<<" "<<m<<" ";
            if(ans.size()==0)   cout<<"IMPOSSIBLE";
            else if(ans.size()==1) cout<<ans[0];
            else
            {
                cout<<"{";
                for(int i=0;i<ans.size();i++)
                {
                    if(i) cout<<", ";
                    cout<<ans[i];
                }
                cout<<"}";
            }
        }
        cout<<"\n";
    }
return 0;
}