B. Строковая ловушка

Codeforces

IDCF10120B

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Дана строка длины n. В начальный момент времени вы находитесь в позиции 1 (позиции нумеруются с единицы), на каждом шаге выполняется переход в другую позицию в соответствии с следующими правилами: если в строке есть еще одна или более позиций, буквы в которых совпадают с буквой в текущей позиции, то вы переходите случайную из них, иначе — двигаетесь на одну позицию вправо. Можно ли выбраться из строки (под этим понимается, что вы в какой-то момент времени находитесь в позиции n после чего сдвигаетесь вправо) или же Вы попали в строковую ловушку, и вам придется блуждать по ней вечно? В первой строке дано число n (1 ≤ n ≤ 105) — длина строки. Во второй строке дана строка s, строка состоит только из строчных букв латинского алфавита. Выведите «_YES_», если выбраться из строки возможно, и «_NO_» — в противоположном случае. ## Входные Данные В первой строке дано число n (1 ≤ n ≤ 105) — длина строки.Во второй строке дана строка s, строка состоит только из строчных букв латинского алфавита. ## Выходные Данные Выведите «_YES_», если выбраться из строки возможно, и «_NO_» — в противоположном случае. ## Примеры Входные данные3abcВыходные данныеYESВходные данные3aaaВыходные данныеNO [samples]

**Definitions** Let $ n \in \mathbb{Z} $ be the length of the string. Let $ s = s_1 s_2 \dots s_n $ be a string over the alphabet $ \Sigma \subseteq \{a, b, \dots, z\} $. Let $ p_t \in \{1, 2, \dots, n\} $ denote the position at step $ t $, with $ p_0 = 1 $. **Transition Rules** At each step $ t $: - If $ \exists j \ne p_t $ such that $ s_j = s_{p_t} $, then $ p_{t+1} $ is chosen uniformly at random from $ \{ j \mid j \ne p_t \text{ and } s_j = s_{p_t} \} $. - Otherwise, $ p_{t+1} = p_t + 1 $. **Objective** Determine whether there exists a finite $ t $ such that $ p_t = n $ and the next transition moves to position $ n+1 $ (i.e., the string is exited). **Output** Output "YES" if exit is possible; "NO" otherwise.

API Response (JSON)

{
  "problem": {
    "name": "B. Строковая ловушка",
    "description": {
      "content": "Дана строка длины n. В начальный момент времени вы находитесь в позиции 1 (позиции нумеруются с единицы), на каждом шаге выполняется переход в другую позицию в соответствии с следующими правилами: есл",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10120B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Дана строка длины n. В начальный момент времени вы находитесь в позиции 1 (позиции нумеруются с единицы), на каждом шаге выполняется переход в другую позицию в соответствии с следующими правилами: есл...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the length of the string.  \nLet $ s = s_1 s_2 \\dots s_n $ be a string over the alphabet $ \\Sigma \\subseteq \\{a, b, \\dots, z\\} $.  \nLet $ p_t \\in \\{1, 2, \\...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments