시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 6 | 6 | 6 | 100.000% |
Kindergarten graduates participate in English alphabet Olympiad. The main task is to pronounce English letters in the alphabet order without repeats.
Children can start to pronounce letters at any moment, even when the other participant has not finished yet. At the same time, the teacher writes all pronounced letters into one common string. The task is not easy for children and sometimes they make mistakes such as skipping letters. For each participant the number of mistakes they make is the number of skipped letters. The total number of mistakes for all children doesn’t exceed $k$. If at some point participant is tired to pronounce letters, (s)he stops, and all the remaining letters are not counted as mistakes.
You know $k$ and the final string, your task is to find the minimum possible number of participants, or say that data is not correct.
The first line contains a single integer $k$ ($0 \le k \le 1000$) — the maximum number of skipped letters.
The second line contains teacher’s string $s$ — all pronounced letters. $s$ consists of capital English letters and the length of the string does not exceed $1000$.
Print single word “Impossible
” in a single line if the data is incorrect (it isn’t possible to get this line with missing only $k$ letters), otherwise print single integer — the minimum number of participants in the Olympiad.
번호 | 배점 | 제한 |
---|---|---|
1 | 16 | $k = 0$ |
2 | 16 | All letters in $s$ are in alphabet order |
3 | 11 | $s_i$ equals ‘ |
4 | 11 | It’s possible to get a string by skipping no more than $k$ letters, and the minimum number of participants doesn’t exceed $3$ |
5 | 46 | No additional constraints |
5 ABDBCBADB
4
100 INNOPOLIS
4
0 ABB
Impossible
In the first example, the rows separately for each participant might look like this:
ABD
— 1 mistake;BC
— 1 mistake;BD
— 2 mistakes;AB
— 0 mistakes;In the second example:
INO
— 12 mistakes;NOP
— 13 mistakes;LS
— 17 mistakes;I
— 8 mistakes;