Информатика

7 592 задачивместе с подтемами

Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.

РейтингЛюбой до 800 800–1199 1200–1599 1600+Без рейтинга

СначалаПодходящие Новые Популярные Простые Сложные

Perimeter#89872

Фермер Джон выстроил N (1 <= N <= 10,000) стогов сена в одном из своих полей. Мы рассмотрим это поле как решетку 100 х 100 из квадратных ячеек 1 х 1, где каждый стог сена занимает ровно одну ячейку. Никакие два стога не находятся в одной и той же ячейке.

ФД заметил, что его стоги всегда образуют один большой связный регион, что означает, что начиная с любого стога сена можно достичь любого другого стога сена с помощью серии шагов в строго соседнюю клетку в одном из четырех направлений: север, юг, запад, восток.
Однако этот связный регион может содержать "дыры" - пустые регионы, которые полностью окружены стогами.
Помогите ФД определить периметр региона, сформированный его стогами. Учитывайте, что дыры не вносят вклад в периметр.
PROBLEM NAME: perimeter
Формат входных данных
* Строка 1: Количество стогов, N.
* Строки 2..1+N: Каждая строка содержит(x,y) - положение одного стога где x и y целые числа в диапазоне 1..100. Позиция (1,1) это левый нижний угол поля ФД, а позиция (100,100) это правый верхний угол поля.
Формат выходных данных
* Строка 1: периметр связного региона стогов.
Примечание
Длина периметра равна 14, например левая сторона имеет длину 3. Заметьте, что дыра в середине не вносит значение в периметр.

Поиск компонент связности

—Войти и решать

Cow Crossings#89870

Каждый день N (1 <= N <= 100,000) коров Фермера Джона переходят дорогу, расположенную в середине фермы. Рассмотрим карту фермы Джона на 2D-плоскости, дорога идет горизонтально, одна сторона дороги описывается прямой y=0, другая - прямой y=1.
Корова i пересекает дорогу, следуя по прямой из позиции (a_i,0) на одной стороне в позицию (b_i,1) на другой стороне. Все a_i различны, так же как и все B_i. И все эти числа находятся в диапазоне -1,000,000...1,000,000.
ФД называет переход безопасным, если он не пересекается никакими другими переходами. Помогите ФД подсчитать количество безопасных переходов.
PROBLEM NAME: crossings
Формат входных данных
* Строка 1: Количество коров, N.
* Строки 2..1+N: Строка i содержит целые числа a_i и b_i, описывающие путь коровы i.
Формат выходных данных
* Строка 1: Количество безопасных переходов.
Примечание
Переходы первой и третьей коров не пересекаются переходами никаких других коров. Переходы второй и четвертой коров пересекают друг друга.

Использование сортировки

—Войти и решать

The Bessie Shuffle#89868

Беси тренируется делать карточные трюки. Она уже освоила уникальный
способ тасования M (2 <= M <= 100,000) карт так, чтобы i-ая карта сверху
становилась p[i] картой сверху.

Теперь она переходит в бОльшим колодам.
У Беси имеется колода из N карт (M<=N<=100,000), последовательно
пронумерованных 1..N. Она тасует её следующим образом: берёт первые M
карт и выполняет описанное выше тасование. И возвращает эти M карт
наверх колоды. Затем она забирает верхнюю карту из колоды и размещает
её значением вниз. Она продолжает этот процесс, выкладывая верхние
карты последовательно поверх друг друга, пока у неё не закончатся карты.
Когда у Беси становится карт меньше чем M, она больше не выполняет
тасование, но размещать верхнюю карту поверх ранее выложенных.

Беси знает, что изначально колода находится в отсортированном порядке с 1
наверху, потом 2 и т.д. N в конце. Вам задано описание тасования Беси.
Помогите Беси вычислить, какие карты окажутся на Q (1 <= Q <= N,
Q <= 5,000) указанных различных позициях в колоде.

PROBLEM NAME: shuffle

Формат входных данных

* Строка 1: Одна строка, содержащая N, M Q разделённые одиночными
пробелами

* Строки 2..1+M: Строка i+1 указывает позицию сверху P[i], i-ой карты в
тасовании Беси (1 <= P[i] <= M).

* Строки 2+M..1+M+Q: Строка i+1+M содержит одно целое число q_i
Описывающее i-ый запрос. Вы должны вычислить значение карты
неа позиции q_i сверху (1 <= q_i <= N).

Формат выходных данных

* Строки 1..Q: В i-ой строке, выведите одно целое число – значение карты
на позиции q_i сверху колоды по завершению процесса.

Примечание

Процесс протекает следующим образом

[1, 2, 3, 4, 5] -> [2, 3, 1, 4, 5] (выложить 2 значением вниз)
[3, 1, 4, 5] -> [1, 4, 3, 5] (выложить 1 значением вниз)
[4, 3, 5] -> [3, 5, 4] (выложить 3 значением вниз)
[5, 4] (выложить 5 значением вниз)
[4] (выложить 4 значением вниз)

Итого финальный порядок такой [4, 5, 3, 1, 2]

Задачи на моделирование

—Войти и решать

Milk Scheduling#89867

У Фермера Джона есть N (1 <= N <= 10,000) коров, которых нужно подоить.
Каждая дойка занимает ровно одну единицу времени.

Некоторые коровы не любя долго ждать дойки.
Точнее корова I производит g_i галлонов молока (1<=g_i<=1000),
но только если её подоить до её дед-лайна – d_i (1<=d_i<=10,000).
Время начинается в момент t=0.
Поэтому не более x коров может быть подоено до дед-лайна t=x.

Помогите ФД определить максимальное количество молока,
которое он может получить, если установить оптимальный порядок дойки коров.

PROBLEM NAME: msched

Формат входных данных

* Строка 1: Значение N.

* Строки 2..1+N: Строка i+1 содержит целые числа g_i и d_i.

Формат выходных данных

* Строка 1: Максимальное количество галлонов молока, которое может
получить ФД

Примечание

ФД сначал подоит корову 3, не будет доить корову 4, поскольку её
дед-лайн конфликтует с коровой 3. Затем ФД подоит коров 1 и 2.

Жадный алгоритм

—Войти и решать

The Bessie Shuffle (gold)#89865

Беси практикуется в карточных фокусах. Она уже освоила Беси-тасование – тасование M (2 <= M <= 100,000) карт, так чтобы i-ая карта сверху становилась P[i]-ой картой сверху.
Теперь она переходит на бОльшие колоды. У неё есть колода из N (M <= N <= 1,000,000,000) карт, последовательно пронумерованных от 1 до N. Она тасует её следующим образом: берёт первые M карт, и выполняет их Беси-тасование, затем снова кладёт их наверх колоды. Далее она удаляет верхнюю карту из колоды и кладёт ее на стол значением вниз. Она повторяет этот процесс, выкладывая забираемые карты поверх друг друга, пока карты не кончатся. Когда у неё в исходной колоде остаётся меньше чем M карт, она прекращает выполнять Беси-тасование, но продолжает брать верхнюю карту и выкладывать её поверх ранее взятых.
Беси знает, что изначально колода находится в отсортированном порядке, Причём карта 1 наверху, карта 2 следующая и т.д. По заданному описанию Беси-тасования, вычислите какие карты окажутся на Q (1 <= Q <= N, Q <= 5,000) различных указанных позициях колоды.
В 50% тестов N<=100,000.
PROBLEM NAME: shufflegold
Формат входных данных
* Строка 1: Числа N, M и Q разделенные одиночными пробелами
* Строки 2..1+M: Строк i+1 указывает позицию сверху колоды, P[i], на которую переместиться i-ая карта после Беси-тасования (1 <= P[i] <= M).
* Строки 2+M..1+M+Q: Строка i+1+M содержит одно целое число q_i описывающее i-ый запрос. Вы должны вычислить значение на карте, которая окажется в позиции q_i сверху (1 <= q_i <= N).
Формат выходных данных
* Строки 1..Q: На i-ой строке, выведите одно целое число, указывающее карту, которая окажется на позиции q_i сверху.
Примечание
Тасование происходило так
[1, 2, 3, 4, 5] -> [2, 3, 1, 4, 5] (выкладываем 2 значением вниз) [3, 1, 4, 5] -> [1, 4, 3, 5] (выкладываем 1 значением вниз) [4, 3, 5] -> [3, 5, 4] (выкладываем 3 значением вниз) [5, 4] (выкладываем 5 значением вниз) [4] (выкладываем 4 значением вниз)
Финальный расклад [4, 5, 3, 1, 2]

Задача на реализацию

—Войти и решать

Optimal Milking#89864

Фермер Джон купил новый амбар, содержащий N (1 <= N <= 40,000) доильных машин, последовательно пронумерованных от 1 до N и расположенных в ряд.
Доильная машина i способна извлекать по M(i) (1 <=M(i) <= 100,000) единиц молока в день. Однако, они установлены так близко, что, если машина I используется в какой-то день, то в этот день не могут быть использованы две соседние машины (начальная и конечная машина имеют по одному соседу). ФД может выбирать различные подмножества работающих машин в различные дни.
ФД хочет вычислить максимальное количество молока, которое он может извлечь за серию из D(1 <= D <= 50,000) дней. В начале каждого дня у него есть достаточное количество времени, чтобы выполнить модификацию одной выбранной машины I, и изменить дневной выпуск молока этой машины от прошлого дня к сегодняшнему. Вам дан список этих ежедневных модификаций, определите, сколько молока может извлечь ФД в течение D дней (заметим, что это число может не вместиться в 32-битное целое).
PROBLEM NAME: optmilk
Формат входных данных
* Строка 1: Значения N и D.
* Строки 2..1+N: Строка i+1 содержит начальное значение M(i).
* Строки 2+N..1+N+D: Строка 1+N+d содержит два целых числа i и m, означающие, что ФД изменил значение M(i) на m в начале дня d.
Формат выходных данных
* Строка 1: Максимальное суммарное количество молока, которое ФД сможет произвести за D дней.
Примечание
В день 1 оптимальное количество молока 2+4 = 6 (также достижимое как 1+3+2). В день 2 оптимальное количество молока 7+4=11. В день 3 оптимальное количество молока 10+3+2=15.

Дерево отрезков, RSQ, RMQ

—Войти и решать

Wormholes#89863

Фермер Джон имеет хобби, связанное с физикой высоких энергий. В результате чего на его ферме образовалось N (2 <= N <= 12, N чётное) Дыр, каждая из которых расположена в различной точке на 2D-карте его фермы.
ФД знает, что эти дыры формируют N/2 связанных пар. Например, если A и B такая связанная пара, то любой объект, попавший в точку A Перемещается в точку B, двигаясь в этом направлении, а любой объект, попавший в точку B аналогично перемещается в точку A. Это может Иметь неприятные последствия, например, предположим, что имеется пара A в точке (0,0) и B в точке (1,0). Пусть Беси начинает из позиции (1/2,0) двигаясь по оси X в положительном направлении. Беси войдёт в точку B выйдет из A, затем попадёт в точку B опять и т.д. – то есть она попадает в бесконечный цикл!
ФД знает точное расположение каждой дыры на его ферме. Он знает, что Беси это корова, которая всегда гуляет в +x направлении, но он не знает точные координат Беси в текущий момент. Посчитайте количество различных пар дыр таких, что образуют для Беси бесконечный цикл, если она стартует из неудачной позиции.
PROBLEM NAME: wormhole
Формат входных данных
* Строка 1: количество дыр, N.
* Строки 2..1+N: Каждая строка содержит два разделённых пробелом целых числа, описывающих (x,y) координаты одной дыры. Каждая координата в диапазоне 0..1,000,000,000.

Формат выходных данных
* Срока 1: Количество различных пар дыр таких, что образуют для Беси бесконечный цикл, если она стартует из неудачной позиции и будет двигаться в +x направлении.

Примечание
Если мы пронумеруем дыры 1..4, то и сформируем две пары 1 и 2, 3 и 4. Беси попадёт в цикл, начиная из любой из точек из интервала (0,0) – (1,0) или из интервала (0,1) – (1,1). Аналогично, из тех же стартовых точек Беси попадёт в цикл, если мы сформируем пары 1-3, 2-4. Только пары 1-4 и 2-3 позволяют Беси двигаться в +x направлении из любой из точек плоскости, не имея возможности попасть в цикл.

—Войти и решать

Record Keeping#89862

Фермер Джон детально записывает порядок прихода коров на дойку. Каждый час группа из трёх коров входит в амбар и ФД записывает их имена. Например, за 5 часов он имеет такой список, где каждая строка соответствует группе вошедших коров:
BESSIE ELSIE MATILDA FRAN BESSIE INGRID BESSIE ELSIE MATILDA MATILDA INGRID FRAN ELSIE BESSIE MATILDA
ФД заметил, что одна и та же группа коров может несколько раз появляться в этом списке. Например, группа BESSIE, ELSIE и MATILDA появляется три раза (ФД необязательно записывает их имена в одинаковом порядке при каждом входе в амбар).
Помогите ФД посчитать количество приходов той группы, которая пришла наибольшее количество раз.
PROBLEM NAME: records
Формат входных данных
* Строка 1: Количество часов, N, в течение которых ФД вёл запись (1 <= N <= 1000).
* Строки 2..1+N: Каждая строка содержит список из трёх разделенных одиночными пробелами имён. Каждое имя имеет длину от 1 до 10 символов и стоит только из символов A-Z.

Формат выходных данных
* Строка 1: Количество приходов той группы, которая пришла наибольшее количество раз.
Примечание
Группа {BESSIE, ELSIE, MATILDA} вошла в амбар 3 раза.

—Войти и решать

Bookshelf (Silver)#89858

Когда Фермер Джон не доит коров, собирает сено, выстраивает коров или строит изгороди, он сидит и читает хорошую книгу. С годами он собрал коллекцию из N книг (1 <= N <= 2,000), и хочет построить для них новое множество книжных полок.
Каждая книга I имеет ширину W(i) и высоту H(i). Книги необходимо ставить на полки в определенном порядке; например, первая полка должна содержать книги с номерами от 1 до k для некоторого k. Вторая полка должна содержать книгу k+1 и т.д. Каждая полка имеет общую ширину не более L (1 <= L <=1,000,000,000). Высота полки равна высоте самой высокой книги на этой полке, а высота множества книжных полок равна сумме высот на всех полках, поскольку полки ставятся одна поверх другой.
Помогите ФД вычислить минимально возможную высоту всего множества книжных полок.
PROBLEM NAME: bookshelf
Формат входных данных
* Строка 1: два разделенных пробелом целых числа: N и L.
* Строки 2..1+N: Строка i+1 содержит два разделенных пробелом целых числа : H(i) W(i). (1 <= H(i) <= 1,000,000; 1 <= W(i) <= L).
Формат выходных данных
* Строка 1: Минимально возможная высота множества полок.
Примечание
Всего 3 полки. Первая содержит книгу 1 (высота 5, ширина 7), вторая содержит книги 2..4 (высота 13, ширина 9), третья содержит книгу 5 (высота 3, ширина 8).

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

—Войти и решать

Tied Down#89857

Беси одна из тех коров, которые любят создавать проблемы. Во избежание этого Фермер Джон решил привязать Беси к изгороди длинной веревкой. Если смотреть сверху, изгородь представляет N столбов (1 <= N <= 10), которые расположены вдоль вертикальной прямой. Беси находится в позиции (bx,by) находящейся справа от это вертикальной линии. Веревка, которой ФД привязывает Беси описывается последовательностью из M отрезков прямой, (3 <= M <= 10,000), где первый отрезок начинается в позиции Беси, и последний отрезок заканчивается в позиции Беси. Никакой из столбов не лежит ни на одном из этих отрезков. Однако отрезки могут пересекаться, и многие отрезки могут пересекаться в своих конечных точках.
Пример такой сцены, вид сверху:

Чтобы помочь Беси освободиться, подружки стащили пилу из амбара. Определите минимальное количество столбов, которые они должны спилить, для того, чтобы Беси могла освободиться (то есть она сможет убежать, И никакой из отрезков веревки не зацепился, ни за какой из столбов)
Все (x,y)-координаты на вводе (столбы изгороди, Беси, конечные точки отрезков), есть целые числа в диапазоне 0..10,000. Все столбы имеют одну и ту же x-координату, bx больше этой величины.
PROBLEM NAME: tied
Формат входных данных
* Строка 1: Четыре целых числа, разделенных пробелами: N, M, bx, by.
* Строки 2..1+N: Строка i+1 содержит разделенные пробелами x и y координаты столба i.
* Строки 2+N..2+N+M: Каждая из этих M+1 строк содержит, по очереди, x и y координаты точки веревки. Первая и последняя точки всегда совпадают с координатами Беси (bx,by).
Формат выходных данных
* Строка 1: Минимальное количество столбов, которое нужно удалить, Чтобы корова смогла убежать, двигаясь вправо.
Примечание
Удаление столба 1 или столба 2 приводит к желаемому результату.

Вычислительная геометрия

—Войти и решать

Bookshelf#89856

Когда Фермер Джон не доит коров, собирает сено, выстраивает коров или строит изгороди, он сидит и читает хорошую книгу. С годами он собрал коллекцию из N книг (1 <= N <= 100,000), и хочет построить для них новое множество книжных полок.
Каждая книга I имеет ширину W(i) и высоту H(i). Книги необходимо ставить на полки в определенном порядке; например, первая полка должна содержать книги с номерами от 1 до k для некоторого k. Вторая полка должна содержать книгу k+1 и т.д. Каждая полка имеет общую ширину не более L (1 <= L <=1,000,000,000). Высота полки равна высоте самой высокой книги на этой полке, а высота множества книжных полок равна сумме высот на всех полках, поскольку полки ставятся одна поверх другой.
Помогите ФД вычислить минимально возможную высоту всего множества книжных полок.
PROBLEM NAME: bookshelf
Формат входных данных
* Строка 1: два разделенных пробелом целых числа: N и L.
* Строки 2..1+N: Строка i+1 содержит два разделенных пробелом целых числа : H(i) W(i). (1 <= H(i) <= 1,000,000; 1 <= W(i) <= L).
Формат выходных данных
* Строка 1: Минимально возможная высота множества полок.
Примечание
Всего 3 полки. Первая содержит книгу 1 (высота 5, ширина 7), вторая содержит книги 2..4 (высота 13, ширина 9), третья содержит книгу 5 (высота 3, ширина 8).

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

—Войти и решать

Когда идут ливневые дожди, поля Фермера Джона всегда подтапливаются. И, поскольку имеется рельеф местности, в результате образуются острова, разделенные пространствами воды.
Поля ФД описаны как одноместный рельеф, указанием N (1 <= N <= 100,000) последовательных высот H(1)...H(n). Представим себе, что этот рельеф ограничен с обоих сторон валами бесконечной высоты. Теперь рассмотрим, что случится во время ливневого дождя: сначала водой покрываются нижние регионы, при этом получаются, разъединенные «острова», которые, в конце концов, могут все покрыться водой, если она будет прибывать и прибывать. Если уровень воды становится равным уровню куска земли, то этот кусок считается покрытым водой.

Пример показан на рисунке выше: слева мы добавили 1 единицу воды, и покрыли 4 острова. Затем мы добавили еще 7 единиц воды и теперь только два острова торчат из воды. Вычислите максимальное количество островов, которое мы сможем увидеть, если вода будет прибывать с нуля и до тех пор, пока весь рельеф не скроется под водой.

PROBLEM NAME: islands
Формат входных данных
* Строка 1: Целое число N.
* Строки 2..1+N: Строка i+1 содержит высоту H(i). (1 <= H(i) <= 1,000,000,000)
Формат выходных данных
* Строка 1: Одно целое число, определяющее максимальное количество островов, которое получится в один момент времени во время проливного дождя.

Сортировка событий

—Войти и решать

Cows in a Row#89851

У Фермера Джона N коров (1 <= N <= 1000) выстроены в ряд. У каждой коровы имеется ID породы. У коровы с номером i, ID породы B(i).
ФД думает, что его ряд коров выглядел бы более впечатляюще, если бы он имел как можно более длинный непрерывный блок коров с одинаковым ID коровы. Для того, чтобы создать такой блок, ФД решил удалить из своего ряда всех коров, имеющих конкретный ID породы, который он выберет.
Помогите ФД определить длину наибольшего непрерывного блока коров с одинаковым ID, который он может получить, удалив всех коров с некоторым ID, который выберет ФД.

PROBLEM NAME: cowrow
Формат входных данных
* Строка 1: Целое число N.
* Строки 2..1+N: Строка i+1 содержит B(i), целое число в диапазоне 0...1,000,000.
Формат выходных данных
* Строка 1: Наибольший размер непрерывного блока коров, с одинаковым ID коровы, который он может создать.

Примечание
При удалении всех коров с ID=3, ФД может получить ряд 2, 7, 7, 7, 7, 5, 7. В этому ряду максимальный непрерывный блок состоит из 4 коров с ID 7.

Алгоритмы обработки

—Войти и решать

Clumsy Cows#89849

Определите минимальное количество символов в строке из круглых скобок, которые нужно заменить на противоположный ( левую скобку на правую, или наоборот) , чтобы получить сбалансированную строку.
Существует несколько способов определить сбалансированную строку скобок. Например, такой: В строке должно быть одинаковое количество левых и правых скобок, и для любого ее префикса количество левых скобок должно быть не меньше, чем количество правых скобок.
Например, эти строки - сбалансированные () (()) ()(()())
А эти - нет: )( ())( ((())))
PROBLEM NAME: clumsy
Формат входных данных
* Строка 1: строка из скобок длиной не более 100,000 символов.

Формат выходных данных
* Строка 1: Одно целое число - минимальное количество скобок, которые нужно "переключить" , чтобы конвертировать заданную строку в сбалансированную.

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

Линейные алгоритмы

—Войти и решать

Concurrently Balanced Strings#89847

Коровы Фермера Джона различаются по породам и каждая корова помечена гигантским пятном на боку в виде круглой скобки. В зависимости от направления, в котором смотрит корова, эта скобка может быть левой или правой скобкой.
Однажды утром ФД организовал своих коров в K строк по N коров в каждой строке (1 <= K <= 10, 1 <= N <= 50,000). Коровы смотрят в произвольных направлениях, поэтому построение может быть описано как K строк из N символов-скобок. Назовем эти строки S₁, S₂, :, S_K. ФД заметил, что некоторые диапазоны коров "параллельно сбалансированы". Диапазон i..j коров называется "параллельно сьалансированным" тогда и только тогда, когда строки S₁,S₂,:,S_K сбалансированы в этом диапазоне. Например, если K=3 и у нас есть 3 строки
S₁ = )()((())))(()) S₂ = ()(()()()((()) S₃ = )))(()()))(()) 1111 01234567890123
Тогда диапазон [3:8] параллельно сбалансирован, поскольку S₁[3...8] = ((())) S₂[3...8] = ()()() S₃[3...8] = (()())
Диапазоны [10...13] и [11...12] также параллельно сбалансированы.
Ваша задача - посчитать количество сбалансированных диапазонов для заданных K строк длины N.
Строка S называется сбалансированной, если количество левых скобок равно количеству правых и для любого префикса этой строки количество левых скобок не меньше чем количество правых скобок.
Например эти строки сбалансированы () (()) ()(()())
А эти - нет: )( ())( ((())))
PROBLEM NAME: cbs
Формат входных данных
* Строка 1: Два целых числа, K и N.
* Строки 2..K+1: Каждая строка содержит N скобок.
Формат выходных данных
* Строка 1: Одно целое число - количество сбалансированных диапазонов

Префиксные суммы(минимумы, ...)

—Войти и решать

Balanced Trees#89846

Ферма Джона - гигантское дерево из N пастбищ (1 <= N <= 40,000), каждое из которых помечено символом ( или символом ).
Например:
'('--'('--')'--'('--')' | | ')' ')'--'('--'(' | | ')' '('--')'--')'--')'--'('
Поскольку ферма дерево - то некоторые пары пастбищ соединены дорожками, так что существует уникальный путь между любыми двумя парами пастбищ. Некоторые из этих путей представляют сбалансированные строки скобок. Теперь ФД хочет узнать какова максимальная глубина вложенности среди всех сбалансированных строк представляющих эти пути.
Максимальной глубиной вложенности сбалансированной строки скобок называется максимальное превышение количества левых скобок над правыми среди всех префиксов этой строки. Например, для строки ()()() максимальная глубина вложенности - 1, а для строки ((()))() максимальная глубина вложенности - 3:
((()))() 12321010
Для примера фермы, представленного выше "наиглубокая" строка есть ((())), ее глубина равна 3, а строка получается по пути из A в B:
'('--'('--')'--'('--')' | | ')' ')'--'('--'(' < A | | ')' '('--')'--')'--')'--'(' ^C ^B
Заметим, что она отличается от самой длинной сбалансированной строки (())(()), которая начинается в A, заканчивается в C и имеет длину 8.
Ваша задача - вывести максимальную глубину вложенности среди путей на данном дереве.
PROBLEM NAME: btree
Формат входных данных
* Строка 1: Одно целое число N, количество вершин в дереве.
* Строки 2..N: Строка i+1: Одно целое число p_(i+1) (1 <= p_(i+1) <= i), означающее, что существует ребро между вершинами I+1 и P_(I+1) в этом дереве.
* Строки N+1..2N: Строка N+i: Или ( или ), метка вершины i.
Формат выходных данных
* Строка 1: Одно целое число - максимальная глубина вложенности среди всех сбалансированных путей

—Войти и решать

Typo#89844

Беси только что купила новый лэптоп. Однако ей неудобно работать с клавиатурой, поэтому она набирает строки из круглых скобок. Она может ошибиться и набрать ( вместо ) и наоборот.
Посчитайте количество мест в строке таких, что замена одной скобки на противоположную в этом месте сделает строку сбалансированной.
Есть несколько способов определить, что такое "сбалансированная" строка скобок. Например, так: 1) Всего должно быть одинаковое количество левых ( и правых ) скобок и для любого префикса этой строки, левых скобок должно быть не меньше чем правых.
Следующие строки сбалансированы () (()) ()(()())
А эти - нет:
)( ())( ((())))
PROBLEM NAME: typo
Формат входных данных
* Строка 1: строка из скобок с длиной N (1 <= N <= 100,000).
Формат выходных данных
* Line 1: количество позиций в этой строке, (если они вообще есть), таких, что замена одной скобки на противоположную в этой позиции приведет к тому, что строка станет сбалансированной.
Примечание
Для исходной строки:
12345678 ()(())))
Замена скобки в позиции 2 приводит к такой сбалансированной строке
12345678 (((())))
Аналогично сбалансированные строки получается при замене скобок в позициях 5, 6, и 7.

Префиксные суммы(минимумы, ...)

—Войти и решать

Horseshoes#89843

Еще Беси уважает "совершенно сбалансированные строки", в которых за строкой из левых скобок следует строка их правых скобок такой же длины.
(((())))
Имеется двумерный массив из N*N символов ( и ). Начиная с левого верхнего угла массива нужно пройти, выбирая символы так, чтобы построенная строка была совершенно сбалансированной и имела максимальную длину.
На каждом шагу можно двигаться вверх, вниз, влево или вправо, но нельзя заходить в одну и ту же клетку более одного раза. Можно зайти не во все клетки.
PROBLEM NAME: hshoe
Формат входных данных
* Строка 1: Целое число N (2 <= N <= 5).
* Строки 2..N+1: Каждая строка содержит строку из N скобок. Все вместе эти строки описывают решетку N*N.
Формат выходных данных
* Line 1:Длина наибольшей совершенно сбалансированной строки. Если Беси не может построить совершенно сбалансированную строку например, если левый верхний угол содержит символ )., то выведите 0.

Примечание
Последовательность шагов, которую нужно выполнить, чтобы получит ответ 8 такова: 1()) 2)(( 345( 876)

—Войти и решать

Find the Cow!#89842

нн
Беси сбежала и прячется на холме, покрытом высокой травой. Фермер Джон, пытаясь поймать Беси решил ползти по траве на руках и коленях, так чтобы подобраться незамеченным.
Трава перед Фермером Джоном выглядит как строка из N круглых скобок (1 <= N <= 50,000), например
)((()())())
Фермер джон знает, что задние ноги Беси выглядят как две соседних левых скобок ((, а пара ее передних ног выглядит, как пара соседних праваых скобок )). Поэтому местоположение Бес,и может быть описано парой индексов x < y таких, что (( находятся на позиции x, а )) находятся на позиции y.
Вычислите количество различных позиций, в которых может находится Беси.
PROBLEM NAME: cowfind
Формат входных данных
* Строка 1: строка из скобок, длиной N (1 <= N <= 50,000).
Формат выходных данных
* Строка 1: Количество позиций, в которых Беси может стоять (то есть количество таких различных пар (x,y), что x < y и (( стоят на позиции x, а )) стоят на позиции y )

Примечание
Всего имеется четыре варианта расположения Беси, они указаны ниже:
1. )((()())()) ^^ ^^
2. )((()())()) ^^ ^^
3. )((()())()) ^^ ^^
4. )((()())()) ^^ ^^

—Войти и решать

Фермер Джон оставил свой трактор в середине поля. Коровы решили подшутить над ФД. Они разместили N стогов сена (1 <= N <=50,000) в различных участках поля, так что ФД не может забрать трактор не удалив некоторые из них.
Местоположение трактора и стогов сена - это точки на декартовой плоскости с целочисленными координатами от 1 до 1000. Нет стогов сена в позиции трактора. Трактор ФД может двигаться только параллельно осям координат (на север, юг, запад и восток) на целое количество единиц. Трактор не может проходить через точку, в которой имеется стог сена.
Пожалуйста, помогите ФД определить минимальное количество стогов сена, которые придется убрать, чтобы он мог привести трактор в начало координат.
PROBLEM NAME: tractor
Формат входных данных
* Строка 1: Три разделенных пробелом целых числа N x y (x,y) - начальные координаты трактора
* Строки 2..1+N: Каждая строка содержит (x,y)-координаты стога сена

Формат выходных данных
* Строка 1: Минимальное количество стогов сена, которое ФД должен удалить для того, чтобы обеспечить путь своему трактору к началу координат.
Примечание
Достаточно удалить только 1 стог.

Обход в ширину

—Войти и решать