ZAGREB – CROATIA
AUGUST 15 – 22

COMPETITION DAY 2 – MINERS

MINERS
There are two coal mines, each employing a group of miners. Mining coal is hard work, so miners need food to
keep at it. Every time a shipment of food arrives at their mine, the miners produce some amount of coal. There
are three types of food shipments: meat shipments, fish shipments and bread shipments.
Miners like variety in their diet and they will be more productive if their food supply is kept varied. More
precisely, every time a new shipment arrives to their mine, they will consider the new shipment and the
previous two shipments (or fewer if there haven't been that many) and then:
•
If all shipments were of the same type, they will produce one unit of coal.
•
If there were two different types of food among the shipments, they will produce two units of coal.
•
If there were three different types of food, they will produce three units of coal.
We know in advance the types of food shipments and the order in which they will be sent. It is possible to
influence the amount of coal that is produced by determining which shipment should go to which mine.
Shipments cannot be divided; each shipment must be sent to one mine or the other in its entirety.
The two mines don't necessarily have to receive the same number of shipments (in fact, it is permitted to send all
shipments to one mine).
TASK
Your program will be given the types of food shipments, in the order in which they are to be sent. Write a
program that finds the largest total amount of coal that can be produced (in both mines) by deciding which
shipments should be sent to mine 1 and which shipments should be sent to mine 2.

EXAMPLES

The first line of input contains an integer N (1 ≤ N ≤ 100 000), the number of food shipments.
The second line contains a string consisting of N characters, the types of shipments in the order in which they
are to be distributed. Each character will be one of the uppercase letters 'M' (for meat), 'F' (for fish) or 'B' (for
bread).

6
MBMFFB

16
MMBMBBBBMMMMMBMB

Output a single integer, the largest total amount of coal that can be produced.
GRADING
In test cases worth a total of 45 points, the number of shipments N will be at most 20.
DETAILED FEEDBACK WHEN SUBMITTING
During the contest, you may select up to 10 submissions for this task to be evaluated (as soon as possible) on
part of the official test data. After the evaluation is done, a summary of the results will be available on the contest
system.

ZAGREB – CROATIA
AUGUST 15 – 22

COMPETITION DAY 2 – MINERS

12

29

In the left sample, by distributing the shipments in this order: mine 1, mine 1, mine 2, mine 2, mine 1, mine 2,
the shipments will result in 1, 2, 1, 2, 3 and 3 units of coal produced in that order, for a total of 12 units. There
are other ways to achieve this largest amount.

생성자가 기록되지 않았습니다.

출처 IOI 2007