После урока про сортировки Маша решила применить полученные знания с пользой. У неё есть тетрадка, куда она записывает всех, кому за что-нибудь благодарна. Список может быть очень длинным, но Маша его упорядочила по алфавиту (это называется – лексикографический порядок). Помогите ей организовать быстрый поиск по этому списку. Формат ввода На первой строке передается количество людей в списке – натуральное число. Затем на следующих строках идет список людей. А после списка – перечень префиксов

Задача состоит в организации быстрого поиска в отсортированном списке. Мы можем использовать бинарный поиск для решения этой задачи.

Шаги решения:
1. Прочитать количество людей в списке и сохранить его в переменной N.
2. Создать список (назовем его ‘people’), в котором будем хранить имена людей.
3. Прочитать N строк с именами людей и добавить их в список ‘people’.
4. Отсортировать список ‘people’ в лексикографическом порядке.
5. Прочитать перечень префиксов, сохранить их в отдельном списке (назовем его ‘prefixes’).
6. Для каждого префикса в списке ‘prefixes’, выполнить следующие шаги:
– Применить бинарный поиск для поиска первого и последнего вхождения префикса в списке ‘people’.
– Если не найдено ни одного вхождения префикса, вывести “-1 -1”.
– Если найдено хотя бы одно вхождение префикса, вывести индексы первого и последнего вхождения разделенные пробелом.

Пример:
Ввод:
5
Alice
Bob
Charlie
Eve
Mallory
2
Al
C

Вывод:
0 1
-1 -1

На первом шаге мы прочитали количество людей в списке (N = 5) и создали список ‘people’. Затем прочитали N строк с именами людей и добавили их в список ‘people’. Далее, отсортировали список ‘people’ в лексикографическом порядке.
На втором шаге мы прочитали перечень префиксов (префиксы: “Al” и “C”) и добавили их в список ‘prefixes’.
На третьем шаге мы выполнили бинарный поиск для каждого префикса и вывели результат. В данном случае, префикс “Al” найден в списке ‘people’ с индексами 0 и 1, а префикс “C” не найден в списке ‘people’.