Deck of Cards
Time Limit: 2 Seconds
Memory Limit: 65536 KB
21-point is a small game played with cards. Its aim is to accumulate the points on the cards so as to get 21 points. This game also appears on some cell phones.
To simplify the problem, let's have some assumptions.
The game is played with a standard deck of 54 cards, namely A, 2, 3, 4, 5, 6 , 7, 8, 9, 10 (denoted as T), J, Q, K, Joker (denoted as F. However, the number of cards of a game may be up to 100.
In this game, an Ace values 1 point, the face cards (K, Q and J) value 10 points each and the remaining cards are valued by their numerical values. The joker is a bit different, which will be mentioned later.
There are 3 slots on the table, namely 1x, 2x, 3x.
A slot is available if the total points of the cards on that slot do not exceed 21.
The cards on a slot will be taken away as soon as the total points of cards are 21.
You are asked to put the cards on the table in the given order.
The cards can be put on a slot only if the slot is available.
A joker values as large as possible. In another word, a slot's total value becomes 21 immediately after placing a joker into it.
- The game ends if no slot is available or the cards are all used.
You can get 50 dollars if you succeed putting one card onto the table, and 100 dollars multiplied by the number on the slot if you succeed eliminating cards on a slot.
Now your task is to calculate the maximum money you can get.
The input contains multiple test cases!
The first line contains an integer N, denoting the number of cards of this game. The next line contains N characters separated by a single space, denoting the cards.
A line with N = 0 signals the end of the input, which should not be processed.
Output the maximum money you can get in one line for each test case.
J J J J J J J J J J
F T J Q K T J Q K T J
In the first case, you can put the joker onto the 3x slot and get 21 points. The total money you get is 50 + 100 * 3 = 350 dollars.
In the second case, you can only put 3 J's onto each slot and no slot is available then. The total money you get is 50 * 9 = 450 dollars.
The third case is a combination of the first two. Note that the first joker can't be counted as 1 point.
Author: GUAN, Yao
Source: Zhejiang Provincial Programming Contest 2007