✅ Обязательные задачи (LMS)#

Эти задачи нужно решить и сдать в LMS.

Задача 1. Рассадка участников#

Условие#

На олимпиаду по информатике пришло N участников. Известно, в какой школе учится каждый из них. В компьютерном классе N компьютеров стоят в одну линию вдоль стены.

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

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

В первой строке вводится число N (1 ≤ N ≤ 1000). Во второй строке — N натуральных чисел, номера школ участников.

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

YES, если рассадить можно, иначе NO.

Примеры#

Ввод:

5
1 1 1 2 3

Вывод:

YES

Ввод:

4
1 1 1 2

Вывод:

NO

Заметка

В первом примере подойдёт рассадка 1 2 1 3 1. Во втором примере троих участников из школы 1 на четыре места без соседства не посадить.

Совет

Посчитайте, сколько участников из самой «многочисленной» школы. Рассадить можно, если это количество не больше (N + 1) / 2.

Задача 2. Туристический маршрут#

Условие#

Дана карта гор Авалона: высоты точек при движении с запада на восток. Туристический маршрут — это отрезок подряд идущих точек, на котором есть подъём и спуск: внутри маршрута найдётся точка, которая строго выше и начальной, и конечной точки.

Найдите длину самого короткого туристического маршрута. Длина маршрута — количество точек в нём.

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

В первой строке вводится число N — количество точек. Во второй строке — N целых чисел, высоты точек.

Гарантируется, что хотя бы один туристический маршрут существует.

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

Одно число — минимальная длина маршрута.

Пример#

Ввод:

4
15 20 20 10

Вывод:

Заметка

Отрезки 15 20 20 и 20 20 10 не подходят: высота 20 не строго больше конца 20. Подходит только весь маршрут 15 20 20 10 — его длина 4.

Совет

Переберите все пары концов i < j, найдите максимум на отрезке [i, j] и проверьте, что он строго больше a[i] и a[j]. Начальное значение ответа возьмите заведомо большим, например N + 1.

Задача 3. Близость геномов#

Условие#

Геном — строка из заглавных латинских букв. Пары соседних оснований — это все подстроки длины 2. Степень близости первого генома второму — количество пар первого генома, которые встречаются во втором геноме.

Если одна и та же пара встречается в первом геноме несколько раз, каждое вхождение считается отдельно.

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

Две строки s1 и s2, каждая на отдельной строке.

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

Одно число — степень близости первого генома второму.

Пример#

Ввод:

ABBACAB
BCABB

Вывод:

Заметка

Пары первого генома: AB, BB, BA, AC, CA, AB. Пары второго: BC, CA, AB, BB. Во втором геноме встречаются AB, BB, CA и ещё раз AB — всего 4.

Совет

Пару выделяйте через s1.substr(i, 2), а наличие во второй строке проверяйте через s2.find(pair) != string::npos.

Задача 4. Срез строки#

Условие#

Дана строка S и три целых числа start, end, step. Постройте срез строки: символы с индексами start, start + step, start + 2·step, ..., строго меньшими end. Индексы считаются с нуля.

Если end больше длины строки, срез идёт до конца строки.

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

В первой строке — строка S без пробелов. Во второй строке — три целых числа start, end, step (0 ≤ start, 0 ≤ end, step ≥ 1).

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

Получившаяся строка. Если в срез не попал ни один символ, выведите пустую строку.

Пример#

Ввод:

abcdefg
1 6 2

Вывод:

bdf

Заметка

Берутся символы с индексами 1, 3, 5: b, d, f. Следующий индекс 7 уже не меньше 6, поэтому срез заканчивается. Так же работает срез S[1:6:2] в Python.

Задача 5. Свободные купе#

Условие#

В плацкартном вагоне 54 места, пронумерованных от 1 до 54. Вагон разбит на 9 купе.

Первые 36 мест расположены по левую сторону от прохода: места 1–4 находятся в первом купе, места 5–8 — во втором, и так далее, места 33–36 — в девятом. По правую сторону от прохода — боковые места с номерами от 37 до 54, они нумеруются в противоположном направлении: места 37 и 38 стоят напротив девятого купе, а места 53 и 54 — напротив первого.

Группа школьников едет на олимпиаду и хочет купить несколько подряд идущих купе целиком, вместе с прилегающими боковыми местами. Даны номера свободных мест. Определите, какое наибольшее число подряд идущих купе полностью свободно.

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

В первой строке — число N (0 ≤ N ≤ 54), количество свободных мест. Далее N строк — номера свободных мест.

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

Одно число — наибольшее количество подряд идущих полностью свободных купе.

Пример#

Ввод:

Вывод:

Заметка

Полностью свободно только второе купе: места 5, 6, 7, 8 и боковые 51, 52. В первом купе занято место 2, в третьем — места 11 и 12.

Совет

Отметьте свободные места в массиве флажков bool freeSeat[55] = {false};. Купе i (от 1 до 9) — это места 4*i - 3, 4*i - 2, 4*i - 1, 4*i и боковые 55 - 2*i, 56 - 2*i. Затем найдите самую длинную серию свободных купе.

Задача 6. Операции со строками#

Условие#

Даны три строки. Над каждой строкой разрешается выполнять две операции:

заменить любой символ на два таких же символа (a → aa);
заменить два подряд идущих одинаковых символа на один (aa → a).

С помощью этих операций нужно сделать все три строки равными одной и той же строке S, причём S должна быть как можно короче. Если сделать строки равными невозможно, выведите IMPOSSIBLE.

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

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

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

Строка S или слово IMPOSSIBLE.

Примеры#

Ввод:

aab
abb
ab

Вывод:

ab

Ввод:

ab
ba
ab

Вывод:

IMPOSSIBLE

Совет

Операции меняют только длину «блоков» одинаковых символов, но не их порядок. Сожмите каждую строку, оставив по одному символу из каждого блока (aabbbcc → abc). Если все три сжатые строки равны — это и есть ответ. Сжатие удобно оформить функцией string compress(string s).