Cued In
InterviewTime limit1sMemory limit512 MB
Given the balls left on a snooker table, compute the maximum points a player can score in one run following the red-colour alternation rules.
- Level
Medium6 of 10
- Topics
- Greedy, Implementation, Math, Simulation
- Solved
- No attempts yet
Problem
Snooker is a cue sport played by two players who take turns potting balls on a rectangular table. Each colour is worth a fixed number of points.
A turn is a run of pots. The run ends as soon as no ball the rules allow is left on the table. The rules for a single pot are:
- If the ball potted just before was red, the next ball must be a ball of another colour.
- Otherwise, if at least one red is still on the table, the next ball must be red.
- Otherwise the player may pot any ball left on the table.
The first pot of the run follows the same rules, with no ball potted before it.
A potted red never comes back to the table. A coloured ball comes back to the table right away when it was potted just after a red, and the colour potted just after the last red comes back in the same way. Every other potted ball stays off the table.
An experienced player needs one glance across the table to work out how much the remaining balls are worth. For a beginner it is harder. Given the balls on the table, print the largest score the player can make in one turn. Each pot scores the value of the ball potted.
Input
The first line has one integer N (1 ≤ N ≤ 21), the number of balls left on the table.
Each of the next N lines has the colour of one ball, written as red, yellow, green, brown, blue, pink or black.
The balls come in no particular order, and each of yellow, green, brown, blue, pink and black appears at most once.
Output
Print the largest score the player can make in one turn.