When selecting files in an application dialog, Vasya noted that he can get the same selection in different
ways.
A simple mouse click selects a single file (the
existing selection is discarded). A shift-click is used to select a range of
files from the file clicked last time to the current file (the existing
selection is discarded). Finally, a control-click is used to invert the
selection state of a single file.
Consider a sequence of actions. First we select
file #5 simply by clicking it. Then, shift-clicking file #10 we get the
following selection: #5, #6, #7, #8, #9, #10. If after
that we control-click files #7 and #3 then we will have files #3, #5, #6, #8,
#9, and #10 selected. Shift-clicking file #1 we select files #1, #2, and #3
(last time we clicked file #3, and the previous selection is gone).
Vasya is wondering, what the minimum number of
clicks will be, to make a certain selection from the list of files.
Write a program to determine the optimal way of
making the required selection. If there are several minimal solutions, any of
them is considered correct.
Example. Suppose we are to select files #2,
#5, #6, #8, #9 from a list of 10 files. A possible optimal solution will
include the following clicks: 5, Shift+9, Ctrl+2, Ctrl+7.
Limitations
1 <= n
<= 105.
Input
The first line contains an integer n, the number of files in the list. The following line contains n
characters defining the required selection. If i-th file is to be selected then there is an
asterisk (“*”) in position i, and a dot
(“.”) otherwise.
Output
The first line of the output file must contain a single integer k – the minimum number of clicks necessary to
make the given selection. The following k lines must define the
way to make such a selection. Each line should contain the number of file to be
clicked on the corresponding step, and a prefix “Ctrl+” or “Shift+” (without
quotation marks) where necessary.
Example
Input
|
Output
|
|
10
.*..**.**.
|
4
5
Shift+9
Ctrl+2
Ctrl+7
|
Input
|
Output
|
|
10
.*..**..**
|
5
2
Ctrl+5
Ctrl+6
Ctrl+9
Ctrl+10
|
All Rybinsk-2012 problems (in PDF)
