Командная олимпиада школьников Санкт- Петербурга по информатике и программированию. Разбор задач

Задача A
Бактерии

Автор задачи – Михаил Дворкин
Условие – Михаил Дворкин
Подготовка тестов – Сергей

Постановка задачи

Дано целое число n
За один шаг можно:
Разделить n на любой

Идея решения

Определить, возможно ли получить m
Разложить m на простые делители
Если хотя

Нахождение решения

Рассмотреть задачу с конца ― получить из m число n,

Решение

Разложить оба числа на простые множители
Пока существует простой делитель, который входит

Почему это работает?

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

Задача B
Шахматная
головоломка

Автор задачи – Виталий Аксенов
Условие – Сергей Поромов
Подготовка тестов – Владимир

Условие задачи

Дано расположение коня на доске
Требуется поставить ладью и слона на

Как решать?

Если слон или ладья бьют коня, то конь их не

Интересные клетки

Ладья бьет все поля в том же столбце или строке
Слон

Задача C
Шоколад

Автор задачи – Виталий Аксенов
Условие – Антон Ахи
Подготовка тестов – Нияз

О чем задача?

Как решать?

Перебрать всевозможные вертикальные и горизонтальные разрезы
Проверить, можно ли хоть один

Задача D
Луна

Автор задачи – Юрий Петров
Условие – Юрий Петров
Подготовка тестов – Владимир

О чем задача?

Необходимо найти луну на фотографии

Как решать?

Ограничения небольшие – можно и достаточно проверить всевозможные положения и

Как проверить луну?

Проверить, что все точки фотографии на расстоянии не более

Задача E
Ожерелье

Автор задачи – Михаил Дворкин
Условие – Сергей Поромов
Подготовка тестов – Нияз

Как решать?

Ожерелий из двух, трех, четырех и пяти жемчужин нет
Для остальных

Альтернативное решение

Генерируем случайное ожерелье
Проверяем, есть ли ось симметрии

Задача F
Гонки

Автор задачи – жюри олимпиады
Условие – Антон Банных
Подготовка тестов – Виталик

За какое время проедет машина?

Проедет x div (tv) целых сегментов длинной

Как решать?

Время для одной машины
x / v + (ceil(x / (tv))

Задача G
Робот

Автор задачи – Михаил Дворкин
Условие – Михаил Дворкин
Подготовка тестов – Алексей

О чем задача

Робот переместился из начала координат в точку A(x, y),

Как решать?

Длина каждого отрезка пути не меньше 1 и не больше

Пусть робот попадет в точку B, если всегда будет смещаться на

Если все направления, коэффициенты при которых не равны 0, были найдены

Если какого-то направления с ненулевым k нет в пути, то ответа

Задача H
Санта

Автор задачи – Виталий Аксенов
Условие – Сергей Мельников
Подготовка тестов – Алексей

О чем задача

Даны два списка из K и М натуральных чисел,

Как решать?

Так как каждое число встречается в списках не более одного

Задача I.
Подстрока

Автор задачи – Антон Банных
Условие – Антон Банных
Подготовка тестов – Антон

Решение

Ахо-Корасик
Строка abc
Запросы:
2 3 bc
2 3 abc

Решение

Для каждого префикса строки запишем, в какой вершине автомата мы оказались
а

Решение

Рассмотрим дерево, образованное суффиксными ссылками

Решение

Для каждого запроса нужно определить, встречалась ли вершина из соответствующего поддерева

Решение

Перенумеруем вершины в порядке выхода из обхода в глубину

Вершины одного поддерева имеют последовательные номера
Пусть пара (префикс, номер вершины) —

Решение

Двумерное дерево отрезков — O(n log n)
Одномерное дерево отрезков на сумму
События:
Начало

Задача I.
Подстрока

Автор задачи – Антон Банных
Условие – Антон Банных
Подготовка тестов – Антон

Как решать?

Ахо-Корасик
Суффиксный массив
Суффиксное дерево
Суффиксный автомат

Ахо-Корасик

Строка abc
Запросы:
2 3 bc
2 3 abc

Решение

Для каждого префикса строки запишем, в какой вершине автомата мы оказались
а

Идея решения

Рассмотрим дерево, образованное суффиксными ссылками

Задача

Запрос: l, r, длина строки len
Строке соответствует вершина x
Определить, встречалась ли

Решение

Перенумеруем вершины в порядке выхода из обхода в глубину

Решение

Вершины одного поддерева имеют последовательные номера
Пусть пара (префикс, номер вершины) –

Решение

Решение

Двумерное дерево отрезков: O(n log2 n)
Одномерное дерево отрезков на сумму
События:
Начало прямоугольника
Конец

Асимптотика

Ахо-Корасик: O(n)
Перенумерация вершин: O(n)
Обработка запросов: O(n log n)

Задача J
Вода

Автор задачи – Виталий Аксенов
Условие – Антон Ахи
Подготовка тестов – Антон

Как решать?

Поддерживаем текущий уровень воды
Поддерживаем суммарную скорость вытекания воды
Обрабатываем события

События

Уровень воды достиг очередного отверстия
Запрос на уровень воды
Появление новой течи
Устранение течи

Решение

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

Реализация

Выделим «интересные высоты» ─ те, которые встречаются в запросах
Храним скорость вытекания

Реализация

Появление и починка течи ─ изменение соответствующего элемента массива и суммарной

Асимптотика

Выделение «интересных высот»
сортировка: O(n log n)
хеш-таблица: O(n)
Обработка событий: O(n)
Итого: O(n) или