Доброго всем времени суток!

Не столь давно во время отборочно-тренировочных занятий команды Украины перед Международной лингвистической олимпиадой был озвучен ряд довольно интересных задач на составление словарей. Что они из себя представляют? В общем случае задача такого плана формулируется следующим образом:

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

Пример: Необходимо составить словарь слов так, чтобы асимптотически минимизировать время поиска строки в нем, полностью совпадающей с строкой на входе. Очевидно, в таком случае неплохим вариантом будет стандартный словарь, в котором слова отсортированы в алфавитном порядке (тогда алгоритмом бинарного поиска мы за логарифмическое время от количества слов найдем нужную статью) (хотя на самом деле это не оптимальный вариант, но об этом чуть позже).

Позже мы решили, что операцию открытия страницы с заданным номером или статьи с заданным номером мы можем выполнять за константное время. В таком случае словарь из примера можно оптимизировать, задав функциональную зависимость между строкой и номером статьи, которая ей соответствует (или, если говорить по-людски, посчитать хеш). Тогда мы сможем искать слово за время, пропорциональное длине слова, что уже несколько круче. В принципе, используя этот подход (хеширование входных данных) может помочь нам составить необходимый словарь для любой такой задачи так, чтобы ответ искался за время, пропорциональное размеру входных данных. Поэтому всплыла еще одна характеристика — размер словаря.

Собственно, задача, которая и спровоцировала небольшой холивар, формулируется так:

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

П.С. маска — строка из символов алфавита + специального символа (скажем, "?"), который можно заменить на любую одну букву из алфавита. П.П.С. так как задачу оптимизации времени мы вроде как решили, предлагаю вам подумать над тем, как можно ужать размеры словаря так, чтобы особо не терять во времени.

В субботу 11-ого и в воскресение 12-ого января в Киеве в университете им. Бориса Гринченка прошли два тура третьего (городского) этапа Всеукраинской ученической олимпиады по информатике.

В преддверии этого мероприятия массово ходили слухи, что наконец-то это соревнование перекочует на ejudge или какую-нибудь другую систему, значительно упрощающую процесс проведения олимпиады. Однако, не судьба.

Впрочем, давайте не будем о плохом. По крайней мере никаких серьезных осечек организации не наблюдалось, что уже довольно неплохо. Также хотелось бы отметить, что условия в этом году впервые были объедены по тематике. Во всех задачах первого тура речь шла о заявке Украины на проведение Зимних Олимпийских игр 2022. Хоть и мелочь, но приятно)

Собственно, условия можно почитать тут.

Архивы работ участников первого и второго туров можно найти здесь и здесь соответственно.

Архивы с условиями, тестами, разборами и авторскими решениями можно взять отсюда и отсюда. (Условия и разбор на украинском языке)

Результаты можно посмотреть тут. (Результаты обновляются по мере тестирования работ)

Дополнительную информацию о данном соревновании вы можете найти на этом сайте. Удачи!

Помогите справиться с заданием. Идей нету вообще. Заранее спасибо

Условие:

Я.п. с++. Есть две подфункции одного уровня. Func1 и func2. Обе функции типа void, не получают и не возвращают значений. В обеих функциях есть локальная переменная temp. Функция func2 вызывает func1, а затем выводит строку со значением своей переменной temp на экран. Вот код

Задача:

функция func2 должна выводить значение, полученное от пользователя функцией func1 (то есть она должна каким-то образом получить это значение, для этого в ней и зарезервирована своя переменная temp, для удобства). Для реализации этого допускаются любые программно-аппаратные средства, КРОМЕ:

1. Изменения типов функций. Они должны оставаться void и не должны ни к чему кастоваться при вызове. Строго говоря, ни в одной из функций не должна находиться инструкция return.

2. Переноса инструкции cin >> temp из первой функции во вторую. Или добавление второй такой инструкции в func2. Значение должно запрашиваться один раз и только из функции func1. Выводиться это значение обязательно, соответственно, должно непременно из функции func2.

3. Использования глобальных переменных. А также всяческих статических классов и прочей ерунды. Добавляться в ходе решения что-то должно только в коде этих двух функций.

4. Использования указателей, ссылок.

5. Записи\чтения файлов.

6. Использования системных средств — семафоров, счетчиков, флажков, блокировок и т.д. А также любых других средств API.

7. Использования сетевых соединений