#include #define pb push_back #define f first #define s second #define pii pair #define mp make_pair using namespace std; const int MAX = 26; int distances[MAX][MAX]; int dp[101][MAX][MAX]; string keyboard[] = {"QWERTYUIOP", "ASDFGHJKL ", "ZXCVBNM "}; void compute_distances() { for (int letter = 0; letter < 26; letter++) { for (int next_letter = letter + 1; next_letter < 26; next_letter++) { pii position_first, position_second; for (int i = 0; i < 3; i++) { for (int j = 0; j < 10; j++) { if (keyboard[i][j] - 'A' == letter) { position_first = mp(i, j); } if (keyboard[i][j] - 'A' == next_letter) { position_second = mp(i, j); } } } int manhattan_distance = abs(position_second.f - position_first.f) + abs(position_second.s - position_first.s); distances[letter][next_letter] = distances[next_letter][letter] = manhattan_distance; } } } int main() { compute_distances(); string word; cin >> word; for (int letter = 0; letter < 101; letter++) { for (int i = 0; i < 26; i++) { for (int j = 0; j < 26; j++) { dp[letter][i][j] = (1LL << 29); } } } dp[0][('f' - 'a')][('j' - 'a')] = 0; word = " " + word; for (unsigned i = 1; i < word.size(); i++) { int next_letter = word[i] - 'A'; for (int j = 0; j < 26; j++) { for (int k = 0; k < 26; k++) { if(dp[i - 1][j][k] != (1LL << 29)) { dp[i][next_letter][k] = min(dp[i][next_letter][k], dp[i - 1][j][k] + distances[next_letter][j]); dp[i][j][next_letter] = min(dp[i][j][next_letter], dp[i - 1][j][k] + distances[k][next_letter]); } dp[i][next_letter][k] = min(dp[i - 1][j][k] + distances[next_letter][j], dp[i][next_letter][k]); } } } int n = word.size() - 1, last_letter = word[n] - 'A', sol = (1LL << 30); for (int k = 0; k < 26; k++) { sol = min(sol, min(dp[n][k][last_letter], dp[n][last_letter][k])); } cout << sol; return 0; }