Задача А. ДДД
Правильный ответ задачи – 69.
Задача B. Про Дениса М.
Время, которое потратит команда,
можно вычислить по формуле t
= 112 + (391 + B + 1) +
(B * 20), число B дано на входе. Нужно
вычислить значение формулы и сравнить его с числом 738. Получается, что при B = 11 Денис ещё выходит в
финал, а при B = 12 уже
нет.
Задача C. Тройка чисел
Обозначим числа из входных данных
a, b, c. Нам нужно выбрать максимум из a, b, c, ab, ac, bc, abc.
Последнее произведение не влезает ни в один целочисленный тип, поэтому следует
использовать для вычисления произведений и их сравнения тип double.
Задача D. Классификатор Тимуса
Это техническая задача, нужно
написать любое решение, выполняющее то, что сказано в условии.
Задача E. Берегите брови!
Ключевые слова: дерево отрезков, дерево Фенвика, бинарное
сбалансированное дерево. Если вы не сумели сдать задачу на контесте и не знаете
этих слов, то вам будет полезно найти и почитать информацию о них.
Создадим бинарное
сбалансированное дерево, ключами в котором будут названия напитков, а
значениями – текущее количество данного напитка в шоте. В таком случае
наливание жидкости – это просто увеличение значения в одной из вершин. В каждой
вершине требуется дополнительно хранить сумму значений на поддереве. Тогда
нахождения напитка по заданной глубине можно будет найти простым спуском по
дереву.
Выпивание части одного из ликёров
– это просто вычитание из значения в одной из вершин. Выпивание всего ликёра – это
удаление вершины из дерева. Заметим, что удалений вершин не может быть более,
чем n.
Все вышеперечисленные операции
выполняются за время O(log n), что позволяет решить всю
задачу за время O(n log n).
Кроме того, названия всех
напитков известны заранее, поэтому мы можем заранее занумеровать их числами от
1 до n
и вместо бинарного сбалансированного дерева использовать дерево отрезков
или дерево Фенвика.
Задача F. Парадокс трамвая
Ключевые слова: Теория вероятности, метод динамического
программирования.
Будем считать, что если в первом
и втором вагоне трамвая стало равное число людей, то все останавливаются и
процесс не продолжается.
dp[i][j] –
вероятность того, что в какой-то момент времени в первом вагоне будет i человек, во втором – j человек. Такая функция
пересчитывается за время O(1).
Ответом будет сумма dp[i][i] по всем i. Итого получили решение за время O(n * n), требующее также O(n * n) памяти. По ограничению на
память это решение не пройдёт, поэтому нужно сделать «расслоение». Т.е. хранить
только две диагонали, начиная с диагонали с уравнением i + j = a + b, затем i + j = a + b + 1 и т.д.
Задача G. Васиана
Ключевые слова: поворот точки на угол, параллельный перенос, BigInteger (java), BigDecimal (java).
Если повернуть множество точек на
угол atan2(a, d), а после этого параллельно перенести,
то получится одна из четырёх фигур:
1) Точка
(0, 0)
2) Луч
с вершиной в (0, 0), направленный вверх
3) Прямая,
совпадающая с осью OY
4) Парабола
y = p * x * x
Случаи 1, 2, 3 тривиальны. В
случае 4 следует растянуть параболу и окружность по обеим осям в p раз.
В таком случае радиус окружности вырастет в p раз, а центр её переместится. Парабола
превратится в y = x * x. Теперь единственная переменная – это y-координата точки. Далее
осталось решить биквадратное уравнение.
Числа на входе превышают все
возможные целые и вещественные типы, поэтому для решения задачи нужна длинная
арифметика. Можно либо использовать тип BigInteger и решать в рациональных
дробях, либо использовать тип BigDecimal.
Все решения жюри, в том числе на C++ с самописной длинной арифметикой на массивах и на векторах, а
также на Java с использованием BigInteger и BigDecimal, работают не более 0.5
секунды. Однако важно заметить, что в решении через BigDecimal используется
EPS = 1e-75 (c 1e-70 даёт WA).
У жюри нет решения задачи с
помощью численных методов, укладывающееся в TL. Возможно, оно есть у вас? J
Задача H. Сокращения
Ключевые слова: бор, сжатый бор, LCA – наименьший общий предок.
Заметим, что чтобы минимизировать
сумму сокращений, требуется просто минимизировать длину каждого сокращения
независимо.
Пусть L – суммарная длина строки.
Построим бор всех слов. Для
каждой вершины сформируем список номеров строк, которым она принадлежит
(суммарный размер всех списков в таком случае равен L). Каждая вершина в боре – это префикс
какого-то набора исходных слов.
Также построим бор всех
развёрнутых слов, назовём его B. Его использование мы опишем
далее.
Будем обозначать сокращение парой
чисел (a, b). Для сокращения через тире:
a – длина префикса до
тире, b – длина суффикса после тире. Для сокращения через точку: a – длина префикса, b = 0.
Переберём все вершины бора. Пусть
мы зафиксировали некоторую вершину v и её глубина h
(расстояние в буквах до корня). Для всех строк, которым принадлежит данная
вершина, найдём минимальное z такое, что (h,
z) – её корректное
сокращение.
Сделаем это следующим образом:
возьмём список всех слов, лежащих в данной вершине, построим сжатый бор
развёрнутых слов для них. Мы это можем сделать за время O(m * log m), где
m –
количество слов в данной вершине. Для построения такого бора можно использовать
вызов функции LCA от бора B. В таком боре будет не
более 2m вершин. Значит, за время O(m) мы
можем обработать их все и получить ответ на все m запросов.
Общее время работы решения –
O(L * log L)
Задача I. XOR
Если 2k = A XOR B, то B = A XOR 2k.
Представим все числа в двоичном виде. XOR на степень двойки заменяет одну единицу нулём, либо наоборот,
поэтому он меняет чётность количества единиц в двоичной записи числа. Задачу
можно решить так: первая группа состоит из всех чисел с чётным числом единиц в
двоичной записи, вторая группа – из всех остальных чисел.
Задача J. Делегация УрФУ
Если a делится на 3,
то ответ a + b – 1, в противном случае 3 *
(a + b) – 1.
Задача K. Шахматный эндшпиль
Здесь нужно аккуратно разобрать
все случаи. От хода f5-e6 защититься нельзя, соответственно, для него ответ «mate». От хода b3-c3
единственная защита: d4-c3. От всех остальных ходов защищает a7-b6.
Комментариев нет:
Отправить комментарий