Информатика

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

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

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

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

Breed Proximity#89889

N (1 <= N <= 50,000) коров Фермера Джона выстроились в ряд, каждая описывается своим ID породы.
Коровы одной породы рискуют поругаться, если стоят слишком близко. А именно, две коровы одной породы называются "crowded" если их позиции в ряду отличаются не более чем на K (1<=K< N).
Вычислите максимальный ID пары "crowded" коров.
PROBLEM NAME: proximity
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа: N и K.
* Строки 2..1+N: Каждая строка содержит ID породы одной коровы в ряду. Все ID коров находятся в диапазоне 0..1,000,000.

Формат выходных данных
* Строка 1: Максимальный ID породы двух "crowded" коров или -1 если нет такой пары коров.
Примечание
Имеется две пары "crowded" коров - с ID породы 3 и 4.

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

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

Square Overlap#89887

Фермер Джон планирует построить N (2 <= N <= 50,000) квадратных огороженных пастбищ у себя на ферме, каждое размером ровно K x K (1 <= K <= 1,000,000).
Пастбище i имеет центр в точке (x_i, y_i), с целочисленными координатами в диапазоне -1,000,000...1,000,000. Никакие два пастбища не имеют один и тот же центр.
Вычислите (ненулевую) площадь перекрытия двух квадратных пастбищ. Выведите 0, если никакие два квадрата не перекрываются. Выведите -1 если перекрываются более одной пары квадратов.
PROBLEM NAME: squares
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа, N и K. Гарантируется, что K четное.
* Строки 2..1+N: Строка i+1 содержит целые числа x_i и y_i, описывающие центр пасбища i.
Формат выходных данных
* Строка 1: Площадь перекрытия двух квадратов. Выведите 0, если никакие два квадрата не перекрываются, выведите -1, если перекрываются более одной пары квадратов.
Примечание
Пастбища #1 и #3 перекрываются на 20 единиц площади.

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

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

Painting the Fence#89885

Корова Беси красит забор Фермеру Джону. Беси начинает в позиции 0 и выполняет последовательность из N инструкций. (1 <= N <= 100,000) вида "10 L", что означает покрасить 10 единиц влево и "15 R", что означает покрасить 15 единиц вправо.
Бесси может уйти не далее чем на 1,000,000,000 единиц от исходной точки.
По имеющей инструкции ФД хочет узнать область забора, которая покрашена как минимум K слоями краски.
PROBLEM NAME: paint
Формат входных данных
* Строка 1: Целые N и K
* Строки 2..1+N: Каждая строка описывает одну из N инструкций
Формат выходных данных
* Строка 1: Общая часть, покрашенная как минимум K слоями краски.
Примечание
6 единиц покрыто как минимум 2 слоями краски. Это интервалы: [-11,-8], [-4,-3], [0,2].

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

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

Чтобы заработать немного денег, коровы открыли ресторан. В ресторане N мест (1 <= N <= 500,000) в одном ряду. Изначально, все они пусты.
В течение дня в ресторане происходят M (1 <= M <= 300,000) различных событий одного из двух типов:
1. Прибывает вечеринка размером p (1 <= p <= N). Беси хочет усаживать вечеринку на непрерывный блок из p мест. Если таких блоков несколько, то она садит вечеринку на блок с самым маленьким номером начальной позиции. Если такого блока нет, вечеринка убывает.
2. Задается диапазон [a,b] (1 <= a <= b <= N), и каждый в этом диапазоне мест, подымается и покидает ресторан.
Помогите Беси вычислит общее количество вечеринок, которые "уйдут несолоно хлебавши" в течение дня.

PROBLEM NAME: seating
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа, N и M.
* Строки 2..M+1: Каждая строка описывает одно событие в форме "A p" (что означает прибытие вечеринки размером p) или в форме "L a b" (что означает, что все коровы в диапазоне [a,b] уходят).

Формат выходных данных
* Строка 1: Количество вечеринок, которые не начнутся.
Примечание
Вечерника #3 не сможет быть размещена. Все другие вечеринки состоятся.

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

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

Cow Lineup#89882

N коров (1 <= N <= 100,000) Фермера Джона выстроились в ряд. Каждая корова идентифицирована числом в диапазоне 0...1,000,000,000; которое обозначено B(i). Множество коров могут иметь один и тот же идентификатор.
ФД думает, что ряд коров будет впечатлять больше, если бы там был большой непрерывный участок, на котором все коровы имеют одинаковый идентификатор. Для того чтиобы создать такой участок, ФД выбирает до K идентификаторов и удаляет из своего ряда всех коров имеющих эти идентификаторы.
Помогите ФД вычислить длину наиблоьшего последовательного блока коров с одним и тем же идентификатором, после такого удаления.

PROBLEM NAME: lineup
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа: N и K.
* Строки 2..1+N: Строка i+1 содержит идентификатор B(i).
Формат выходных данных
* строка 1: Размер наибольшего непрерывного блока коров с одним идентификатором, который может создать ФД.
Примечание
Удалив всех коров с идентификатором 3, ФД получит ряд: 2, 7, 7, 7, 7, 5, 7. Имеется наибольший непрерывный участок из четырех чисел 7.

"Два указателя"

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

Painting the Fence#89881

Корова Беси красит забор Фермеру Джону. Беси начинает в позиции 0 и выполняет последовательность из N инструкций. (1 <= N <= 100,000) вида "10 L", что означает покрасить 10 единиц влево и "15 R", что означает покрасить 15 единиц вправо.
Бесси может уйти не далее чем на 1,000,000,000 единиц от исходной точки.
По имеющей инструкции ФД хочет узнать область забора, которая покрашена как минимум двумя слоями краски.

PROBLEM NAME: paint
Формат входных данных
* Строка 1: Целое N
* Строки 2..1+N: Каждая строка описывает одну из N инструкций
Формат выходных данных
* Строка 1: Общая часть, покрашенная как минимум 2 слоями краски.
Примечание
6 единиц покрыто как минимум 2 слоями краски. Это интервалы: [-11,-8], [-4,-3], [0,2].

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

Milk Scheduling#89876

N (1 <= N <= 10,000) коров Фермера Джона пронумерованы последовательно от 1 до N. Для доения коровы i требуется T(i) единиц времени. Однако некоторые коровы необходимо подоить ранее других (из-за их положения на ферме). Если корову A требуется подоить перед коровой B, ФД должен полностью закончить дойку коровы A, прежде чем начать дойку коровы B.
Для того, чтобы подоить всех своих коров как можно быстрее, ФД нанял большое количество доярок - достаточно для того чтобы доить любое количество коров одновременно.
Определите минимальное количеатво времени, требуемое для дойки всех коров.

PROBLEM NAME: msched
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа: N (количество коров) и M (количество ограничений).
* Строки 2..1+N: Строка i содержит значение T(i).
* Строки 2+N..1+N+M: Каждая строка содержит два разделенных пробелом целых числа A и B, означающих, что корова A должна быть полностью подоена, прежде чем приступать к дойке коровы B.

Формат выходных данных
* Строка 1: Минимальное количество времени, требуемое чтобы подоить всех коров.
Примечание
Коров 1 и 3 можно начинать доить сразу и делать это одновременно. Когда закончится дойка коровы 3, можно начинать дойку коровы 2. Через 11 единиц времени закончится дойка всех коров.

Топологическая сортировка

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

Taxi#89875

Беси открыла такси-сервис для других коров на ферме. Коровы собрались в различных местах вдоль изгороди длины M (1<=M<=1,000,000,000) и каждая хочет переместиться в некоторое другое место вдоль изгороди. Беси должна подобрать корову в том месте, где она находится и отвезти в то место, куда она хочет.
Автомобиль Беси маленький и за раз может возить только одну корову. Коровы могут входить машину и выходить из нее мгновенно.
Беси хочет минимизировать расстояние проезда. Вам даны стартовые и финишные позиции N коров (1 <= N <= 100,000), определите минимальное количество езды, которое должна выполнить Беси. Беси поняла, что иногда выгодно высаживать корову не в позиции ее назначения.
Беси начинает в самой левой точке изгороди - позиции 0 и и должна закончить свое путешествие в самой правой точке - в позиции M.
PROBLEM NAME: taxi
Формат входных данных
* Cтрока 1: N и M разделенные пробелом
* Строки 2..1+N: (i+1)-ая строка содержит два разделенных пробелом целых числа, s_i и t_i (0 <= s_i, t_i <= M), указывающих стартовую и конечную позиции i-ой коровы.

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

Примечание
Беси возьмет первую корову в позиции 0 и перевезет ее на позицию 6. Здесь она высадит первую корову и возьмет вторую корову, отвезет куда ей надо, а потом поедет к концу изгороди.

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

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

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: Одно целое число, определяющее максимальное количество островов, которое получится в один момент времени во время проливного дождя.

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

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