В 2024 году я принял участие в этом конкурсе и стал победителем (🎉), поэтому хочу из первых рук поделиться информацией о том, как это было.
В первой статье с общей информацией о конкурсе я рассказал о том, какие этапы необходимо было пройти. В этой части подробнее напишу о предметном тестировании по информатике.
Предметное тестирование представляет собой решение заданий на программирование околоолимпиадной тематики. Среди членов жюри конкурса были А.Кириенко и Е. Андреева и М. Густокашин, что многое объясняет) Всего было 6 заданий, на написание отводилось 2 часа 30 минут.
Мой результат получился таким
Задания я решал сам, без использования поиска в Интернете или ИИ. Во-первых, это правильно) А во-вторых, списывание вполне можно отследить.
После проведения предметного тура организаторы конкурса выложили разбор заданий.
Теперь о каждой задаче подробнее. В карусели изображений представлены условия задачи, а после программных решений разбор от организаторов.
Задача A. Камень, ножницы, бумага
Очень простая задача на условный оператор и сложные логические условия. Решилась с первой попытки
Задача B. Аня и коллекционные карточки
В этом задании пришлось внимательно читать, что именно гарантируется в бустере. Проще всего с максимальным количеством бустеров. Поскольку в каждом бустере есть хотя бы одна не обычная карточка, чтобы получить как можно больше бустеров, будем считать, что она ровно одна. Тогда в каждом бустере будет либо легендарная, либо редкая. А всего их будет n + m. С минимальным количеством посложнее. Если в бустере не более одной легендарной, значит, бустеров, как минимум, столько, сколько легендарных. И в каждый такой бустер мы можем добавить не более двух редких. Можно посчитать, сколько бустеров надо под легендарные и под редкие и взять максимум из них, чтобы поместились все. Решение получается короткое, но сначала надо было прийти к этим заключениям
Задача C. Удвоение букв
С этой задачей справился за 4 посылки. Не сразу удалось учесть все случаи. Необходимо удвоить некоторые буквы слова так, чтобы слово было минимальным лексикографически. Ограничение на длину строки 10^5 не позволяет решать задачу перебором.
Логика решения у меня получилась такой: перебираем строку посимвольно.
Если текущий символ больше, чем следующий за ним, то дублировать его не надо, строка станет только больше лексикографически. Например, 152, рассматриваем 5. Если продублируем, будет 1552, что лексикографически больше, чем 152.
Если текущий символ меньше, чем следующий за ним, то символ дублируем, строка от этого станет меньше. Если в 152 мы рассматриваем 1, то продублировав ее получим 1152, что меньше чем 152.
Самая сложная ситуация - когда идут подряд одинаковые символы. Сначала необходимо посчитать, сколько символов у нас подряд повторяются.
Если следующий символ после повторяющихся больше, чем повторяющийся, мы дублируем все повторяющиеся символы. Логика как у ситуации выше. Если повторяющийся символ больше следующего, то не дублируем его.
А еще не надо дублировать символ или повторяющиеся символы, если они в конце строки. Они увеличат длину, что сделает строку лексикографически большей.
Итоговое решение выглядит так
Данные задания у меня получилось решить полностью, на 100 баллов. Оставшиеся три задачи разберем в следующей статье, чтобы пост не получился слишком длинным.
А как бы Вы решили такие задачи? Делитесь своими вариантами в комментариях.