UVa12247 — Jollo

PROBLEM CODE 12247-Jollo

Jollo is a simple card game which the children from Logonia love to play. It is played between two players with a normal deck of 52 cards. In the game, cards are ordered according to their rank and suit, forming a sequence of 52 distinct values.
The game is composed of three rounds, played in a best-of-three series (a player must win two rounds to win the game). At the beginning of the game the deck is shuffled and each player is given a hand of three cards. In each round the players show one card to each other and the player with the highest card wins the round. The cards shown in a round are discarded (i.e., they cannot be shown again).
The King’s son loves to play the game. But he is not very smart, losing frequently to his little sister. And when he loses, he cries so loud no one can stand it. The servant who deals the cards to the Prince and his sister is afraid he will be sent to prison if the Prince continues to lose. The servant is allowed to see every card he deals, and after dealing five cards (three to the Princess and two to the Prince) he wants to know which is the lowest card he should deal to the Prince so that there is no chance he will lose the game, no matter how badly he plays.

Input

Each test case is given in a single line that contains five distinct integers A, B, C, X and Y , describing the cards dealt to the players. The first three cards are given to the Princess (1 ≤ A, B, C ≤ 52) and the last two cards are given to the Prince (1 ≤ X, Y ≤ 52). The last test case is followed by a line containing five zeros.

Output

For each test case output a single line. If there exists a card that will make the Prince win the game no matter how badly he plays, you must print the lowest such a card. Otherwise, print ‘-1’.

Sample Input

28 51 29 50 52
50 26 19 10 27
10 20 30 24 26
46 48 49 47 50
0 0 0 0 0

Sample Output
30
-1
21
51

SOLUTION

This is an easy kind of problem can be solved easily by analyzing some test case.

Lets assume that a,b,c i.e. cards of Princess will fight with d,e i.e. Prince two cards.
So all possible combination will be
a,b <-> d,e
a,c <-> d,e
b,c <-> d,e
b,a <-> d,e
c,a <-> d,e
c,b <-> d,e

Now by all this cases we will decide the third card of Prince i.e f

Now, the main question is how we decide the value of f.

Let’s take a general case a,b,c will fight with d,e,f respectively.

Case 1: if a>d && b>e then no value of f can make Price win thus f=-1
Case 2: if a>d && b<e then we need a card of value c+1 to make Price win thus f=c+1
Case 3: if a<d && b<e then any value of f can make Price win thus f=1

Now we will make a function that handle all the above three cases and we call this function for all the combination of a,b,c and store the value of f in an array of size 6.

Now if any value is -1 means at some combination of a,b,c Prince will loose thus answer is -1
else take the maximum value of the all six answers.

Now one problem will arise that is if the answer is already a card taken.It means Princess and Prince have same no. cards.

So for this we will manage a hash table of size 52 where we will check for the availability of cards. if card exceed 52 then answer -1 otherwise the next card to maximum of the array of answers.

CODE in C++

#include<iostream>
#include<algorithm>
using namespace std;
int f(int a,int b,int c,int d, int e)
{
     if(a>d && b>e)
     {
          if(b>e) return -1;
          else return (c+1);
     }
     else
     {
     if(b>e) return (c+1);
     else return 1;
     }
}
int main()
{
     while(1)
     {
          int ar[52]= {0}; //array to check the cards
          int a,b,c,d,e;
          cin>>a>>b>>c>>d>>e;
          if(a==0 && b==0 &&c==0 &&d==0 &&e==0) break;
          ar[a-1]=1; ar[b-1]=1; ar[c-1]=1; ar[d-1]=1; ar[e-1]=1; //updating the hash table
          int x[6];
          //storing the value of all combinations
          x[0]=f(a,b,c,d,e);
          x[1]=f(a,c,b,d,e);
          x[2]=f(b,a,c,d,e);
          x[3]=f(b,c,a,d,e);
          x[4]=f(c,a,b,d,e);
          x[5]=f(c,b,a,d,e);
          //sorting the array
          sort(x,x+6);
          // if any value is -1 then answer is -1
          if(x[0]==-1)
               cout<<-1<<endl;
          
          else
          {
               int y=x[5];
               //if the maximum value is the card already posses by Prince or Princes
               //searching for the next available card.
               if(ar[y-1]==1) {
                    while(ar[y]==1) y++;
                    if(y<52) //if less than 52 print the card value
                         cout<<y+1<<endl;
                    else
                         cout<<-1<<endl; //else print -1
               }
               else
                    cout<<y<<endl; // if card is availbale then print
          }
     }
}