루미 알고리즘

#1422플래티넘Pekgälsvalsen

PO 2017 훈련 캠프코딩출제 Johan Sannemo스웨덴어 원문이 문제가 어렵다면 — 배우는 순서 보기

스웨덴어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

Doris håller på att skriva ett långt email till sin familj. Texten består av K olika bokstäver, och är N bokstäver lång. Doris har inte så bra minne, så hon kommer inte ihåg var bokstäverna på tangentbordet sitter. Istället använder hon en variant av den så kallade pekgälsvalsen när hon skriver.

Doris skriver sin text i K omgångar, en omgång för var och en av de olika bokstäverna som utgör texten. I början skriver Doris ned alla förekomster av en av bokstäverna med sin ena gäl. Därefter går hon tillbaka till början av texten, och väljer ut en ny bokstav. Sedan skriver hon in alla förekomster av denna bokstav, genom att använda högerpilstangenten med hennes andra gäl. Efter detta går hon återigen tillbaka till början av texten, nu för att skriva ned den tredje bokstaven, och så vidare. Hon upprepar detta tills hon skrivit hela texten. På så sätt behöver hon bara minnas var tangenten för en enda bokstav finns i taget.

Beroende på vilken ordning hon väljer att skriva in bokstäverna i kan detta ta olika lång tid. Om hon ska skriva in texten aabbac så kräver ordningen a, b, c att hon trycker på högerpilstangenten 7 gånger. Först skriver hon in aaa utan att använda högerpil. Sedan går hon tillbaka till texten, använder högerpil två gånger och skriver in bb. Till slut går hon tillbaka till början, går höger fem gånger och skriver in c.

Om hon istället valde ordningen b, a, c skulle hon först skrivit bb. Sedan skulle hon använt två högertryck för att skriva aabba, och till slut fem ytterligare gånger för att skriva aabbac.

Ordningen c, b, a kräver endast att hon trycker högerpil två gånger, vilket är optimalt.

Indata

Den första raden innehåller de positiva heltalen N och K. Nästa rad innehåller en sträng med N tecken, valda bland de K första små bokstäverna i alfabetet (a, b, c, …). Det är dessutom garanterat att strängen innehåller exakt K olika tecken.

Utdata

Skriv ut ett enda tal – antalet gånger Doris måste trycka högerpil för att skriva texten.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

GruppPoängvärdeGränser
18K = 2, N ≤ 100
210K ≤ 7, N ≤ 100
328K ≤ 10, N ≤ 1000
419K ≤ 10, N ≤ 10^6
535K ≤ 18, N ≤ 10^6

예제

예제 1

입력
6 3
aabbac
출력
2

예제 2

입력
10 2
aaabaaabbb
출력
1

출처 표기

출처: Programmeringsolympiaden 2017년 훈련 캠프 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.