Задача 4. Берёзы
Есть две параллельные прямые, на одной N точек, на другой M точек (по условию задачи, это аллеи, на которых растут берёзы). Известно расстояние между прямыми и координаты точек на прямых (задается одним числом - расстоянием от начала прямой).
Есть ленточка длины L.
Спрашивается, какое максимальное количество берёз можно окружить этой ленточкой, при этом надо окружить хотя бы по одной берёзе с каждой стороны.
Или, более формально: рассмотрим всевозможные множества точек, длина выпуклой оболочки которых <= L и в множестве есть хотя бы одна точка с каждой прямой. Нужно вывести размер максимального из этих множеств. Ситуация 1: (N + M) < 50 (30 баллов) Давайте для начала поймём, что в ответ будет входить какой-то отрезок подряд идущих берёз сверху и какой-то отрезок подряд идущих берёз снизу.
У одного отрезка два конца. У двух отрезков 4 конца.
Отсюда очевидное решение за N^4, где просто перебираем все четыре конца и за O(1) считаем ответ. Ответом является сумма верхнего и нижнего отрезка плюс сумма двух отрезков, которые пересекают аллею (вычислим их по теореме Пифагора). Получим 30 баллов.
Ситуация 2: (N + M) < 500 (60 баллов)
Чтобы получить 60 баллов, заметим, что если мы сможем с помощью верёвки длины L получить X берёз, то точно сможем получить любой ответ из интервала [2; X].
Отсюда вывод: можно сделать бинарный поиск по ответу. Теперь мы считаем, что сумма длин отрезков у нас зафиксирована (мы её вычисляем в бинарном поиске). Давайте за N^3 переберём первые три точки (две точки нижнего отрезка и одну верхнего). Так как у нас зафиксирована общая длина, то вычтем из неё длину нижнего отрезка и узнаем длину верхнего, а так как нам известна первая точка верхнего отрезка, то мы можем вычислить и вторую точку верхнего отрезка.
Итак, мы получили координаты всех четырёх точек, значит, можем посчитать периметр. Асимптотика составляет O(N^3 * log(N)).
Ситуация 3: решение задачи на 100 баллов
И снова - бинпоиск по ответу. Теперь надо минимизировать длину при фиксированном количестве.
Переберём i,j — два начала. Тогда есть отрезок валидных концов на правой половине таких, что соответствующий левый конец с таким ответом где-то в адекватном месте. При фиксированных i,j надо минимизировать x + y + sqrt((x-y)^2 + d). Это запрос минимума на диагональном отрезке в матричке.
Если перебирать i,j сначала по сумме, то можно соответствующей такой сумме диагональ в матрице выписать и делать обычное дерево отрезков.
Получается NM*log^2.
Дальше из этого делается NM*log либо SparceTable'ом, либо аккуратным слежением за валидными концами и очередью с минимумом. Вроде без этого набирало 100. http://codeforces.ru/blog/entry/6449#comment-118763 Задача 3: A + B = C
Дано число С, состоящее не более чем из 10000 цифр, то есть 1 <= C < 1010001.
Пусть С - это n-значное число. Найти количество пар таких n-значных чисел A и B, чтобы выполнялись следующие условия:
1. A + B = C 2. A и B - красивые числа (число называют красивым, если любые две соседние цифры не равны. Например, число 5651 - красивое, а 5561 - нет). Решение на 100 баллов
Будем использовать идею динамического программирования.
Состояние динамики:
dp[i][j][k] - мы обработали i позиций с конца(0 <= i < n) в числе A, где i-ая цифра A[i] = j (0 <= j <= 9), k - параметр (равный 0 или 1) показывает, был ли с предыдущего шага переход через разряд.
По j и k однозначно восстанавливается B[i], из уравнения A[i] + B[i] + k = C[i].
Переходы в динамике: следим, чтобы не было двух подряд идущих одинаковых чисел и выполнялись условия состояния динамики.
Ответ на задачу:
сумма dp[n - 1][i][0] для таких i, что A[i] != 0 и B[i] != 0.
Пусть d = 10 * 2 (10 чисел + ( было/ не было) перехода через разряд) Из каждого состояния будет O(d) переходов. Следовательно, асимптотика составит O(n * d * d). |
| |||||||||