12247 – Jollo UVA Solution

This is an easy problem from uva judge http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3399

Ad hoc,  complete search, data structures.

How I did it

• Read the cards from the princess, read the cards from the prince.
• If the cards are equal to 0 stop the program.
• Generate all possible games with the cards. (12 possibles games).
• For every game find the lowest card to win the game and save that card in a set of probable answers.
• In all possible games try every possible answer and check if is enough to win every game.(12 games).
• Print the answer.

Hints

•  Generate all possible games. (Always 12)
• The possible status of a game for prince:  Win Win, Win Lose, Lose Win, Lose Lose.
• If we have a game Lose Lose, print -1.

Critical Input

1 2 3 51 52

Critical Output

4

Code

#include <iostream>
#include <cstdio>
#include <vector>
#include <bitset>
#include <set>
using namespace std;
typedef pair<int,int> ii;

struct game
{
    ii p1;
    ii p2;
    ii p3;
};

vector<int>girl,boy;
vector<game> gameArray;
bitset<54> myCards;
set<int> mySet;

bool isWW(int pos)
{
    game tmp = gameArray[pos];

    if(tmp.p1.first < tmp.p1.second && tmp.p2.first < tmp.p2.second)
       return true;
    else
        return false;
}

vector<int> getNotUsed(int x, vector<int>vec)
{
    vector<int> ans;

    for(int a=0; a<vec.size(); a++)
        if(x!=a)
           ans.push_back(vec[a]);
return ans;
}

void generate()
{
    vector<int> nGirl, nBoy;
    for(int x=0; x<girl.size(); x++)
    {
        for(int y=0; y<boy.size(); y++)
        {
            ii p1 = make_pair(girl[x], boy[y]);

            nGirl = getNotUsed(x,girl);
            nBoy  = getNotUsed(y, boy);

            ii p2 = make_pair(nGirl[0], nBoy[0]);
            ii p3 = make_pair(nGirl[1], -1);

            game g1, g2;
            g1.p1 = p1;g1.p2 = p2;g1.p3 = p3;
            gameArray.push_back(g1);

            p2 = make_pair(nGirl[1], nBoy[0]);
            p3 = make_pair(nGirl[0], -1);
            g2.p1 = p1;g2.p2 = p2;g2.p3 = p3;
            gameArray.push_back(g2);
        }
    }
}

void print()
{
    for(int u=0; u<gameArray.size(); u++)
    {
        game tmp = gameArray[u];
        cout<<"Res\n";
        cout<<tmp.p1.first<<"  "<<tmp.p1.second<<endl;
        cout<<tmp.p2.first<<"  "<<tmp.p2.second<<endl;
        cout<<tmp.p3.first<<"  "<<tmp.p3.second<<endl<<endl;
    }
}

bool impossible()
{
    int cont;
    for(int x=0; x<gameArray.size(); x++)
    {
        game tmp = gameArray[x];
        cont = 0;
        if(tmp.p1.first > tmp.p1.second)
           cont++;
        if(tmp.p2.first > tmp.p2.second)
           cont++;

        if(cont == 2)
           return true;
    }
return false;
}

int getProbAnswer()
{
    for(int i=1; i<=52; i++)
        if(!myCards.test(i))
           return i;
return -1;
}

int getProbVal(int u)
{
    game tmp = gameArray[u];
    int card = tmp.p3.first;

    for(int i=card; i<=52; i++)
        if(!myCards.test(i))
           return i;
return -1;
}

int getAnswer()
{
    set<int>:: iterator it;
    bool flag;
    int tmp,card;
    for(it=mySet.begin(); it!=mySet.end(); it++)
    {
        tmp = (*it);
        if(tmp == -1)
           return -1;

        flag = true;
        for(int a=0; a<gameArray.size(); a++)
        {
            if(isWW(a))
               continue;
            game g1 = gameArray[a];
            card = g1.p3.first;

            if(tmp < card)
            {
                flag = false;
                break;
            }
        }
        if(flag)
           return tmp;
    }
return -1;
}

int main()
{
int a,b,c,x,y, tmpAnswer, answer;
while(scanf("%d %d %d %d %d", &a, &b, &c, &x, &y))
{
    if(!a && !b  && !c  && !x  && !y)
       break;

    girl.clear(),boy.clear();gameArray.clear();
    girl.push_back(a);girl.push_back(b);girl.push_back(c);
    boy.push_back(x);boy.push_back(y);
    myCards.reset();
    mySet.clear();
    myCards.set(a, 1);myCards.set(b, 1);myCards.set(c, 1);myCards.set(x, 1);myCards.set(y, 1);
    generate();
    //print();
    if(impossible())
       printf("-1\n");
    else
    {
        for(int u=0; u<gameArray.size(); u++)
        {
            if(isWW(u))
            {
                tmpAnswer = getProbAnswer();
                mySet.insert(tmpAnswer);
            }
            else
            {
                tmpAnswer = getProbVal(u);
                mySet.insert(tmpAnswer);
            }
        }
        /*cout<<"Posibles respuestas";
        for(set<int>::iterator it=mySet.begin(); it!=mySet.end(); it++)
            cout<< *it <<" ";
        cout<<endl;*/
        answer = getAnswer();
        printf("%d\n", answer);
    }
}
return 0;
}