A. Night at the Museum

Codeforces

IDCF731A

Time1000ms

Memory256MB

Difficulty—

implementationstrings

English · Original

Chinese · Translation

Formal · Original

Grigoriy, like the hero of one famous comedy film, found a job as a night security guard at the museum. At first night he received _embosser_ and was to take stock of the whole exposition. _Embosser_ is a special devise that allows to "print" the text of a plastic tape. Text is printed sequentially, character by character. The device consists of a wheel with a lowercase English letters written in a circle, static pointer to the current letter and a button that print the chosen letter. At one move it's allowed to rotate the alphabetic wheel one step clockwise or counterclockwise. Initially, static pointer points to letter '_a_'. Other letters are located as shown on the picture: <center>![image](https://espresso.codeforces.com/f9a6625d44375aa879555a962abab58252e0f103.png)</center>After Grigoriy add new item to the base he has to print its name on the plastic tape and attach it to the corresponding exhibit. It's not required to return the wheel to its initial position with pointer on the letter '_a_'. Our hero is afraid that some exhibits may become alive and start to attack him, so he wants to print the names as fast as possible. Help him, for the given string find the minimum number of rotations of the wheel required to print it. ## Input The only line of input contains the name of some exhibit — the non-empty string consisting of no more than 100 characters. It's guaranteed that the string consists of only lowercase English letters. ## Output Print one integer — the minimum number of rotations of the wheel, required to print the name given in the input. [samples] ## Note <center>![image](https://espresso.codeforces.com/7a9f692be97294f6f0dedd91b5e5794fcea7c621.png)</center>To print the string from the first sample it would be optimal to perform the following sequence of rotations: 1. from '_a_' to '_z_' (1 rotation counterclockwise), 2. from '_z_' to '_e_' (5 clockwise rotations), 3. from '_e_' to '_u_' (10 rotations counterclockwise), 4. from '_u_' to '_s_' (2 counterclockwise rotations). In total, 1 + 5 + 10 + 2 = 18 rotations are required.

Grigoriy 像一部著名喜剧电影的主角一样，找到了一份博物馆夜间保安的工作。在第一个夜晚，他收到了一个_凸印机_，并需要清点整个展览。 _凸印机_是一种可以“打印”塑料带文本的特殊设备。文本按顺序逐字符打印。该设备由一个带有小写英文字母排列成环的轮子、一个指向当前字母的固定指针以及一个打印所选字母的按钮组成。每次移动允许将字母轮顺时针或逆时针旋转一步。初始时，固定指针指向字母 '_a_'。其他字母的排列如图所示： Grigoriy 在将新物品加入库存后，必须在其塑料带上打印名称并将其附着到相应的展品上。不需要将轮子转回初始位置（指针指向 '_a_'）。我们的英雄担心某些展品可能会复活并攻击他，因此他希望尽可能快地打印名称。请帮助他：对于给定的字符串，求出打印它所需的轮子最小旋转次数。输入仅一行，包含某个展品的名称——一个非空字符串，长度不超过 #cf_span[100] 个字符。保证字符串仅由小写英文字母组成。请输出一个整数——打印输入中给出的名称所需的轮子最小旋转次数。对于第一个样例中的字符串，最优的旋转序列如下： ## Input The only line of input contains the name of some exhibit — the non-empty string consisting of no more than #cf_span[100] characters. It's guaranteed that the string consists of only lowercase English letters. ## Output Print one integer — the minimum number of rotations of the wheel, required to print the name given in the input. [samples] ## Note 要打印第一个样例中的字符串，最优的旋转序列如下：从 '_a_' 到 '_z_'（#cf_span[1] 次逆时针旋转），从 '_z_' 到 '_e_'（#cf_span[5] 次顺时针旋转），从 '_e_' 到 '_u_'（#cf_span[10] 次逆时针旋转），从 '_u_' 到 '_s_'（#cf_span[2] 次逆时针旋转）。总共需要 #cf_span[1 + 5 + 10 + 2 = 18] 次旋转。

Let the alphabet be arranged in a circle of 26 letters, labeled $ a, b, c, \dots, z $, with positions indexed from 0 to 25, where $ a \leftrightarrow 0 $, $ b \leftrightarrow 1 $, ..., $ z \leftrightarrow 25 $. Let $ s = s_1 s_2 \dots s_n $ be the input string of length $ n \leq 100 $, where each $ s_i \in \{a, b, \dots, z\} $. Let $ p_0 = 0 $ be the initial position of the pointer (corresponding to letter 'a'). For each character $ s_i $, let $ c_i \in \{0, 1, \dots, 25\} $ be its numeric position in the alphabet. Define the cost to move from current position $ p $ to target position $ c $ as: $$ \text{dist}(p, c) = \min\left( |p - c|, 26 - |p - c| \right) $$ Let $ p_i $ be the position of the pointer after printing the $ i $-th character. Then: - $ p_0 = 0 $ - For $ i = 1 $ to $ n $: $ p_i = c_i $ and the cost for step $ i $ is $ \text{dist}(p_{i-1}, c_i) $ The total minimum number of rotations is: $$ \sum_{i=1}^{n} \min\left( |p_{i-1} - c_i|, 26 - |p_{i-1} - c_i| \right) $$ **Objective:** Compute the above sum.

Samples

Input #1

zeus

Output #1

Input #2

map

Output #2

Input #3

ares

Output #3

API Response (JSON)

{
  "problem": {
    "name": "A. Night at the Museum",
    "description": {
      "content": "Grigoriy, like the hero of one famous comedy film, found a job as a night security guard at the museum. At first night he received _embosser_ and was to take stock of the whole exposition. _Embosser_",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF731A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Grigoriy, like the hero of one famous comedy film, found a job as a night security guard at the museum. At first night he received _embosser_ and was to take stock of the whole exposition.\n\n_Embosser_...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Grigoriy 像一部著名喜剧电影的主角一样，找到了一份博物馆夜间保安的工作。在第一个夜晚，他收到了一个_凸印机_，并需要清点整个展览。\n\n_凸印机_是一种可以“打印”塑料带文本的特殊设备。文本按顺序逐字符打印。该设备由一个带有小写英文字母排列成环的轮子、一个指向当前字母的固定指针以及一个打印所选字母的按钮组成。每次移动允许将字母轮顺时针或逆时针旋转一步。初始时，固定指针指向字母 '_a_'。其...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Let the alphabet be arranged in a circle of 26 letters, labeled $ a, b, c, \\dots, z $, with positions indexed from 0 to 25, where $ a \\leftrightarrow 0 $, $ b \\leftrightarrow 1 $, ..., $ z \\leftrighta...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments