Skip to main content
STEM:Hub

Пример из предварительного этапа

Как решать такие задачи

  • Фиксируйте неизменяемые части: все символы вне [ ] должны стоять ровно так же.
  • Внутри [ ]:
    • Диапазоны: a-g значит любая буква от a до g; A-S — от A до S.
    • Альтернация через |: [x|yz] — либо x (со своей семантикой, если это метасимвол), либо любая из букв y или z (если это просто перечисление символов). В примере задачи [a-z|123] трактуется как «строчная латинская буква» ИЛИ «цифра 1, 2 или 3».
  • Звёздочка * в маске — метасимвол: «любая непустая подстрока из латинских букв и цифр» (один или более символов [A-Za-z0-9]). Если она стоит как альтернатива внутри [*|!?], то эта позиция может быть либо такой подстрокой, либо одиночным символом ! или ?.
  • Сопоставляйте строку целиком: от начала до конца по маске.
  • Точка после OL в условии — это конец предложения, не часть маски. Сама маска: SC[a-gA-S][*|!?]OL

Проверка вариантов по маске SC[a-gA-S][*|!?]OL

  • SCHOOOL — подходит: SC + H (в A–S) + OO (это “*”, буквы) + OL.
  • SChоOL — не подходит: третья буква h вне диапазона a–g/A–S; к тому же «о» выглядит как кириллическая, не латинская.
  • SCHOO!L — не подходит: после SC и H перед «OL» стоит «!L», а нужно либо «!» затем «OL», либо буквенно-цифровая подстрока, за которой сразу «OL».
  • SCHOOLOL — подходит: SC + H + OOL (это “*”, буквы) + OL.
  • SCH*!OL — не подходит: «!» не может быть значением “”, потому что в “*” разрешены только буквы/цифры; и это не одиночный !/?.
  • SCH?OL — подходит: SC + H + ? (альтернатива в [*|!?]) + OL.

Верные ответы:

  • SCHOOOL
  • SCHOOLOL
  • SCH?OL

Кратко по маске и ответам

Маска: SC[a-gA-S][*|!?]OL

  • Вне [ ] — фиксированные символы.
  • [a-gA-S] — ровно 1 буква: либо от a до g, либо от A до S.
  • [|!?] по условию задачи — это альтернация: либо звездочка «», означающая любую непустую подстроку из латинских букв/цифр ([A-Za-z0-9]+), либо одиночный символ ! или ?.
  • Итого: строка должна быть SC + 1 буква из диапазона + (либо [A-Za-z0-9]+, либо !, либо ?) + OL, без лишних символов.

Правильные варианты

  • SCHOOOL — SC + H (в A–S) + OO (непустая буквенно-цифровая подстрока) + OL.
  • SCHOOLOL — SC + H + OOL (непустая буквенно-цифровая подстрока) + OL.
  • SCH?OL — SC + H + ? (альтернатива) + OL.

Почему остальные неверны

  • SChоOL — h не входит в диапазон a–g (младшие латинские до g включительно). К тому же «о» похоже на кириллическую букву «о», а в подстроке по «*» допускаются только латинские буквы/цифры.
  • SCHOO!L — после SC и H стоит «OO!L». В позиции [*|!?]:
    • Если взять ветку «непустая подстрока», то «OO» подходит, но дальше по маске обязано идти «OL», а у нас «!L».
    • Если взять ветку «!», то строка должна быть SC H ! OL, а у нас есть лишнее «OO» перед «!».
  • SCH*!OL — после SC и H идёт «!». Звёздочка как значение «» допускает только буквы/цифры, символ «» в самой строке недопустим. Если выбрать ветку «!», то остаётся лишний символ «», который ни к чему не привязан, — несоответствие.

Почему на regex101 получается только SCH?OL regex101 использует стандартные регулярные выражения, а в них:

  • Квадратные скобки [ ] — это класс символов, который всегда сопоставляет ровно один символ из набора.
  • Внутри класса символов:
    • «|» — не оператор ИЛИ, а простой символ «|».
    • «» — тоже не квантификатор, а обычный символ «». То есть запись SC[a-gA-S][*|!?]OL в обычном regex означает:
  • S C
  • один символ из a..g или A..S,
  • затем один символ из набора {*, |, !, ?},
  • затем O L. Из предложенных строк под это попадает только SCH?OL (при условии, что h — H заглавная как в примере). Поэтому сайт показывает только её.

Как правильно проверить на regex101 Переведите маску задачи в эквивалентный стандартный regex с якорями начала/конца строки: ^SCa-gA-SOL$

  • [A-Za-z0-9]+ — «любая непустая подстрока из букв и цифр».
  • (?:…|…) — настоящее «ИЛИ» в регэкспе. С этой регуляркой корректно совпадут SCHOOOL, SCHOOLOL и SCH?OL, а остальные — нет.

Дополнение

  • Следите, чтобы буквы были латинскими (а не кириллическими) и регистр учитывается согласно диапазонам.

Олимпиадные задания: примеры и метод решения

  1. Выбор подходящих паролей (qualitative)
  • Алгоритм:
    • Сопоставьте фиксированные части.
    • Проверьте символ из диапазона [a-gA-S].
    • Рассмотрите альтернативу: либо одиночный ?/!, либо непустая буквенно-цифровая подстрока (один или более символов [A-Za-z0-9]).
    • Учтите Unicode-подмены (латинская/кириллица).
  • Мини-набор тренировок: придумать 5 подходящих и 5 заведомо неподходящих строк с пояснением.
  1. Конструирование маски/регекса под политику (synthesis)
  • Пример: «Пароль начинается с ABC, затем 2–4 буквы/цифры, затем либо !, либо строка из цифр длиной 3.»
  • Решение:
    • Ясно разделить сегменты и альтернативу.
    • Регекс: ^ABC(?:[A-Za-z0-9]{2,4})(?:!|\d{3})$
  1. Подсчет числа допустимых паролей (counting)
  • Пример: Сколько строк соответствуют ^SCa-gA-SOL$, если ограничить длину итоговой строки ≤ 10?
  • План:
    • [a-gA-S] — 7 + 19 = 26 вариантов.
    • Альтернатива:
      • [!?] — 2 варианта длины 1.
      • [A-Za-z0-9]+ — длина k ≥ 1, алфавит 62 (52 буквы + 10 цифр).
    • Общая длина: фиксировано SC (2) + 1 + альтернатива + OL (2) = 5 + длина(альтернативы).
    • При ограничении длины ≤ 10 получаем максимальную длину альтернативы 5.
    • Итого: 26 × (2 + Σ_{k=1..5} 62^k).