Problem G
Sequential Yahtzee

Danny has a hand-held game of Yahtzee that he likes to play (how 90’s!). The object of Yahztee is to score points by placing the result of rolls of $5$ dice into one of $13$ categories. The categories are listed below, along with how you score points for each category:






$1$ point for each $1$


total of all $5$ dice


$2$ points for each $2$


total of all $5$ dice


$3$ points for each $3$

Full House



$4$ points for each $4$

Small Straight



$5$ points for each $5$

Long Straight



$6$ points for each $6$


total of all $5$ dice




A $3$(or $4$)-of-a-Kind is any $5$ dice where at least three (or four) show the same value. A Full House consists of $3$ dice with the same value and the other two with the same value (different from the first value); a Small Straight is four consecutive values on any of four of the dice, a Long Straight is five consecutive values, and a Yahtzee is all five dice showing the same value. Finally the Chance category can be used for any set of five dice. For example, if the five dice showed four $2$’s and one $5$, you would score $8$ points if you put it in the $2$’s category, $5$ points if you put it in the $5$’s category, and $13$ points if you put it in either the $3$-of-Kind, $4$-of-a-Kind or Chance categories. If you put it in any other category you would get $0$ points.

A game consists of $13$ rounds. At the start of each round, you roll all $5$ dice. You can either assign the $5$ dice to any of the unused categories or (more likely) re-roll any number of the dice (even all $5$ if you like). You get to do this one more time and after (at most) the third roll you must place the dice in an unused category. After $13$ rounds, all the categories have been used and you total up the points you got for each category.

In regular Yahtzee you have your choice of which of the scoring categories to use after every round – in fact, the decision on which category to use is one of the challenges of Yahtzee. Danny normally plays this way, but as we said he plays A LOT of Yahtzee, so sometimes he like to switch things up a bit. One of his favorite variations is something he calls sequential yahtzee. In this version, the only category you can use after the first set of rolls is the $1$’s (the first category on his hand-held game); after this, you must use the $2$’s for your second category, and so on (in the order the categories are given in the table above) until you reach the Yahtzee category.

For example, suppose there’s a glitch in Danny’s game and the dice only roll $1$’s (it is a pretty old game). After the first round Danny has (what else) a set of five $1$’s. In regular Yahtzee he could score $50$ points for a Yahtzee, but in sequential yahtzee he must put it in the $1$’s category and scores $5$ points. After he rolls five $1$’s again, he must put it in the $2$’s category and scores $0$. He scores $0$ for the next $4$ rounds, putting his five $1$’s in the $3$’s, $4$’s, $5$’s and $6$’s category. He gets $5$ points for each of the next two rounds, placing his five $1$’s first in the $3$-of-a-Kind and then in the $4$-Of-A-Kind. He gets nothing in the next two rounds, scores $5$ points for the Chance category and then FINALLY gets $50$ points for a Yahtzee in the $13$th round. All together he scores $70$ points

Danny keeps track of all the dice rolls in the game and often wonders if he could have done better than he did in a game of sequential yahtzee, assuming that the same overall sequence of dice appears regardless of the way he chooses to re-roll dice in any given round. Another example should make things clear. Suppose the sequence of dice is that of the second sample input. If Danny assigns the first five dice to the “$1$’s” category he will get a score of $4$, but if he re-rolls the $3$, obtaining another $1$, his score will improve to $5$. In round $2$, if he assigns the next $5$ dice his score for the “$2$’s” category will be $4$, but if he re-rolls the $4$, $5$, and $6$ (obtaining $1$, $2$, and $3$), and then re-rolls these three new dice again, he obtains three more $2$s for an improved score of $10$ in the second category. At the end of the game, the sequence of five $1$s yields a yahtzee; the final $4$ is not used. The best score obtainable for this sequence of dice is $340$.

Your job is simple: given a sequence of consecutive dice rolls, what’s the maximum score possible in a game of sequential yahtzee? Well, maybe it’s just the description of the problem that’s simple.


Input starts with a line containing an integer $n$ ($65 \leq n \leq 195$) indicating the number of dice rolls. Following this, on one or more lines, are the $n$ dice rolls, all values between $1$ and $6$ inclusive.


Display the maximum possible sequential yahtzee score using the given dice rolls, filling in all $13$ categories. Not all the dice rolls need to be used, but those that are must be consecutive starting with the first roll.

Sample Input 1 Sample Output 1
1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1

Sample Input 2 Sample Output 2
3 1 1 1 1 1 4 2 5 2 6 1 3 5 2 2 2
3 3 3 3 3 4 4 4 4 4 5 5 5 5 5 6 6 6 6 6
6 6 6 6 6 6 6 6 6 6 1 1 1 2 2 1 2 3 4 5
1 2 3 4 5 1 1 6 1 6 6 6 6 1 1 1 1 1 4

Please log in to submit a solution to this problem

Log in