Many thanks to Clive Fraser for presenting us this fine puzzle at the
first day of the New Year 2024!
A scout troop runs a series of Proficiency Courses for the scouts. There are 9 separate courses and these have
to be completed in sequence. A scout has to achieve a satisfactory standard on course 1 before they can
progress to course 2. A similar arrangement applies to progression from course 2 to course 3 and so on up
to course 9. When a scout reaches the required standard on a course they are given a badge to mark this
achievement. The standard badge for the course is referred to as a Merit Award. However, scouts are
encouraged to achieve more than the minimum standard required to pass a course. Scouts achieving significantly
higher than the minimum pass standard are given Bronze, Silver or Gold Awards depending on their
performance. So Bronze is a higher achievement than Merit, Silver is higher than Bronze and Gold is for the
highest standard. Scouts achieving one of the special awards are presented with a badge which is trimmed in
either Bronze, Silver or Gold.
Not all of the scouts in the troop have successfully completed the level 1 course. Of those that have, the
number of courses completed varies from 1 to 9. Consider four of these scouts. Scout 1 has completed the
first 3 courses, all at Silver standard (SSS). Scout 2 has completed just the first course, gaining
Bronze (B). Scout 3 has completed the first 2 courses, gaining Gold for the first and Bronze for the
second (GB). Scout 4 has completed the first 4 courses, gaining Merit Awards on the first 2 and then
Gold followed by Bronze for the next 2 (MMGB).
If we choose a group of scouts it is interesting to note the highest award achieved by any scout in the group
for each possible Proficiency Level. Clearly it is only relevant to consider Proficiency Levels which have been
attained by at least one scout in the chosen group. We can represent the best achievements of the group of
scouts using letter strings similar to those used for the individual scouts above. Since there are only 9
different levels none of these letter strings can ever contain more than 9 letters. Also, since there are
only 4 different grades of award, the letter strings will contain only the characters M, B, S and G.
As an example, consider a very small scout troop in which only the 4 scouts already described have achieved
the required standard for at least one of the Proficiency Levels. If we select a sub-group of these scouts
there are 15 possible ways of choosing the sub-group. Note that this group can contain any number of scouts
from 1 to the maximum number of scouts (4 in this case). The following table takes each of the 15 groups
in turn and gives a letter string to represent the best achievements from the group as a whole. In this
example none of the scouts has more than 4 badges so none of the letter strings for the best group
achievement can be longer than 4 characters.
Scout 1 SSS
Scout 2 B
Scout 3 GB
Scout 4 MMGB
Scouts 1 and 2 SSS
Scouts 1 and 3 GSS
Scouts 1 and 4 SSGB
Scouts 2 and 3 GB
Scouts 2 and 4 BMGB
Scouts 3 and 4 GBGB
Scouts 1, 2 and 3 GSS
Scouts 1, 2 and 4 SSGB
Scouts 1, 3 and 4 GSGB
Scouts 2, 3 and 4 GBGB
Scouts 1, 2, 3 and 4 GSGB
The first 4 groups contain single scouts so the best group achievement is the same as that of the individual
scout. In the group containing all 4 scouts the best achievement at Level 1 is Gold (scout 3), the best
achievement at Level 2 is Silver (scout 1), the best achievement at Level 3 is Gold (scout 4) and the
best achievement at Level 4 is Bronze (scout 4).
If we examine the 15 best group achievements in the table above, we can see that 5 of them do not have any
Merit or Silver Awards within them. These 5 best group achievements consist only of Gold and Bronze Awards.
The 5 groups in this category are shown below:
Scout 2 B
Scout 3 GB
Scouts 2 and 3 GB
Scouts 3 and 4 GBGB
Scouts 2, 3 and 4 GBGB
The actual scout troop typically has between 55 and 62 scouts who have achieved at least one of the
Proficiency Levels. The number of possible sub-groups is now very much larger than that in the example above.
You need to consider all possible sub-groups of these scouts and to count the number of groups where the best
group achievement is made up entirely of Gold and Bronze Awards (i.e. no Silver or Merit Awards).
Input and output:
The first line of the problem will be a single integer N denoting the number of scouts who have at least one
Proficiency Badge. N lines then follow. Each line will contain a character string of between 1 and 9
letters, giving the set of badges achieved by the corresponding scout. Calculate the number of groups of
scouts where the best group achievement is made up entirely from Gold and Bronze Awards. This number is the
required answer.
Example:
input:
4
SSS
B
GB
MMGB
answer:
5