⭐ Необязательные задачи#

Дополнительная тренировка по теме. Решайте, если обязательные задачи уже сданы.

Задача 1. Зеркальное слово#

Условие#

Дано слово. Определите, является ли оно палиндромом, то есть одинаково ли читается слева направо и справа налево.

Входные данные#

Одно слово из строчных латинских букв.

Выходные данные#

YES, если слово — палиндром, иначе NO.

Примеры#

Ввод	Вывод
`level`	`YES`
`hello`	`NO`
`a`	`YES`

Совет

Заведите два индекса: left = 0 и right = s.size() - 1. Пока left < right, сравнивайте s[left] и s[right] и сдвигайте индексы навстречу друг другу. Проверку удобно вынести в функцию bool isPalindrome(string s).

Задача 2. Самая популярная задача#

Условие#

На олимпиаде было 10 задач с номерами от 1 до 10. Известно, какую задачу сдал каждый из N участников. Определите номер задачи, которую сдавали чаще всего. Если таких задач несколько, выведите задачу с наименьшим номером.

Входные данные#

В первой строке вводится число N (1 ≤ N ≤ 1000). Во второй строке — N чисел от 1 до 10.

Выходные данные#

Номер самой популярной задачи.

Примеры#

Ввод	Вывод
`7` `3 1 3 7 1 3 2`	`3`
`4` `5 2 5 2`	`2`

Заметка

Заведите массив счётчиков int cnt[11] = {0}; и для каждого числа x делайте cnt[x]++. Индекс 0 не используется — так номера задач совпадают с индексами.

Задача 3. Хороший массив#

Условие#

Массив называется хорошим, если каждое число x, которое в нём встречается, встречается ровно x раз. Например, массив 3 1 3 2 3 2 хороший: единица встречается один раз, двойка — два, тройка — три.

Определите, является ли данный массив хорошим.

Входные данные#

В первой строке вводится число N (1 ≤ N ≤ 1000). Во второй строке — N чисел от 1 до 1000.

Выходные данные#

YES, если массив хороший, иначе NO.

Примеры#

Ввод	Вывод
`6` `3 1 3 2 3 2`	`YES`
`3` `2 2 2`	`NO`
`1` `1`	`YES`

Совет

Сначала посчитайте, сколько раз встречается каждое число: cnt[a[i]]++. Потом пройдите по массиву ещё раз и проверьте cnt[a[i]] == a[i] для каждого элемента. Обратите внимание: здесь нужны два прохода, поэтому числа придётся сохранить в массив.

Задача 4. Все вхождения подстроки#

Условие#

Даны строка s и образец t. Выведите позиции (считая с нуля) всех вхождений t в s. Вхождения могут перекрываться.

Входные данные#

Две строки из строчных латинских букв, каждая на отдельной строке.

Выходные данные#

Позиции всех вхождений через пробел в порядке возрастания. Если вхождений нет, выведите -1.

Примеры#

Ввод	Вывод
`abababa` `aba`	`0 2 4`
`hello` `ll`	`2`
`hello` `xyz`	`-1`

Совет

Перебирайте начальную позицию i от 0, пока i + t.size() <= s.size(), и сравнивайте s.substr(i, t.size()) == t. Другой способ — s.find(t, from): второй аргумент задаёт, с какой позиции искать.

Задача 5. Минимальное окно#

Условие#

Дана строка из строчных латинских букв. Найдите длину самой короткой подстроки, которая содержит все различные буквы, встречающиеся в строке.

Входные данные#

Одна строка длиной до 10⁵ символов.

Выходные данные#

Одно число — длина минимального окна.

Примеры#

Ввод	Вывод
`aabcbcdbca`	`4`
`aaaa`	`1`
`abc`	`3`

Заметка

В первой строке четыре различные буквы a, b, c, d. Самое короткое окно, которое их все содержит, — dbca, его длина 4.

Совет

Задача на метод двух указателей. Двигайте правую границу r и считайте буквы в окне массивом int cnt[26]. Как только в окне есть все нужные буквы, сдвигайте левую границу l, пока это условие не нарушится, и обновляйте ответ. Каждая граница проходит строку один раз, поэтому решение работает быстро даже для 10⁵ символов.