루미 알고리즘

#1597실버Christian's Piano

PO 2024 학교 예선코딩출제 Joshua Andersson영어 원문이 문제가 어렵다면 — 배우는 순서 보기

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

Problem

Christian wants to learn to play the piano but can only manage to play with his index finger right now. Currently, he is practicing hard to learn a piece. A piece is described by a sequence of keys to be pressed in order. For example, the piece abdaa indicates that he should press the keys a, b, d, a, a in order.

However, you notice that he struggles to move his finger quickly between the keys. Curiously, it always takes him exactly one second to move his finger one key to the side but zero seconds to press a key.

To help him, you plan to rearrange the order of the piano keys so that the total time it takes to play the piece is minimized.

For example, if the piece he is trying to learn is abdaa and the piano has the order abd … (the rest of the piano is not shown as it does not affect the answer), it will take a total of 4 seconds to play the piece. The distances when he plays the piece are as follows:

  • a to b takes one second.
  • b to d takes one second.
  • d to a takes two seconds.
  • a to a takes zero seconds.

This means that it takes a total of four seconds to play the piece abdaa on a piano with the order abd ….

Write a program that reads a piece and outputs the total time it takes for Christian to play the piece on the piano with the best possible key order.

Input

The first and only line of input contains a string S (1 ≤ |S| ≤ 200), the piece that Christian wants to learn. The piece consists of characters from a-z and contains at most 15 distinct characters.

Output

Print an integer: the number of seconds it takes for Christian to play the piece on a piano with the best possible key order.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

GroupPointsConstraints
120The piece contains at most 8 distinct characters.
280No additional constraints.

Explanation of sample 2

One possible optimal order of the piano keys is adbc.

예제

예제 1

입력
abdaa
출력
4

예제 2

입력
abdaadbc
출력
7

출처 표기

출처: Programmeringsolympiaden 2024년 학교 예선 · 원문 페이지 · 이용 조건 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). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.