Дана строка, составленная из круглых скобок. Определите, какое наименьшее количество символов необходимо удалить из этой строки, чтобы оставшиеся символы образовывали правильную скобочную последовательность.
Во входном файле записана строка из круглых скобок. Длина строки не превосходит \({100\,000}\) символов.
Выведите единственное целое число — ответ на поставленную задачу.
())(()
2
))(((
5
Петя в очередной раз купил себе набор из кубиков. На этот раз он выстроил из них настоящую крепость — последовательность из N столбиков, высота каждого столбика составляет Ai кубиков.
Вскоре ему стало интересно, насколько его крепость защищена от жуликов и воров. Для этого он ввел понятия башни. Башней называется любая последовательность из K столбиков подряд (где K — любимое число Пети). Защищенность башни определяется как суммарная высота всех столбиков этой башни (чем она больше, тем громаднее и ужаснее она кажется), умноженная на минимум высоты столбиков башни (т.к. враги, очевидно, будут пытаться проникнуть через самое слабое место башни). Неприступность крепости определяется как сумма защищенностей каждой из башен.
Петя решил как можно скорее посчитать, какова же неприступность его крепости. Однако вскоре он понял, что недостаточно знать высоту каждого из столбиков. В зависимости от того, как сгруппировать столбики в башни, получится разный результат. В различных вариантах группировки часть столбиков могут не принадлежать ни одной из башен. Разумеется, Петя выберет то разбиение на башни, при котором неприступность будет максимальна.
Петя успешно справился со своей задачей, но теперь Правительство Флатландии решило защитить свой горный курорт. Правительство уже построило крепость из кубиков (просто кубики были побольше). Теперь вы должны помочь Правительству посчитать неприступность этой крепости. Единственная трудность состоит в том, что у Правительства было очень много денег, и поэтому крепость была построена очень длинная.
В первой строке входного файла содержатся число N — количество столбиков в крепости и число K — любимое число Пети (1 ≤ K ≤ N ≤ 100 000). Далее на следующей строке содержатся N целых чисел, обозначающих Ai (1 ≤ Ai ≤ 106).
На первой строке выведите число Q — количество башен в оптимальном разбиении. Далее выведите Q чисел — номера первых столбиков каждой башни.
1 1 1
1 1
2 1 1 1000000
2 1 2
8 3 1 2 3 4 1 6 7 8
2 2 6
Представьте, что у вас есть автомобиль с очень большим бензобаком - достаточно большим, чтобы вместить любое необходимое количество бензина. Вы путешествуете по кольцевому маршруту, на котором есть некоторое число АЗС. Суммарное количество бензина на всех заправочных станциях в точности равно количеству бензина, необходимому для того, чтобы один раз проехать по маршруту. Когда вы приезжаете на заправочную станцию, вы заливаете весь бензин, который там есть, в свой бензобак. Изначально бак пуст, но гарантируется, что существует станция, с которой можно стартовать в некотором направлении (по часовой стрелке или против часовой стрелки) так, чтобы можно было один раз проехать по маршруту. Даны длина маршрута, расположение заправочных станций и для каждой станции количество километров, которое можно проехать на бензине с одной лишь этой АЗС. Требуется найти все возможные станции и направления старта, которые позволят совершить один круг по маршруту.
Входной файл содержит нескольно тестовых примеров (не более 50). Каждый тестовый пример начинается со строки, содержащей два положительных числа \(c\) и \(s\) (\(c \leq 100\,000\)): длину окружности (в километрах) и количество заправочных станций. Далее следуют \(s\) пар целых чисел \(t\) и \(m\). В каждой паре \(t\) - это целое число от \(0\) до \(c - 1\), означающее позицию этой АЗС, измеренную по часовой стрелке от некоторой произвольной фиксированной точки окружности, а \(m\) - это количество километров, которое можно проехать, используя весь бензин с этой станции. Все позиции различны. За последним тестовым примером следует пара нулей.
Для каждого тестового примера выведите его номер (в формате, показанном в примере), а затем список пар значений в виде \(i\) \(d\),
где \(i\) - это позиция заправочной станции, а \(d\) - это либо C либо CC, либо CCC, означающих, что, стартовав с пустым бензобаком, можно проехать по марштуту из позиции \(i\) по часовой стрелке (C) против часовой стрелки (CC) или в любом направлении
(CCC) и вернуться в позицию \(i\).
Станции нужно выводить в порядке возрастания позиции.
1 ≤ s ≤ 1 000. Решение оценивается в 40 баллов.
Дополнительные ограничения отсутствуют. Решение оценивается в 60 баллов.
10 4 2 3 4 3 6 1 9 3 5 5 0 1 4 1 2 1 3 1 1 1 0 0
Case 1: 2 C 4 CC 9 C Case 2: 0 CCC 1 CCC 2 CCC 3 CCC 4 CCC
В прямоугольной таблице клетки раскрашены в белый и черный цвета. Найти в ней прямоугольную область белого цвета, состоящую из наибольшего количества ячеек.
Во входном файле записана сначала высота \((N)\), а затем ширина \((M)\) таблицы \(((1 \le N \le 5000)\), \((1 \le M \le 5000))\), а затем записано \((N)\) строк по \((M )\) чисел в каждой строке, где \(0\) означает, что соответствующая клетка таблицы выкрашена в белый цвет, а \(1\) – что в черный.
В выходной файл вывести одно число — количество клеток, содержащихся в наибольшем по площади белом прямоугольнике.
5 6 1 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0
9
Формат XML является распространенным способом обмена данными между различными программами. Недавно программист Иванов написал небольшую программу, которая сохраняет некоторую важную информацию в виде XML-строки.
XML-строка состоит из открывающих и закрывающих тегов.
Открывающий тег начинается с открывающей угловой скобки (<), за ней следует имя тега — непустая строка из строчных букв латинского алфавита, а затем закрывающая угловая скобка (>). Примеры открывающих тегов: <a>, <dog>.
Закрывающий тег начинается с открывающей угловой скобки, за ней следует прямой слеш (/), затем имя тега — непустая строка из строчных букв латинского алфавита, а затем закрывающая угловая скобка. Примеры закрывающихся тегов: </a>, </dog>.
XML-строка называется корректной, если она может быть получена по следующим правилам:
Например, представленные ниже строки:
<a></a>
<a><ab></ab><c></c></a>
<a></a><a></a><a></a>
являются корректными XML-строками, а такие строки как:
<a></b>
<a><b>
<a><b></a></b>
не являются корректными XML-строками.
Иванов отправил файл с сохраненной XML-строкой по электронной почте своему коллеге Петрову. Однако, к сожалению, файл повредился в процессе пересылки: ровно один символ в строке заменился на некоторый другой символ.
Требуется написать программу, которая по строке, которую получил Петров, восстановит исходную XML-строку, которую отправлял Иванов.
Входной файл содержит одну строку, которая заменой ровно одного символа может быть превращена в корректную XML-строку. Длина строки лежит в пределах от 7 до 1000, включительно. Строка содержит только строчные буквы латинского алфавита и символы «<» (ASCII код 60), «>»(ASCII код 62) и «/»(ASCII код 47).
Строка во входном файле заканчивается переводом строки.
Выходной файл должен содержать корректную XML-строку, которая может быть получена из строки во входном файле заменой ровно одного символа на другой. Если вариантов ответа несколько, можно вывести любой.
Примеры входных и выходных файлов
|
input |
output |
|
<a></b> |
<a></a> |
|
<a><aa> |
<a></a> |
|
<a><>a> |
<a></a> |
|
<a/</a> |
<a></a> |