Fish Slapping in Henceforthshire P64266


Statement
 

pdf   zip

thehtml

As it is traditional every June, the otherwise peaceful of Saint Humbertus of Henceforthshire is bustling with the participants of the yearly GHOTI (Great Henceforthshire Obsequious Theological Ichtyotrauma) contest, the oldest and most renowned of its kind. The winner will be granted a replica of the Golden Scale of Saint Humbertus, the most famous relic from the namesake Saint of the town, who was martyrized in the late Roman Empire by being dropped on a barrel full of anchovies who devoured his flesh.

In GHOTI, contestants meet in one-to-one combats wearing red and blue salacots, and dance following carefully executed moves to slap their opponents. They prepare their fish arsenal in advance and, after proudly exhibiting it to each other, they use one of them in each round, consisting of a single move. The perfection of each move depends on one of the features of the chosen fish (weight, length, flexibility, …).

In each round, the winner of the latest round (the red player, for the first round) is the one to choose a feature. Then he picks, among his still remaining fish, the fish that he will employ for a move with the chosen feature. Afterwards, his rival will chose his fish for his response with the same feature. Finally, they both will slap each other. The player using the fish with the highest value on the relevant feature will win the round. If both values are equal, it is a draw. In that case, the choice will remain on the same player. Both fish will get destroyed after the slapping. When all fish have been used, the dancer who won more rounds is the winner of the combat.

Given the features’ values of the fish of the two players, can you identify who will be the overall winner, and by what margin, assuming perfect play? Note, each player tries to maximize the difference between his wins and his opponent’s wins.

Input

Input consists of several combats. Each one starts with the number of fish 1 ≤ n ≤ 7 for each participant and the number of features 1 ≤ f ≤ 15 that will be considered. After that come n lines for the red opponent and n lines for the blue one. Each line contains f integers, providing the value of the fish for each feature 0 ≤ vf ≤ 1000.

Output

For each combat, print its result under optimal play: ‘D’ if it will be a draw, ‘R’ x if the red player will win by x rounds, or ‘B’ x if the blue player will win by x rounds.

Consider the first combat of the Sample input. There, the red player has fish with values [8, 1, 1] and [3, 3, 3], and the blue player has fish with values [6, 2, 2] and [4, 4, 4]. The best choice for the red player is to use the first fish with the first feature (with value 8). Then, the best choice for the blue player is to use the first fish (with value 6) for the first round, which he will lose no matter what. This way, he will surely win the second round. Therefore, the result under optimal play is a draw.

Public test cases

  • Input

    2 3
8 1 1
3 3 3
6 2 2
4 4 4
1 1
5
5
1 2
10 10
5 5
1 2
5 5
10 10
2 3
10 5 5
5 10 10
8 8 8
7 7 7
2 3
10 5 5
5 10 10
8 8 8
12 12 12

    Output

    D
D
R 1
B 1
R 2
B 2
    • Information
    Author
    Edgar Gonzalez
    Language
    English
    Official solutions
    C++
    User solutions
    C++