A. Feed with Candy

ограничение по времени на тест: 2 секунды

ограничение по памяти на тест: 256 мегабайт

ввод: стандартный ввод

вывод: стандартный вывод

Главный герой игры Cut the Rope — монстрик Ом Ном, который очень любит конфеты. По случайному совпадению, он же главный герой этой задачи.

Как-то раз Ом Ном зашел в гости к своему другу Эвану. В доме Эвана есть n конфет двух типов (леденцы и карамельки), i-я конфета висит на высоте hi сантиметров от пола дома и имеет массу mi. Ом Ном хочет съесть как можно больше конфет. В начале Ом Ном может прыгать не более, чем на x сантиметров в высоту. Когда Ом Ном съедает конфету массы y, он становится сильнее, и высота его прыжка увеличивается на y сантиметров.

Какое максимальное количество конфет сможет съесть Ом Ном, если он никогда не будет есть подряд две конфеты одного и того же типа (Ом Ном считает, что это слишком скучно)?

Входные данные

В первой строке записаны два целых числа n и x (1 ≤ n, x ≤ 2000) — количество конфет в доме Эвана и начальная высота прыжка Ом Нома.

В каждой из следующих n строк записаны три целых числа ti, hi, mi (0 ≤ ti ≤ 1; 1 ≤ hi, mi ≤ 2000) — тип, высота и масса i-й конфеты. Если число ti равно 0, то текущая конфета — это карамелька, иначе текущая конфета — это леденец.

Выходные данные

Выведите единственное целое число — максимальное количество конфет, которое сможет съесть Ом Ном.

Примеры тестов

входные данные
5 3
0 2 4
1 3 1
0 8 3
0 20 10
1 5 5

выходные данные 4

Примечание

Один из возможных способов съесть 4 конфеты — есть конфеты в порядке: 1, 5, 3, 2. Рассмотрим подробнее такое развитие событий:

1. Изначально высота прыжка Ом Нома равна 3. Он может допрыгнуть до конфет 1 и 2. Допустим, что он съест конфету 1. Так как масса этой конфеты равна 4, высота его прыжка станет равна 3 + 4 = 7.
2. Теперь Ом Ном может допрыгнуть до конфет 2 и 5. Допустим, что он съест конфету 5. Тогда высота его прыжка станет равна 7 + 5 = 12.
3. В данный момент Ом Ном может допрыгнуть до двух конфет: 2 и 3. Есть конфету 2 он не будет, так как ее тип совпадает с предыдущей съеденной конфетой. Ом Ном съедает конфету 3, высота его прыжка становится равна 12 + 3 = 15.
4. Ом Ном съедает конфету 2, высота его прыжка становится равна 15 + 1 = 16. До конфеты 4 он допрыгнуть не может.

Решение:

В задача А типы съеденных конфет должны все время менятся. Так что первая съеденная конфета определяет тип всех последующих конфет. Возможных типа всего два, так что переберем тип первой съеденной конфеты. Пусть в какой-то момент времени Ом Ном должен съесть конфету типа t и может прыгать на высоту h. Очевидно, что наиболее выгодным решением будет съесть конфету с наибольшей массой среди всех конфет, которые Ом Ном может съесть на текущем этапе. Для решения задачи необходимо промоделировать процесс поедания конфет для начального h = x и t = [0, 1] и выбрать лучшее значение

B. Om Nom and Spiders

ограничение по времени на тест: 3 секунды

ограничение по памяти на тест: 256 мегабайт

ввод: стандартный ввод

вывод: стандартный ввод

Ом Ном очень любит конфеты и очень не любит пауков, поскольку последние частенько воруют конфеты. Как-то раз Ом Ном собрался на прогулку по парку. К сожалению, в парке водятся пауки, видеть которых Ом Ном совсем не хочет.

Парк можно представить как клетчатое поле n × m. В парке есть k пауков, каждый паук в момент времени 0 находится в некоторой клетке поля. Пауки все время двигаются, причем каждый паук всегда двигается в каком-то одном из четырех направлений (влево, вправо, вниз, вверх). За единицу времени паук из своей клетки переползает в соседнюю по стороне клетку в соответствующем направлении. Если в этом направлении клетки нет, то он покидает территорию парка. Пауки не мешают друг другу во время передвижения, в частности, в одно и то же время в одной клетке могут находиться несколько пауков.

Ом Ном еще не определился, откуда он начнет свою прогулку, но он точно хочет:

• начать прогулку в момент времени 0 в одной из клеток верхней строки клетчатого поля (клетки этой строки гарантированно не содержат пауков);
• во время всей прогулки двигаться вниз по полю по направлению к нижней строке (прогулка закончится, когда Ом Ном выйдет за пределы парка).

Ом Ном, как известно, передвигается прыжками. Один прыжок длится одну единицу времени и перемещает монстрика со своей клетки в соседнюю по стороне клетку поля следующей вниз строки, либо за пределы парка.

Каждый раз когда Ом Ном приземляется в какой-то клетке, он видит всех пауков, которые пришли в эту клетку в этот момент времени. Ом Ном хочет выбрать оптимальную клетку для начала прогулки. Поэтому ему интересно для каждой возможной стартовой клетки узнать, сколько пауков он увидит в процессе прогулки, если начнет из этой клетки. Помогите ему, посчитайте это количество для каждой возможной стартовой клетки.

Входные данные

В первой строке записано три целых числа n, m, k (2 ≤ n, m ≤ 2000; 0 ≤ k ≤ m(n - 1)). Каждая из n следующих строк содержит m символов — описание парка. Символы, находящиеся в i-й строке, описывают i-ю строку клетчатого поля парка. Если символ в строке равен «.» — это значит, что соответствующая клетка поля пустая; иначе символ в строке будет равен одному из четырех символов: «L» (обозначает, что в этой клетке в момент времени 0 находится паук, который двигается влево), «R» (паука, который двигается вправо), «U» (паука, который двигается вверх), «D» (паука, который двигается вниз).

Гарантируется, что первая строка не сдержит пауков. Гарантируется, что никаких лишних символов описание поля не содержит. Гарантируется, что на поле в момент времени 0 находится ровно k пауков.

Выходные данные

Выведите m целых чисел: j-е число должно обозначать количество пауков, которое увидит Ом Ном, если начнет свою прогулку из j-й клетки первой строки. Клетки в строке клетчатого поля нумеруются слева направо.

Примеры тестов

входные данные
3 3 4
...
R.L
R.U

выходные данные
0 2 2

входные данные
2 2 2
..
RL

выходные данные
1 1

входные данные
2 2 2
..
LR

выходные данные
0 0

входные данные
3 4 8
....
RRLL
UUUU

выходные данные
1 3 3 1

входные данные
2 2 2
..
UU

выходные данные
0 0

Примечание

Рассмотрим первый тестовый пример. Ниже показано, как будет меняться расположение пауков на поле в течение времени:

...		...		..U		...
R.L	->	.*U	->	L.R	->	...
R.U		.R.		..R		...

Символом «*» обозначена клетка, в которой находятся два паука одновременно.

• Если Ом Ном начнет свой путь в первой клетке первой строки, тогда не вовсе не увидит пауков.
• Если он начнет свой путь во второй клетке, тогда он увидит двух пауков в момент времени 1.
• Если он начнет свой путь в третьей клетке, тогда он увидит двух пауков: одного в момент времени 1, а второго в момент времени 2.

Решение:

Пронумеруем столбцы таблицы начиная с 0 слева направа, а строки начиная с 0 сверху вниз. Теперь заметим, что в момент времени t > 0 в клетке (x, y) могут находиться только 4 паука:

• Паук, который движется влево и в начале был в клетке (x, y + t).
• Паук, который движется вправо и в начале был в клетке (x, y - t).
• Паук, который движется вниз и в начале был в клетке (x - t, y).
• Паук, который движется вверх и в начале был в клетке (x + t, y).

Давайте переберем столбец в котором Ом Ном начнет свой путь. Пусть это столбец y. В момент времени 0 все пауки стоят на своих исходных позициях, а Ом Ном стоит в клетке (0, y). Так как на нулевой строке нет пауков, то в момент времени 0 Ом Ном их точно не встречает. Когда Ом Ном находится в клетке (x, y), это значит, что с момента начала движения прошло x единиц времени. Следовательно, для того, чтобы вычислить сколько пауков Ом Ном встретим в этой клетке, необходимо проверить лишь 4 клетки, указанные выше, на наличие паука, движущегося в нужном направлении.

C. Dungeons and Candies

ограничение по времени на тест: 2 секунды

ограничение по памяти на тест: 256 мегабайт

ввод: стандартный ввод

вывод: стандартный ввод

Во время запуска игры «Dungeons and Candies» требуется получить по сети от сервера описания k уровней игры. Каждое описание — карта клетчатого прямоугольного поля n × m, в клетках которого расположены конфеты (в каждой клетке находится не более одной конфеты). Пустая клетка обозначается символом «.», если же в клетке находится конфета, то она кодируется буквой латинского алфавита. Уровень может содержать одинаковые конфеты, в таком случае буквы в соответствующих клетках карты будут одинаковы.

При передачи по сети требуется минимизировать трафик — суммарный размер переданных данных. Уровни можно передавать в любом порядке. Существует два способа передать очередной уровень A:

1. Можно передать уровень A целиком. Этот способ требует передачи n·m байтов по сети.
2. Можно передать разницу между уровнем A и каким-то ранее переданным уровнем B, если такой существует; эта операция требует передачи dA, B·w байтов, где dA, B обозначает количество клеток поля, которые отличаются в A и B, а w — константа. Обратите внимание, что при вычислении dA, B сравниваются соответствующие друг другу клетки уровней A и B. При этом карты уровней нельзя преобразовывать, например, поворачивать или смещать относительно друг друга.

Ваша задача — найти способ передать все k уровней, минимизировав трафик.

Входные данные

В первой строке записаны четыре целых числа n, m, k, w (1 ≤ n, m ≤ 10; 1 ≤ k, w ≤ 1000). Далее следует описание k уровней. Каждый уровень описывается n строками, в каждой из которых записано m символов. Каждый символ — это либо буква латинского алфавита, либо точка («.»). Обратите внимание, что регистр букв имеет значение.

Выходные данные

В первой строке выведите искомое минимальное количество переданных байтов.

Далее выведите k пар целых чисел x1, y1, x2, y2, ..., xk, yk, описывающих способ передачи уровней. Пара xi, yi обозначает, что уровень xi нужно передавать способом yi. Если yi равно 0, значит, уровень нужно передавать первым способом, иначе yiдолжно быть равно номеру ранее переданного уровня, разницу по сравнению с которым нужно передать. Пары выводите в порядке передачи уровней. Уровни пронумерованы от 1 до k в порядке их описания во входных данных.

Если существует несколько оптимальных решений, разрешается вывести любое.

Примеры тестов

входные данные
2 3 3 2
A.A
...
A.a
..C
X.Y
...

выходные данные
14
1 0
2 1
3 1

входные данные
1 1 4 1
A
.
B
.

выходные данные
3
1 0
2 0
4 2
3 0

входные данные
1 3 5 2
ABA
BBB
BBA
BAB
ABB

выходные данные
11
1 0
3 1
2 3
4 2
5 1

Решение:

Давайте рассмотрим неориентированный взвешенный граф, в котором k + 1 вершина. Пронумеруем вершины целыми числами от 0 до k. Вершины c 1 по k будут соответствовать уровни. Для каждой пары уровней i и j добавим ребро из i в j стоимость которого равно стоимости передачи одного уровня как разность с другим. Так же для каждого уровня i добавим ребро между вершиной 0 и i стоимости n·m, т.е. стоимости передачи уровня целиком. Каждый способ передать все уровни соответсвует остовному дереву в указанном графе. Таким обзаром необходимо вывести минимальное остовное дерево в этом графе.

D. Pudding Monsters

ограничение по времени на тест: 5 секунд

ограничение по памяти на тест: 256 мегабайт

ввод: стандартный ввод

вывод: стандартный ввод

Вы когда-нибудь играли в Pudding Monsters? В этой задаче используется упрощенная одномерная модель этой игры.

Представьте себе бесконечную клетчатую полоску, клетки которой пронумерованы последовательно целыми числами. В некоторых клетках полоски стоят монстры, остальные клетки полоски пустые. Все монстры состоят из пудинга, поэтому, если два монстра стоят в соседних клетках полоски, то они склеиваются. Аналогично, если несколько монстров стоят подряд, то все они склеиваются в один блок монстров. Будем называть склеенных друг с другом монстров блоком монстров. Отдельно стоящий монстр, не склеенный ни с кем другим, также считается блоком.

За один ход игрок может взять любой блок монстров и движением руки швырнуть его влево или вправо. Выбранные монстры будут скользить до тех пор, пока не упрутся в какого-то другого монстра (или блок монстров).

Например, если на полоске стоят три монстра в клетках 1, 4 и 5. Тогда возможны только четыре хода: отправить монстра в клетке 1 в минус бесконечность, отправить блок монстров в клетках 4 и 5 в плюс бесконечность, швырнуть монстра 1 вправо (он остановится в клетке 3), швырнуть блок монстров в клетках 4 и 5 влево (они остановятся в клетках 2 и 3).

Некоторые клетки отмечены звездами. Это особенные клетки. Цель игры — сделать так, чтобы на максимально возможном количестве особенных клеток стояли монстры.

Вам заданы номера особенных клеток полоски, а также начальное положение всех монстров. Какое максимальное количество особых клеток можно занять монстрами?

Входные данные

В первой строке записаны два целых числа n и m (1 ≤ n ≤ 105; 1 ≤ m ≤ 2000) — количество монстров на полоске и количество особенных клеток.

Во второй строке записаны n различных целых чисел — номера клеток с монстрами, в третьей строке записаны m различных целых чисел — номера особенных клеток. Гарантируется, что все номера клеток целые положительные числа не превышающие 2·105.

Выходные данные

Выведите единственное целое число — максимальное количество особых клеток, которое можно занять монстрами.

Примеры тестов

входные данные
3 2
1 3 5
2 4

выходные данные
2

входные данные
4 2
1 3 4 6
2 5

выходные данные
2

входные данные
4 2
1 8 4 5
7 2

выходные данные
1

Решение:

Задача решается при помощи динамического программирования. Введем обозначения: sum(l, r) — количество особых клеток на отрезке с l по r, zi — максимальное количество особых клеток, которые можно покрыть, используя только первые iмонстров при условии, что i-тый монстр либо остается на месте, либо отправляется влево, di--- максимальное количество особых клеток, которые можно покрыть, используя только первые i монстров при условии, что i-тый монстр остается на месте.

Рассмотрим процесс вычисления di. Пусть i-тый монстр находится в клетке r. Переберем самую левую особую клетку, которая будет покрыта блоком монстров, в котором будет находиться i-й монстр. Пусть эта особая клетка находится в клетке l. Тогда нам требуется r - l дополнительных монстров отправить вправо для того, чтобы покрыть эту особую клетку. Тогда ответ будет равен zi - (r - l) + sum(l, r). Для вычисления di надо взять максимум по всем особым клеткам, левее i-того монстра.

Теперь, после того, как мы вычислили очередное значение di, необходимо обновить некоторые значения zj. Пусть i-тый монстр находится в клетке l. Переберем самую правую особую клетку, которая будет покрыта блоком монстров, в котором будет находиться i-й монстр. Пусть эта особая клетка находится в клетке r. Тогда нам требуется r - l дополнительных монстров отправить влево для того, чтобы покрыть эту особую клетку. Тогда, zi + (r - l) можно обновить следующим значением di + sum(l + 1, r). Так же необходимо не забыть обновить значение zi значением zi - 1.

Как можно видеть это решение имеет сложность O(n·m), так как для каждого из n монстров мы перебираем все m особых клеток, а все вычисления при фиксированной паре монстр-клетка проходят за O(1).

При реализации могут возникнуть небольшие тонкости, связанные с монстрами, которые уже в начальном состоянии слиплись в один блок.

E. Cardboard Box

ограничение по времени на тест: 5 секунд

ограничение по памяти на тест: 256 мегабайт

ввод: стандартный ввод

вывод: стандартный ввод

Все, кто играли в Cut the Rope, хорошо знают, как организовано прохождение игры. В игре все уровни разделены на коробки. Изначально доступна только одна коробка с несколькими уровнями. За прохождение уровней игрок зарабатывает звезды, по мере накопления звезд открываются новые уровни.

Представьте, что вы впервые играете в Cut the Rope. В данный момент вам доступны только уровни из первой коробки (кстати, она называется «Cardboard Box»). Каждый уровень характеризуется двумя целыми числами: ai — сколько требуется времени, чтобы пройти уровень на одну звезду, bi — сколько требуется времени, чтобы пройти уровень на две звезды (ai < bi).

Вы хотите как можно быстрее открыть следующую коробку с уровнями, для чего требуется заработать как минимум w звезд. Каким образом нужно действовать, чтобы это сделать? Обратите внимание, что проходить уровень можно только один раз: либо на одну звезду, либо на две. Необязательно проходить все уровни.

Входные данные

В первой строке записаны два целых числа n и w (1 ≤ n ≤ 3·105; 1 ≤ w ≤ 2n) — количество уровней в первой коробке и количество звезд, которое требуется, чтобы открыть следующую коробку. В каждой из следующих n строк записаны два целых числа ai и bi (1 ≤ ai < bi ≤ 109) — характеристики i-го уровня.

Выходные данные

В первой строке выведите целое число t — минимальное время, которое требуется, чтобы открыть следующую коробку.

В следующей строке выведите n цифр без пробелов — описание оптимального плана действий:

• если i-й уровень нужно пройти на одну звезду, i-я цифра должна быть равна 1;
• если i-й уровень нужно пройти на две звезды, i-я цифра должна быть равна 2;
• если i-й уровень вовсе не нужно проходить, i-я цифра должна быть равна 0.

Примеры тестов

входные данные
2 3
1 2
1 2

выходные данные
3
12

входные данные
5 3
10 20
5 10
10 20
6 9
25 30

выходные данные
14
01020

Примечание

В первом тестовом примере ответ 21 также считается правильным.

Решение:

В задаче E нужно было написать правильную жадность. Правильных жадностей существует несколько, вот одна из них:

• Посмотрим на некоторый оптимальный ответ (набор как-то пройденных уровней). Отсортируем все уровни по b[i]. Если рассмотреть последний взятый в ответ уровень, пройденный на 2 звезды, то окажется, что все находящиеся до него в таком порядке уровни пройдены хотя бы на одну звезду. Иначе, можно было бы заменить этот уровень на какой-то не пройденный и не увеличить ответ.
• Пользуясь вышесказанным, зафиксируем префикс L уровней в порядке сортировки по b[i]. Все уровни этого префикса мы должны хоть как-то пройти (либо на 1, либо на 2 звезды). Дополнительно, будет считать, что все уровни пройденные на 2 звезды должны содержаться только в этом префиксе (такой префикс должен существовать для некоторого оптимального ответа, как было показано ранее).
• Так как мы зафиксировали префикс длиной L уровней, которые мы точно хоть как-то пройдем, можно сказать, что нам осталось добрать w - L звезд. Как мы можем добирать эти звезды? Либо допроходить какие-то уровни из префикса L на 2 звезды, либо проходить уровни не из префикса L на одну (потому что уровни, которые мы проходим на 2 звезды должны содержаться только на зафиксированном префиксе).
• Понятно, что для того, чтобы получить оптимальный ответ нужно выбрать w - L самых дешевых звезд. Поэтому отсортируем n элементов: L чисел b[i] - a[i] (для всех i ≤ L), n - L чисел a[i] (для всех i > L). Выберем среди этих чисел w - Lминимальных.

Описанное нужно было реализовывать быстрее, чем за квадрат. Самая очевидная реализация использует декартово дерево, чуть менее очевидная использует дерево отрезков.

Итоговая сложность решения: O(n log n).

F. Banners

ограничение по времени на тест: 5 секунд

ограничение по памяти на тест: 512 мегабайт

ввод: стандартный ввод

вывод: стандартный вывод

Все современные мобильные приложения делятся на платные и бесплатные. Даже разработчики одного приложения часто выпускают две версии: платную версию без рекламы и бесплатную версию с рекламой.

Предположим, что платная версия приложения стоит p (p — целое число) рублей, а бесплатная версия приложения содержит c рекламных баннеров. Каждого пользователя можно охарактеризовать двумя целыми числами: ai — сколько рублей этот пользователь не пожалеет за платную версию приложения, и bi — сколько баннеров он готов терпеть в бесплатной версии приложения.

Поведение каждого пользователя будем считать строго детерминированным:

• если для пользователя i значение bi не меньше c, тогда он пользуется бесплатной версией,
• иначе, если значение ai не меньше p, то он покупает платную версию без рекламы,
• иначе пользователь просто не пользуется приложением.

Каждый пользователь бесплатной версии приложения приносит прибыль c × w рублей. Каждый пользователь платной версии приложения приносит прибыль p рублей.

Ваша задача — помочь разработчикам приложения оптимально выбрать параметры p и c. А именно, считая, что известны все характеристики пользователей, для каждого значения c от 0 до (max bi) + 1 определить максимальную прибыль от приложения и соответствующий параметр p.

Входные данные

В первой строке записаны два целых числа n и w (1 ≤ n ≤ 105; 1 ≤ w ≤ 105) — количество пользователей и прибыль с одного баннера. В каждой из следующих n строк записано два целых числа ai и bi (0 ≤ ai, bi ≤ 105) — характеристики i-го пользователя.

Выходные данные

Выведите (max bi) + 2 строки, в i-й строке выведите два целых числа: pay — максимальная полученная прибыль при c = i - 1, p(0 ≤ p ≤ 109) — соответствующая оптимальная стоимость. Если существует несколько оптимальных решений, разрешается вывести любое.

Примеры тестов

входные данные
2 1
2 0
0 2

выходные данные
0 3
3 2
4 2
2 2

входные данные
3 1
3 1
2 2
1 3

выходные данные
0 4
3 4
7 3
7 2
4 2

Решение:

Задача F была самой сложной задачей контеста. Чтобы лучше представить себе ее решение, можно перейти к геометрическому представлению задачи. Представим, что люди — это точки на плоскости Opc, тогда, то что требуется найти — для каждой прямой c = i, такую прямую p = j, что некоторая функция принимает максимальное значение. Под некоторой функцией понимается следующая: (количество точек не ниже прямой c = i умножить на w·i) плюс (количество точек ниже прямой c = i и не левее прямой p = j умножить на j).

Будем двигать сканирующую прямую снизу вверх. Сначала рассматриваем c = 0, затем c = 1 и так далее. При этом для каждого p будем хранить величину d[p] — чему равен ответ на задачу при текущем c, если второй параметр будет равен p. Если у нас есть корректно посчитанный массив d[] и мы переходим от c к c + 1, как пересчитать этот массив для нового c?

Посмотрим на всех людей, для которых хоть что-то поменяется, очевидно — это люди у которых b[i] = c. При текущем c они еще пользовались бесплатной версией, но после увеличения на 1, они перестанут ей пользоваться. Понятно, что каждый такой человек i модифицирует массив следующим образом: d[1] +  = 1, d[2] +  = 2, ..., d[b[i]] +  = b[i].

Теперь можно переформулировать задачу в терминах структур данных. Есть два вида запросов: прибавить на префиксе возрастающую арифметическую прогрессию, узнать максимум среди всех элементов массива d. Один из способов решить такую задачу — корневая декомпозиция.

Разобьем все запросы на группы по sqrt(q) штук, в каждой группе выделим отрезки, на которых к ячейке d[i] значение iприбавляется с одним и тем же коэффициентом. Для каждого такого отрезка построим нижнее огибающее множество прямых y = d[i] + i·x. Так как запросов в группе sqrt(q), то и отрезков будет O(sqrt(q)). Значит прибавление на префиксе и взятие максимума можно будет делать за O(sqrt(q)).

Итоговая сложность решения: O(MAXX·sqrt(MAXX)), где MAXX — максимальное значение среди a[i] и b[i].