영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
Problem
Several different groups are invited to sit in the front row during the closing ceremony of this year's IOI (International Olympiad in Informatics). Each person has been assigned a seat. However, the organizers of IOI didn't realize that the groups prefer to sit together, so they distributed the seats somewhat randomly. Therefore, the people decide to take matters into their own hands: by swapping seats with each other, they try to maximize the number of pairs of people from the same group sitting next to each other. The organizers would get angry if the seat swapping becomes too chaotic, so they decide that each person can switch seats at most once, and only with a person who is at most K seats away.
What is the maximum number of pairs of people from the same group sitting next to each other that can be achieved?
Input
The first line contains a string of length N (1 ≤ N ≤ 30), describing the original row. Each letter in the string describes which group the person at the corresponding position belongs to and is either A, B, C, or D. The second line contains an integer K, the maximum distance people are allowed to move (1 ≤ K ≤ 2).
Output
The program should output an integer: the maximum number of pairs of people from the same group sitting next to each other that can be achieved through valid seat swaps.
Scoring
Your solution will be tested on a set of test case groups. To get points for a group, you must pass all test cases in that group.
| Group | Points | Constraints |
|---|---|---|
| 1 | 20 | K=1, N ≤ 15, and there are 3 groups (A, B, C). |
| 2 | 40 | K=2 and there are 2 groups (A, B). |
| 3 | 40 | K=2 and there are 4 groups (A, B, C, D). |
Explanation of Example 1
In sample 1, the following arrangement can be achieved: A B B A A A, by swapping the first and second person, and swapping the third and fourth person.
Explanation of Example 2
In sample 2, the following arrangement can be achieved: A A C C B B B A, by swapping the second and third person, and swapping the fourth and sixth person.
예제
예제 1
BAABAA 1
3
예제 2
ACABBCBA 2
4