Зашло не очень оптимальное решение примерно с 40^6 операциями. Выгодно покупать предметы слева направо. Динамика, где состояние номер предмета — id, кол-во денег — k ,сколько в предыдущих из (id+1, id+2, ... ) предметов были куплены, храним максимальный профит. Переход заключается в покупке нескольких предметов типа id.

обычная дп от 3х параметров (позиция, сколько осталось деньги, сколько товаров купили) — в ней храним оптимум. теперь идем справа налево и пересчитываем — пробуем в данной позиции купить сколько нибудь товаров. чтобы быстро работало, надо: а) заметить, что за 1600 монет всегда можно скупить все что есть, б) для троек (позиция, сколько купили правее позиции, сколько покупаем в текущей позиции) сразу посчитать сколько мы заработаем.

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

у нас лично этот момент съел час контеста. не понимаю как некоторые команды сдали эту задачу с плюса.

U Для начала научимся решать задачу для отрезка [1, r]. Сгенерируем простые числа до k + 1. Найдем всевозможные числа, которые являются произведением этих простых(каждое простое входит со степенью 0 или 1). Их не много, т.к. нужны числа только до 2e9. Теперь найдем количество составных чисел по формуле включений-исключений. Формула очевидна, если нарисуете круги Эйлера.

В дорешивание залил примерно такое решение:

1. всего пар может быть (N=n*(n-1)/2), значит различий в 4 символа можно не считать. (c4=N-c1-c2-c3)

2. для каждой строки строим маски, заменяя символы на *, например для dead — *ead, d*ad, d**d, d***, и т.д. всего получается 14(4+6+4) масок. для этих масок, создаем массив счетчиков для вида маски и какую-то структуру счетчиков по самим маскам(например, хэш-таблица).

3. при добавлении в хэштаблицу новой маски, которая там уже была, текущий счетчик маски плюсуется к виду.

4. после считывания всех элементов, собираем счетчики видов в 3 группы(4+6+4). Нужно, еще учесть, что в 3 группе есть пересечения с 1 и 2 группами, а во второй пересечение с 1й группой. эти пересечения нужно вычесть, вначале из 2, потом из 3. Тут я рисовал табличку с масками и по ней искал пересечения.

http://pastebin.com/fTp4nRtT — вот такой код на Java получился

0.1 + 0.1 — 0.1 * 0.1

1.0 — (1.0 — 0.1) * (1.0 — 0.1)

P(A + B) = P(A) + P(B) — P(A * B) Формула очевидна, если нарисуете круги Эйлера.

вы видимо хранили в вершине дерева разбора d[v][i] — количество способов получить остаток i. Вот при пересчете для степени можно за O(p) для вершины посчитать, для суммы d[v][i] = d[left[v]][j] * d[right[v]][z], где (j + z) % p == i, так вот это можно посчитать с помощью FFT. А для умножения можно просто остаток заменить на степень, в которой первообразная равна этому остатку, тогда решение будет как и для суммы

Если вкратце, то в задаче B делаем так: 1) Разбили все по слоям с одинаковой интересностью. Понятно, что в ответ войдет ровно по 1ой клетке из каждого слоя. 2) Будем считать ответ последовательно для каждого слоя по возрастанию интересности. Динамика: d[i][j] — ответ на задачу, если закончили в клетке (i, j). Тогда её пересчет — это просто максимум по всем клеткам из предыдущего слоя (динамики + расстояние до (i, j)). Получили переход за линию — медленно. 3) Пусть посчитали iый слой, тогда сделаем следующую структуру данных в 4х экземплярах: будем поддерживать максимум из (d[i][j] + (n — i — 1) + (m — i — 1)) (для каждого угла формулка своя, но схожая, так что будем рассматривать только случай верхнего левого угла)на префиксном прямоугольнике с общим верхним углом в углу нашего поля(4 угла — 4 разных версии). Для этого подойдет, например, двумерный фенвик. 4) Теперь пересчет динамики будет таким: просто возьмем очередную точку из i+1 го слоя, она делит на 4 префиксных прямоугольника наше поле, в каждом из них найдем максимум в соотв. фенвике, и из них выберем максимум. Получили сложность решения n*log^2 и ТЛ cоотв. 5) Теперь можно избавится от одного log, просто заменив одну координату пересчетом с помощью указателей. Посортируем клетки из iго и i+1-го слоя по x, при равенстве по y. Тогда идем сканлайном, фенвик будет по y-кам. Еще один вариант: заменить фенвика на дерево отрезков сетов и применить каскадирование(для особо изощренных). Ответом будет максимум по всем клеткам d[i][j]. Насчет задачи K: Утверждается, что выгодно всегда убивать только по отрезкам, в которых выстрелы расположены через 1(точка — тоже отрезок). Тогда происходит несложная динамика d[i][j][0..2] — i клеток обработали, j выстрелов сделали, 0 — выстрелили на предыдущей клетке, 1 — на предпредыдущей, 2 — не стреляли. Переходим за 0(1). Получаем квадрат состояний, переходы за 0(1). Насчет доказательства факта: нужно показать, что не будет встречаться двух подряд идущих элемента. Если нестрого, то если встречаем три подряд, то средний можно выкинуть, а вместо пары можно сделать пару со свободной клеткой(в которую не стреляли) между ними.

Отлично! Не очень понятно почему это работает, но вроде интуитивно это ощущается :-)

Я правильно понимаю, что x_i - s_i это сколько минимум раз нам нужно обогнать не "вообще", а машинами с большими номерами?

Когда мы вычитаем min(mi, x_i - (i - pos) + 1), то этим мы как бы учитываем сразу несколько свопов машинки с номером pos и с номером i?

В E парсим выражение, считаем динамику по дереву разбора: dp[v][i] — сколько способов получить значение i в поддереве с корнем v. А пересчитывать динамику с помощью умножения полиномов быстрее чем за квадрат.

UPD: для суммы понятно как полиномы построить, а для умножения логарифмируем и получаем сумму. еще в умножении правильно учесть случай с нулем.

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

А за что заминусовали то? Дорешивание сейчас не работает.