Решения заданий ФИПИ ЕГЭ по информатике: «Массивы и строки» — с ответами

Поиск максимальной последовательности

Текстовый файл состоит из десятичных цифр и заглавных букв латинского алфавита. Определите в прилагаемом файле последовательность из максимального количества идущих подряд символов, среди которых…

1. 1
   Просматриваем файл и рассматриваем каждую букву G как возможное начало последовательности.
2. 2
   Для каждого такого начала последовательно перебираем символы вправо. Учитываем количество нечётных цифр; после появления второй буквы G дальнейшее расширение для этого начала запрещаем.

Ещё 2 шага — в полном решении

Максимальная цепочка пар

Текстовый файл состоит из символов $A$, $B$, $C$, $D$ и $O$. Определите максимальное количество идущих подряд пар символов вида «согласная + гласная» в прилагаемом файле. Для выполнения этого…

1. 1
   Выделяем множества согласных и гласных символов.
2. 2
   Последовательно просматриваем символы файла. Если текущий символ и следующий образуют пару из согласной и гласной, увеличиваем длину текущей цепочки пар. Иначе сравниваем её с найденным максимумом и начинаем новую цепочку.

Ещё 1 шаг — в полном решении

Максимальное арифметическое выражение

Текстовый файл состоит из цифр 0, 1, 2, 3, 4 и знаков арифметических операций «−» и «*» (вычитание и умножение). Определите максимальное количество символов в непрерывной последовательности, которая…

1. 1
   Для решения требуется просмотреть содержимое прилагаемого текстового файла и найти самый длинный непрерывный фрагмент, соответствующий правилам записи арифметического выражения.
2. 2
   Вложение содержит только изображение кнопки «Открыть файл», а не сам текстовый файл с последовательностью символов. Поэтому длину максимального выражения определить нельзя.

Максимальное арифметическое выражение

Текстовый файл состоит из цифр 0, 2, 3, 4, 5 и знаков арифметических операций «−» и «*» (вычитание и умножение). Определите максимальное количество символов в непрерывной последовательности, которая…

1. 1
   Просматриваем текстовый файл и выделяем непрерывные фрагменты, которые могут быть арифметическими выражениями.
2. 2
   Для каждого фрагмента проверяем структуру выражения: оно начинается и заканчивается числом, знаки «−» и «*» не соседствуют, числа не содержат ведущих нулей, а число 0 не имеет знака.

Ещё 2 шага — в полном решении

Максимальная цепочка пар

Текстовый файл состоит из символов $A$, $B$ и $D$. Определите максимальное количество идущих подряд пар символов $BA$ или $DA$ в прилагаемом файле. Искомая подпоследовательность должна состоять…

1. 1
   Искомая последовательность разбивается на непересекающиеся пары, поэтому после проверки пары нужно переходить к следующему символу через два места.
2. 2
   Пара является допустимой, если её первый символ — $B$ или $D$, а второй символ — $A$.$$s[i] \in \{B,D\} \land s[i+1] = A$$

Ещё 2 шага — в полном решении

Поиск последовательности с ограничениями

Текстовый файл состоит из десятичных цифр и заглавных букв латинского алфавита. Определите в прилагаемом файле максимальное количество идущих подряд символов, оканчивающихся подстрокой 2025, среди…

1. 1
   Считываем строку из прилагаемого файла и удаляем перевод строки.
2. 2
   Перебираем возможные правые границы фрагмента и поддерживаем количество букв Y и вхождений подстроки 2025 в текущем окне.$$count_Y \ge 140,\quad count_{2025}=50$$

Ещё 2 шага — в полном решении

Максимальное арифметическое выражение

Задание выполняется с использованием прилагаемого файла. Текстовый файл состоит из цифр 0, 5, 6, 7 и знаков арифметических операций «−» и «*» (вычитание и умножение). Определите максимальное…

1. 1
   Файл просматривают как строку. Корректное арифметическое выражение имеет структуру: число, затем повторяющиеся пары «арифметический знак — число».
2. 2
   При проверке числа учитывают ограничения: число 0 записывается только одной цифрой, остальные числа не начинаются с нуля; два знака операций подряд недопустимы.

Ещё 2 шага — в полном решении

Максимальная цепочка пар BC

Текстовый файл состоит из заглавных букв латинского алфавита $A$, $B$, $C$, $D$, $E$ и $F$. Определите в прилагаемом файле максимальное количество идущих подряд символов, среди которых пара символов…

1. 1
   Считаем количество вхождений подстроки $BC$ в каждом рассматриваемом непрерывном фрагменте файла. Вхождения могут начинаться на соседних позициях, поэтому проверяем каждую пару соседних символов.$$s[i] = B \text{ и } s[i+1] = C$$
2. 2
   Для каждой левой границы фрагмента постепенно сдвигаем правую границу вправо, поддерживая число найденных пар $BC$. Если число стало равно 190, обновляем максимальную длину.

Ещё 1 шаг — в полном решении

Максимальный фрагмент без подстроки

Текстовый файл состоит не более чем из 1 200 000 символов $X$, $Y$ и $Z$. Определите максимальное количество идущих подряд символов, среди которых нет подстроки $XZZY$. Для выполнения этого задания…

1. 1
   Считываем всю строку из файла и ищем все вхождения подстроки $XZZY$. Удобно использовать метод поиска подстроки или алгоритм КМП.
2. 2
   Для каждой найденной позиции начала запрещённой подстроки вычисляем длину участка от конца предыдущей запрещённой подстроки до её начала.

Ещё 2 шага — в полном решении

Максимум пар гласная-согласная

Задание выполняется с использованием прилагаемых файлов. Текстовый файл состоит из символов A, C, D, F и O. Определите максимальное количество идущих подряд пар символов вида «гласная + согласная» в…

1. 1
   Из символов файла гласной является O, а согласными являются A, C, D и F.
2. 2
   Последовательно проверяем все пары соседних символов. Пара считается подходящей, если её первый символ равен O, а второй принадлежит множеству A, C, D, F.

Ещё 1 шаг — в полном решении

Максимальная цепочка пар

Текстовый файл состоит из символов $A$, $B$ и $C$. Определите максимальное количество идущих подряд пар символов $CA$ или $CB$ в прилагаемом файле. Искомая подпоследовательность должна состоять…

1. 1
   Файл последовательно просматривается слева направо. На каждой позиции проверяется пара из двух символов.
2. 2
   Если пара имеет вид $CA$ или $CB$, она добавляется к текущей цепочке подходящих пар. После этого текущая позиция смещается на два символа.

Ещё 2 шага — в полном решении

Максимальная допустимая последовательность

Текстовый файл состоит не более чем из 1 200 000 символов $A$, $B$, $C$ и $D$. Определите максимальное количество идущих подряд символов, среди которых нет символов $A$ и $D$, стоящих рядом. Для…

1. 1
   Последовательно просматриваем все символы файла, запоминая предыдущий символ.
2. 2
   Если текущий и предыдущий символы образуют пару $AD$ или $DA$, участок допустимых символов заканчивается перед текущим символом. Текущая длина устанавливается равной 1.

Ещё 2 шага — в полном решении

Максимальная цепочка символов

Текстовый файл состоит не более чем из 1 200 000 символов $A$, $B$, $C$ и $D$. Определите максимальное количество идущих подряд символов, среди которых нет символов $B$ и $D$, стоящих рядом. Для…

1. 1
   Нужно найти самый длинный непрерывный фрагмент, в котором нигде не встречается соседняя пара $BD$ или $DB$.
2. 2
   Файл просматривают однократно. Для каждой пары соседних символов проверяют, являются ли они $B$ и $D$ в любом порядке. Если да, текущая длина фрагмента сбрасывается до 1; иначе она увеличивается на 1.$$p_i=B\land p_{i+1}=D\quad\text{или}\quad p_i=D\land p_{i+1}=B$$

Ещё 1 шаг — в полном решении

Максимальная последовательность символов

Текстовый файл состоит из символов, обозначающих прописные буквы латинского алфавита. Определите максимальное количество идущих подряд символов, среди которых никакие две буквы из набора букв $A$…

1. 1
   Обозначим множество запрещённых для соседства букв: $S = \{A, B, C\}$. Нарушение возникает только тогда, когда и текущий, и предыдущий символы принадлежат $S$.$$s_{i-1} \in S \land s_i \in S$$
2. 2
   Выполняем однократный просмотр файла. Если найдено нарушение, длина текущего фрагмента становится равной 1. В противном случае она увеличивается на 1. Одновременно сохраняем наибольшее значение.

Ещё 1 шаг — в полном решении

Максимальная последовательность без PP

Задание выполняется с использованием прилагаемых к заданию файлов. Текстовый файл состоит не более чем из 1 200 000 символов P, Q, R и S. Определите максимальное количество идущих подряд символов…

1. 1
   Последовательность допустима, пока в ней не встречается пара соседних символов $P$. Поэтому строку достаточно просмотреть один раз.
2. 2
   При обнаружении соседних символов $P$ текущая длина последовательности сбрасывается. В остальных случаях она увеличивается на единицу; после каждого шага сохраняется наибольшее значение.

Ещё 1 шаг — в полном решении

Максимальная подпоследовательность

Текстовый файл состоит из символов $T$, $U$, $V$, $W$, $X$, $Y$ и $Z$. Определите в прилагаемом файле максимальное количество идущих подряд символов (длину непрерывной подпоследовательности), среди…

1. 1
   Считываем содержимое файла и рассматриваем его как строку. Будем хранить левую границу текущего фрагмента, число символов $T$ в нём и максимальную найденную длину.
2. 2
   Двигаем правую границу по строке. Если очередной символ равен $T$, увеличиваем счётчик. Если количество символов $T$ стало больше 100, сдвигаем левую границу вправо, уменьшая счётчик при удалении символа $T$.

Ещё 1 шаг — в полном решении

Максимальное арифметическое выражение

Задание выполняется с использованием прилагаемого файла. Текстовый файл состоит из цифр 0, 6, 7, 8, 9 и знаков арифметических операций «−» и «*» (вычитание и умножение). Определите максимальное…

1. 1
   Разбираем файл на непрерывные фрагменты, состоящие из цифр 0, 6, 7, 8, 9 и знаков «−», «*».
2. 2
   Для каждого фрагмента проверяем структуру арифметического выражения: оно начинается и заканчивается числом, знаки операций не стоят рядом, а числа не содержат ведущих нулей; отдельное число 0 записывается только как «0».

Ещё 1 шаг — в полном решении

Максимальная допустимая последовательность

Текстовый файл состоит не более чем из 1 200 000 символов K, L, M и N. Определите максимальное количество идущих подряд символов, среди которых нет символов K и M, стоящих рядом. Для выполнения…

1. 1
   Последовательно просматриваем символы файла, храня предыдущий символ и длину текущей последовательности.
2. 2
   Если текущий и предыдущий символы образуют пару KM или MK, текущую длину устанавливаем равной 1; иначе увеличиваем её на 1.

Ещё 2 шага — в полном решении

Максимальная разрешённая последовательность

Задание выполняется с использованием прилагаемых к заданию файлов. Текстовый файл состоит не более чем из 1 200 000 символов $A$, $B$, $C$ и $D$. Определите максимальное количество идущих подряд…

1. 1
   Условие нарушается только в том случае, если рядом стоят символы $A$ и $B$ в любом порядке: $AB$ или $BA$.
2. 2
   Просматриваем файл слева направо. Для каждого символа сравниваем его с предыдущим. Если образовалась запрещённая пара, текущую длину последовательности начинаем заново.

Ещё 2 шага — в полном решении

Максимальная строка без соседних букв

Текстовый файл состоит из символов, обозначающих прописные буквы латинского алфавита. Определите максимальное количество идущих подряд символов, в которых никакие две буквы из набора букв $N$, $O$ и…

1. 1
   Последовательно просматриваем символы файла, поддерживая длину текущего фрагмента, в котором не встречается запрещённая соседняя пара.
2. 2
   Если текущий и предыдущий символы одновременно принадлежат множеству $\{N, O, P\}$, текущий фрагмент заканчивается. Счётчик сбрасывается до $1$ для текущего символа.

Ещё 2 шага — в полном решении