CCC '10 S1 - Computer Purchase
Submit solution
Points:
1
Time limit:
2.0s
Memory limit:
256M
Problem type
Allowed languages
C++, Python
Canadian Computing Competition: 2021 Stage 1, Junior #4
Valentina wants books on a shelf to be arranged in a particular way. Every time she sees a shelf of books, she rearranges the books so that all the large books appear on the left, followed by all the medium-sized books, and then all the small books on the right. She does this by repeatedly choosing any two books and exchanging their locations. Exchanging the locations of two books is called a swap.
Help Valentina determine the fewest number of swaps needed to arrange a shelf of books as she wishes.
Input Specification
The input will consist of exactly one line containing at least one character. The following table shows how the available \(15\) marks are distributed.
| Subtask | Number of books | Book types |
|---|---|---|
| \(7\) marks | at most \(1\,000\) characters | each character will be L or S |
| \(2\) marks | at most \(500\,000\) characters | each character will be L or S |
| \(4\) marks | at most \(1\,000\) characters | each character will be L , M or S |
| \(2\) marks | at most \(500\,000\) characters | each character will be L , M or S |
Comments