Информатика

16 015 задачвместе с подтемами

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

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

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

Farm Painting#89894

После нескольких суровых зим, Фермер Джон решил, что пришло время покрасить свою ферму. Ферма состоит из N (1 <= N <= 50,000) отгороженных пастбищ, каждое из которых может быть описано прямоугольником на 2D плоскости со сторонами, параллельными осям X и Y.
Пастбища могут содержаться один внутри другого, но их изгороди не могут пересекаться. Поэтому, если два пастбища покрывают одну и ту же область на 2D плоскости, то одно должно содержаться внутри другого.
ФД понимает, что пастбище, содержащееся внутри другого, не видимо снаружи. Поэтому он хочет красить изгороди только тех пастбищ, которые не содержатся внутри других пастбищ.
Определите общее количество пастбищ, изгороди которых он должен покрасить.
PROBLEM NAME: painting
Формат входных данных
* Строка 1: Количество изгородей, N.
* Строки 2..1+N: Каждая строка описывает изгородь 4-мя целыми числами x1, y1, x2, y2 (разделенных одиночными пробелами), где (x1,y1) - левый нижний угол изгороди, (x2,y2) - правый верхний уго изгороди. Все координаты в диапазоне 0..1,000,000.
Формат выходных данных
* Строка 1: Количество пастбищ, которые не содержатся внутри других пастбищ.
Примечание
Пастбище 3 содержится внутри пастбища 1, поэтому ответ 2.

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

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

Беси выложила N камней, на каждом одна буква алфавита и хочет построить ожерелье.
Имя соседки Беси представляет строку из M символов. Беси хочет, чтобы эта строка из M символов не встречалась как непрерывная подстрока в строке, представляющей ее ожерелье.
Беси решила удалить некоторые из камней из своего ожерелья, так чтобы имя другой коровы не встречалась как подстрока.
Определите минимальное количество камней, которое она должна удалить.
PROBLEM NAME: necklace
Формат входных данных
* Строка 1: Строка длины N, описывающая ожерелье Беси все символы в диапазоне a-z.
* Строка 2: Строка длины M, описывающая имя другой коровы все символы в диапазоне a-z.
Формат выходных данных
* Строка 1: Минимальное количество камней, которое нужно удалить из ожерелья Беси, чтобы оно не содержало имя другой коровы как подстроку
Примечание
Модифицированная строка должна быть "abbaa".

Z-функция. Префикс-функция

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

Чтобы окончательно решить вопрос кто быстрее, Беси и ее подруга Эльза решили провести гонки вокруг фермы.
Обе коровы стартуют в одном и том же месте, в одно и то же время и начинают бежать в одном направлении. Прогресс каждой коровы описывается серией отрезков, в течение которого данная корова имеет одинаковую скорость. Например, Бэси может бежать со скоростью 5 в течение 3 единиц времени, затем со скоростью 6 в течение 6 единиц времени. Обе бегут одинаковое общее количество времени.
Коровы попросили Вас посчитать количество раз, когда менялось лидерство в их гонке. Лидерство меняется в той точке времени, когда корова A обгоняет корову B или наоборот.
PROBLEM NAME: cowrace
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа, N и M. (1 <= N, M <= 1000)
* Строки 2..1+N: Каждая строка содержит один из N отрезков бега Беси, описанный двумя целыми числами: скорость и количество времени, которое она бежала с данной скоростью (оба числа в диапазоне от 1 до 1000).
* Строки 2+N..1+N+M: Каждая строка содержит один из M отрезков бега Эльзы, описанный двумя целыми числами: скорость и количество времени, которое она бежала с данной скоростью (оба числа в диапазоне от 1 до 1000).
Формат выходных данных
* Строка 1: Количество раз когда изменилось лидерство в забеге.
Примечание
Эльза была впереди до момента времени t=3, когда обе коровы пробежали 6 единиц расстояния, затем бежали вместе в течение одной единицы времени. Беси затем вырвалась вперед (первое изменение лидерства), затем ее обошла Беси (второе изменение лидерства), Беси так и осталась лидером до конца гонки.

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

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

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).

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

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