403203: GYM101064 J King of Tokyo

King of Tokyo is a board game in which each player is a monster trying to destroy Tokyo, or its enemies. In his or her turn, the player rolls 6 dice, and can reroll some of those dices to get better results. The dice are used to attack, gain energy, cure health or score points. King of Tokyo is very famous in the USA, and one day you were relaxing in the five-star hotel for the ICPC World Finals 2017 when the hotel staff challenged you and many other contestants to a game of King of Tokyo. You know they are very very good in this game, so you decide to use your programming abilities to help you. Your task is to implement a simple King of Tokyo player that tries to score the maximum amount of points, ignoring energy and damage to enemies.

The 6 dice you roll are alike, each with 6 distinct faces: 1, 2, 3, A, V, E. The faces A, V and E are not used for points and their effects should be ignored in this problem. The points awarded for rolling the 6 dice are calculated in the following way: for each 3 dice with the same face up (of the types 1, 2, or 3), you are awarded points equal to the number on the face up; for each additional die with that face up you get 1 extra point.

For example, if we represent a rolling of the dice by the values on their face up, then 22231A scores 2 points, 2222VV scores 3 points, 112233 scores 0 points, 33333E and 222333 scores 5 points.

One turn is done in the following way. Let K be the number of rerolls you have.

1. Roll the 6 dice
2. Choose a subset of the 6 dice, and reroll the chosen dice. You can repeat this procedure up to K times.

Given an initial configuration of rolled dice obtained by the the first step, and K, determine the expected number of points you can score this turn if you play optimally, and print the first subset of dice (possibly empty) that should be rerolled to get that expected value. To indicate that a certain die belongs to that subset, use the value in the face up.

In the first line, a single integer T, the number of test cases.

The next T lines begin with an integer K and are followed by a string of 6 characters representing the first roll.

Limits

• 1 ≤ T ≤ 500
• 0 ≤ K ≤ 4
• Each character in the string is one in 123AVE

For each test case, print 2 lines.

The first line should have a number, the expected number of points, if you play optimally. The error should not exceed 10^- 4.

The second line should contain up to 6 characters, the first subset of dice you should reroll to get the optimal result, print the values in the face up of those dice in any order. If the optimal play is not rerolling any dice, or if K = 0, print "-". This answer will be considered correct if, by rerolling these dice, the expected number of points you get if playing optimally after this play does not differ from the correct answer by more than 10^- 4.

3
0 112223
1 321321
4 EA2322

2.0000000000
-
1.7523148148
1122
3.5980742688
3EA