A. Grasshopper And the String

Codeforces

IDCF733A

Time1000ms

Memory256MB

Difficulty—

implementation

English · Original

Chinese · Translation

Formal · Original

One day, the Grasshopper was jumping on the lawn and found a piece of paper with a string. Grasshopper became interested what is the minimum _jump ability_ he should have in order to be able to reach the far end of the string, jumping only on vowels of the English alphabet. _Jump ability_ is the maximum possible length of his jump. Formally, consider that at the begginning the Grasshopper is located directly in front of the leftmost character of the string. His goal is to reach the position right after the rightmost character of the string. In one jump the Grasshopper could jump to the right any distance from 1 to the value of his _jump ability_. <center>![image](https://espresso.codeforces.com/c9bddfb78bb461141cbceccc6a5890fec0088928.png) The picture corresponds to the first example.</center>The following letters are vowels: '_A_', '_E_', '_I_', '_O_', '_U_' and '_Y_'. ## Input The first line contains non-empty string consisting of capital English letters. It is guaranteed that the length of the string does not exceed 100. ## Output Print single integer _a_ — the minimum _jump ability_ of the Grasshopper (in the number of symbols) that is needed to overcome the given string, jumping only on vowels. [samples]

有一天，蚱蜢在草坪上跳跃时发现了一张写有字符串的纸。蚱蜢想知道，为了仅在英语元音字母上跳跃并到达字符串的最末端，他所需的最小_跳跃能力_是多少。_跳跃能力_是指他单次跳跃的最大可能长度。形式化地，假设蚱蜢最初位于字符串最左侧字符的正前方。他的目标是到达字符串最右侧字符的右侧位置。每次跳跃，蚱蜢可以向右跳跃任意距离，范围为 #cf_span[1] 到他的_跳跃能力_值。以下字母为元音字母：'_A_'、'_E_'、'_I_'、'_O_'、'_U_' 和 '_Y_'。第一行包含一个由大写英文字母组成的非空字符串。保证字符串长度不超过 100。请输出一个整数 #cf_span[a] —— 蚱蜢为仅在元音字母上跳跃以越过该字符串所需的最小_跳跃能力_（以字符数计）。 ## Input 第一行包含一个由大写英文字母组成的非空字符串。保证字符串长度不超过 100。 ## Output 请输出一个整数 #cf_span[a] —— 蚱蜢为仅在元音字母上跳跃以越过该字符串所需的最小_跳跃能力_（以字符数计）。 [samples]

**Definitions** Let $ s = s_1 s_2 \dots s_n $ be a string of length $ n \geq 1 $, where each $ s_i \in \{ \text{A, B, ..., Z} \} $. Let $ V = \{ \text{A, E, I, O, U, Y} \} $ be the set of vowels. Let $ P = \{ 0 \} \cup \{ i \in \{1, \dots, n\} \mid s_i \in V \} \cup \{ n+1 \} $ be the set of valid landing positions, where position $ 0 $ is before the first character and position $ n+1 $ is after the last character. **Constraints** 1. $ 1 \leq n \leq 100 $ 2. The grasshopper starts at position $ 0 $ and must reach position $ n+1 $. 3. The grasshopper may only land on positions in $ P $. 4. Each jump must have length $ \ell $ satisfying $ 1 \leq \ell \leq J $, where $ J $ is the jump ability. **Objective** Find the minimum $ J \in \mathbb{Z}^+ $ such that there exists a sequence of positions $ p_0 = 0, p_1, \dots, p_k = n+1 $ with all $ p_j \in P $ and $ p_{j} - p_{j-1} \leq J $ for all $ j \in \{1, \dots, k\} $. Equivalently, $$ J = \max_{i=1}^{|P|-1} (p_i - p_{i-1}) $$ where $ P $ is sorted in increasing order.

Samples

Input #1

ABABBBACFEYUKOTT

Output #1

Input #2

AAA

Output #2

API Response (JSON)

{
  "problem": {
    "name": "A. Grasshopper And the String",
    "description": {
      "content": "One day, the Grasshopper was jumping on the lawn and found a piece of paper with a string. Grasshopper became interested what is the minimum _jump ability_ he should have in order to be able to reach ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF733A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "One day, the Grasshopper was jumping on the lawn and found a piece of paper with a string. Grasshopper became interested what is the minimum _jump ability_ he should have in order to be able to reach ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "有一天，蚱蜢在草坪上跳跃时发现了一张写有字符串的纸。蚱蜢想知道，为了仅在英语元音字母上跳跃并到达字符串的最末端，他所需的最小_跳跃能力_是多少。_跳跃能力_是指他单次跳跃的最大可能长度。\n\n形式化地，假设蚱蜢最初位于字符串最左侧字符的正前方。他的目标是到达字符串最右侧字符的右侧位置。每次跳跃，蚱蜢可以向右跳跃任意距离，范围为 #cf_span[1] 到他的_跳跃能力_值。\n\n以下字母为元音字母：'...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ s = s_1 s_2 \\dots s_n $ be a string of length $ n \\geq 1 $, where each $ s_i \\in \\{ \\text{A, B, ..., Z} \\} $.  \nLet $ V = \\{ \\text{A, E, I, O, U, Y} \\} $ be the set of vowels. ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments