This page is still under construction.

Parts of this page are still being built. What you see may change.

Orko

Time limit1sMemory limit128 MB

Summary
Given ten cards for player A and the rest for B, compute how many of the ten rounds A wins when both play optimally, with A leading first.
Level

Hard8 of 10

Topics
Game theory, Backtracking, Dynamic programming, Bit manipulation
Solved
No attempts yet

Problem

Orko is a two-player card game. Each card has a colour (Red, Yellow, Green, or Black) and a value (1, 2, 3, 4, or 5). The deck contains twenty cards, one for each distinct combination of colour and value.

Each player is dealt ten of the twenty cards. The game is played over ten rounds, and the objective is to win as many rounds as possible. In each round the player who holds the lead plays one of his cards. The other player must play a card of the same colour if he has one; otherwise he may play any of his cards.

The player with the lead wins the round in either of these cases:

  • the other player has no card of the same colour, or
  • the lead's card has a higher value than the other player's card.

Otherwise the other player wins the round.

The lead for the first round is chosen arbitrarily; the lead for each subsequent round goes to the winner of the previous round.

Assuming that each player follows the strategy that maximizes the number of rounds he wins, determine how many rounds each player wins.

Input

The input contains several test cases. Each test case consists of one line describing the cards dealt to one of the players, Player AA. Each card is given by a letter (R, Y, G, B) denoting its colour, followed by a digit denoting its value (1, 2, 3, 4, 5). The other player, Player BB, receives the remaining cards of the deck.

A line containing ten stars separated by spaces

* * * * * * * * * *

follows the last test case.

Output

For each test case, output on a single line an integer between 00 and 1010: the number of rounds won by Player AA. Assume that Player AA has the lead for the first round.

Examples1

  1. Example 1

    Input
    G1 G3 B2 R2 Y1 R3 R5 Y2 Y3 G5
    * * * * * * * * * *
    
    Expected output
    3