UVa Online Judge 12247 Jollo

general
1

Here’s the question link : https://uva.onlinejudge.org/external/122/12247.pdf

I was trying this problem on the UVa Online Judge. I had a look on various solutions but couldn’t get the idea involved.

Please Help.

Thank You.

2

Prince has 2 cards, X & Y

Princess has 3 cards, A, B & C

They play a best-out-of-three game of showing higher card (winner needs to win 2 games at least)

You need to smallest card that you can give to prince so he wins.

You can assume that prince plays as bad as he can, and princess plays optimally.

That’s our problem.

The only tricky part here is to know what does prince playing “as bad as possible means” and princess playing “optimally” means

It can be stated like this:

  • Prince will always put forward his best card
  • If princess has no card higher than prince’s current best, she will use her smallest card

You can have a brute force approach like this where he just runs a loop from 0 to 52, and chooses a card (that is not one of the 5 given to us) and checks all possibilities and see if prince looses at any 1 of them.

Note: There are 6 possibility ( A can be mapped in 3 ways, B in 2 ways, C in 1 way so 3 x 2 x 1 = 6 ways) and since there are only 52 cards, worst case complexity is O(#test_case * 52)

You can also use this approach, here we have:

  • Both of his card are higher than all of hers, print smallest card that is available to win
  • 1 of his card is greater than all of hers, find a card which is higher than her highest
  • his two cards are only smaller than 1 of her card, find a card higher than her second highest
  • If none of the above, answer is -1.

    Note: if in 2nd case her highest card is 52, print -1
2 Likes
3

Thank You.

4

Your welcome mate :slight_smile: