Алгоритмы

948 задачвместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
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 содержит одно целое число qi
Описывающее i-ый запрос. Вы должны вычислить значение карты
неа позиции qi сверху (1 <= qi <= N).

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

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

Примечание

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

[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 производит gi галлонов молока (1<=gi<=1000),
но только если её подоить до её дед-лайна – di (1<=di<=10,000).
Время начинается в момент t=0.
Поэтому не более x коров может быть подоено до дед-лайна t=x.

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

PROBLEM NAME: msched

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

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

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

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

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

Примечание

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

Жадный алгоритм
—Войти и решать
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 направлении из любой из точек плоскости, не имея возможности попасть в цикл.

Перебор
—Войти и решать
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).
Динамическое программирование: один параметр
—Войти и решать
Islands#89852

Когда идут ливневые дожди, поля Фермера Джона всегда подтапливаются. И, поскольку имеется рельеф местности, в результате образуются острова, разделенные пространствами воды.
Поля ФД описаны как одноместный рельеф, указанием 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: Одно целое число, определяющее максимальное количество островов, которое получится в один момент времени во время проливного дождя.

Сортировка событий
—Войти и решать
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: Одно целое число - максимальная глубина вложенности среди всех сбалансированных путей
Деревья
—Войти и решать
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)

Перебор
—Войти и решать
Tractor#89841

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

 


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

 

Обход в ширину
✓ 1✗ 12—Войти и решать
Landscaping#89840

Фермер Джон строит сад. Сад состоит из последовательности из N цветочниц (1 <= N <= 100). Каждая цветочница изначально содержит Ai цветов. ФД хочет изменить сад таким образом, чтобы каждая цветочница стала содержать Bi цветов. Ai и Bi - числа от 0 до 10.
ФД может делать следующее - купить цветок за X долларов и добавить его в любую цветочницу - убрать цветок из любой цветочницы и это стоит Y долларов - переместить цветок из цветочницы i в цветочницу j за цену Z * abs(i-j) долларов
Вычислите минимальную цену выполнения реорганизации сада.

PROBLEM NAME: landscape
Формат входных данных
* Строка 1: Разделенные пробелом целые числа N, X, Y, Z (0 <= X, Y, Z <= 1000).
* Строки 2..1+N: Строка i+1 содержит разделенные пробелом целые числа Ai и Bi.
Формат выходных данных
* Строка 1: Одно целое число - минимальная стоимость реорганизации сада.


Примечание
Один цветок нужно продать (с цветочницы 4), за цену 200. Остальные цветки можно переместить за цену 10 (3 цветка с цветочницы 4 на цветочницу 1 и 1 цветок с цветочницы 3 на цветочницу 2)

Жадный алгоритм
—Войти и решать
Wrong Directions#89835

Фермер Джон купил программируемый трактор. Чтобы заставить трактор двигаться, он пишет строку длиной N (1 <= N <= 100,000), состоящую только из символов F, L, R. Символ 'F' заставляет трактор двигаться на единицу вперед, символы 'L' и 'R' заставляют трактор повернуться на 90 градусов влево или вправо, соответственно. Трактор начинает движение в точке (0,0) глядя на север.
ФД знает, что он ошибся ровно в одном символе. Например, он мог набрать 'F' или 'L' вместо 'R' в некотором месте. Но он не помнит точно в каком месте он ошибся.
Пожалуйста, вычислите количество различных точек на плоскости, в которых может оказаться трактор в результате выполнения этой программы (направление в конечной позиции не играет роли).
PROBLEM NAME: wrongdir
Формат входных данных
* Строка 1: Строка ФД

Формат выходных данных
* Строка 1: Количество позиций, в которых может оказаться трактор, если ФД ошибся в каком-то одном символе.
Примечание
Всего имеется 4 возможных ошибочных последовательности: FL, FR, LF, RF.
И при их выполнении трактор оказывается в точках (0,1), (0,1), (-1,0), (1,0) соответственно. Всего 3 различных точки.

Задачи на моделирование
—Войти и решать
Times 17#89834

Фермер Джон осознал, что разработка программного обеспечения - это прибыльный бизнес и решил писать маленькие программы местного значения.
Его первая программа такая простая: его клиент хочет, чтобы он ввел число N и вывел 17*N, при этом оба числа должны быть в двоичной системе счисления и число N может иметь до 1000 цифр.
PROBLEM NAME: times17
Формат входных данных
* Строка 1: Двоичное представление числа N (не более 1000 цифр).
Формат выходных данных
* Строка 1: Двоичное представление N*17.
Примечание
Двоичное число 10110111 равно 183 десятичное. 183 x 17 = 3111, а это 110000100111 в двоичном виде.
"Длинная" арифметика
✓ 1✗ 0—Войти и решать
Connect the Cows#89833

Каждый день Фермер Джон обходит свою ферму, чтобы проведать N (1 <= N <= 10) своих коров.
Местоположение каждой из его коров описывается точкой на координатной плоскости, а ФД начинает в точке (0,0). Чтобы сделать маршрут более интересным, ФД ходит только параллельно осям координат (на север, юг, восток и запад). Он меняет направление своего движения, только когда он добирается до одной из коров. Если пожелает, он может не менять направление своего движения, проходя через местоположение коровы. Когда ФД меняет направление движения, он может менять его на 90 или 180 градусов. ФД должен вернутся в исходную точку после посещения всех коров.
Пожалуйста, вычислите общее количество способов, которыми ФД может посетить всех своих коров, если он изменит направление своего движения ровно один раз у каждой коровы. Не изменяя направление движения, он может ходить мимо коровы произвольное количество раз. Один и тот же геометрический путь, пройденный в прямом и обратном направлениях, считается как два различных маршрута.
PROBLEM NAME: connect
Формат входных данных
* Строка 1: Целое число N.
* Строки 2..1+N: Строка i+1 содержит x и y координаты (разделенные пробелом) для i-ой точки(все числа в диапазоне -1000...1000).
Формат выходных данных
* Строка 1: Количество различных маршрутов ФД (может быть равным 0, если их нет)


Примечание
Всего есть два различных маршрута 1-2-4-3 или 3-4-2-1 прежде чем ФД вернется в точку (0,0).

Перебор
✓ 0✗ 1—Войти и решать
Mountain Climbing#89832

Фермер Джон обнаружил, что его коровы дают больше молока, если занимаются спортом. Поэтому он послал N (1 <= N <= 25,000) своих коров взобраться на ближайшую гору и вернуться обратно.
Корове I требуется U(i) времени взобраться на гору и D(i) времени, чтобы спуститься с нее. Каждой корове нужна помощь человека, а их всего два ФД и его кузен фермер Дон (ФДо). ФД будет помогать коровам подниматься, а ФДо - спускаться. Поэтому в любой момент времени только одна корова будет подыматься (с помощью ФД) и не более одной коровы - спускаться (с помощью ФДо).
Группа коров может временно находится на вершине горы, если они туда взобрались, и ждут помощи от ФДо чтобы спуститься. Коровы могут спускаться в порядке, отличном от того, в котором они подымались.
Определите минимальное количество времени, которое требуется всем коровам, чтобы совершить полное путешествие туда и обратно.
PROBLEM NAME: climb
Формат входных данных
* Строка 1: Количество коров, N.
* Строки 2..1+N: Строка i+1 содержит два разделенных пробелом целых числа: U(i) и D(i). (1 <= U(i), D(i) <= 50,000).
Формат выходных данных
* Строка 1: Одно целое число, представляющее минимальное количество времени, которое требуется всем коровам взобраться на гору и вернуться обратно.
Примечание
Если корова 3 пойдет первой, затем корова 1 и затем корова 2 (и в таком же порядке возвращаться), это и даст суммарное время 17.
Жадный алгоритм
—Войти и решать
Haybale Stacking#89826

Беси согласилась помочь ФД уложить пакеты с сеном. Она начинает с N (1 <= N <= 1,000,000, N нечетное) пустых стеков, пронумерованных от 1 до N. Затем ФД дает ей последовательность из K инструкций (1 <= K <= 25,000), каждая вида A B, означающая, что Беси должна добавить по одному пакету с сеном в каждый из стеков в диапазоне от A до B. Например, инструкция 10 13 означает, что Беси должна положить по пакету сеном в стеки 10, 11, 12, 13.
После того как вся работа закончена, ФД хочет узнать медианную высоту всех N своих стеков - то есть высоту среднего стека, если все стеки упорядочить по высоте. По условию N нечетно, поэтому этот стек уникален. Пожалуйста, помогите Беси ответить на этот вопрос.
PROBLEM NAME: stacking
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа, N K.
* Строки 2..1+K: Каждая строка содержит одну инструкцию ФД в виде двух целых (разделенных пробелом) чисел A B (1 <= A <= B <= N).

Формат выходных данных
* Строка 1: Медианная высота после того как Беси выполнит все инструкции


Примечание
После того, как Беси закончит, стеки будут иметь высоты 0,1,2,3,3,1,0. Если их упорядочить, получим: 0,0,1,1,2,3,3. Средний элемент равен 1.

Алгоритмы обработкиИспользование сортировкиПрефиксные суммы(минимумы, ...)
—Войти и решать
Grazing Patterns#89825

Деньги кончились, и теперь ферма Джона имеет размер 5*5 метров. Поле (1,1) находится в левом верхнем углу, поле (5,5) - в правом нижнем.
(1,1) (1,2) (1,3) (1,4) (1,5) (2,1) (2,2) (2,3) (2,4) (2,5) (3,1) (3,2) (3,3) (3,4) (3,5) (4,1) (4,2) (4,3) (4,4) (4,5) (5,1) (5,2) (5,3) (5,4) (5,5)
Каждый квадрат этой решетки содержит траву, кроме K выжженных Квадратов (0 <= K <= 22, K четное) квадратов, где нет травы. Беси начинает пастись в квадрате (1,1), в котором всегда есть трава. Милдред начинает пастись в клетке (5,5), где тоже всегда есть трава.
Каждые полчаса Беси и Милдред съедают всю траву в своем квадрате и переходят в соседний квадрат (на север, юг, запад или восток). Они хотят съесть всю траву и встретиться в общей финальной позиции. Пожалуйста, вычислите количество различных способов сделать это. Беси и Милдред всегда двигаются только в квадрат с травой и никогда не идут в один и тот же квадрат, если это не самый последний квадрат с травой.
PROBLEM NAME: grazing
Формат входных данных
* Строка 1: Целое число K.
* Строки 2..1+K: Каждая строка содержит координаты (I,j) клетки без травы - два целых числа I и J через пробел.

Формат выходных данных
Строка 1: Количество различных способов Беси и Милдред пройти по полю, съесть всю траву и встретиться в одной и той же клетке.
Примечание
Есть только один способ - встретиться в клетке (3,5), пройдя указанными на рисунке ниже маршрутами
b b--b b--b | | | | | b--b b--b b | x x x x b/m | m--m--m--m--m | m--m--m--m--m

Перебор
—Войти и решать
Gifts#89824

Фермер Джон хочет сделать подарки своим N (1 <= N <= 1000) коровам, используя свой бюджет в B (1 <= B <= 1,000,000,000) единиц денег.
Корова I требует подарка с ценой P(i) единиц ценой доставки S(i) (поэтому для ФД будет стоить P(i)+S(i) заказать этот подарок). У ФД есть специальный купон, который он может использовать чтобы заказать подарок за полцены. Если ФД использует этот купон для коровы I, то он должен будет заплатить только P(i)/2 + S(i). По соглашению, все P(i) четные числа.
Пожалуйста, помогите ФД определить максимальное количество коров, которым он сможет сделать подарки.
PROBLEM NAME: gifts
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа, N и B.
* Строки 2..1+N: Строка i+1 содержит два разделенных пробелом целых числа, P(i) и S(i). (0 <= P(i),S(i) <= 1,000,000,000, P(i)- четное)
Формат выходных данных
* Строка 1: Максимальное количество коров, которым ФД может купить подарки.
Примечание
ФД может купить подарки для коров с первой по 4-ую, если он использует Купон для коровы 3. Потраченная сумма будет: (4+2)+(2+0)+(4+1)+(6+3) = 22. Заметим, что ФД альтернативно может использовать купон для коров 1 или 4 И все равно не превысить бюджет.
Жадный алгоритм
✓ 4✗ 0—Войти и решать
Overplanting (Silver)#89822

Фермер Джон купил новую машину, которая умеет садить траву в прямоугольном регионе со сторонами, параллельными осям координат. К несчастью, эта машина однажды сломалась и посадила траву не в одном, а в N (1 <= N <= 1000) различных регионах, некоторые из которых могут даже перекрываться.
По заданным прямоугольным регионам, засаженным травой, помогите ФД определить общую площадь, покрытую травой.
PROBLEM NAME: planting
Формат входных данных
* Строка 1: Целое число N.
* Строки 2..1+N: Каждая строка содержит четыре разделенных одиночными пробелами целых числа x1 y1 x2 y2 указывающих прямоугольный регион с верхним - левым углом (x1,y1) и нижним – правым углом (x2,y2). Все координаты – целые числа в диапазоне -10^8...10^8..
Формат выходных данных
* Строка 1: Общая площадь, покрытая травой. Заметим, что общая площадь может быть настолько большой, что не поместиться в 32-битное целое.
Отрезки
—Войти и решать
Cow IDs#89821

Фермер Джон пометил всех своих коров двоичными числами. Однако не любыми, а только такими, в которых ровно K единиц. (1<=K<=10). Конечно, лидирующий бит каждой метки равен 1. ФД назначает метки в порядке возрастания чисел, начиная от самой маленькой корректной метки (K-битного числа, состоящего из всех единиц). Теперь он нуждается в Вашей помощи: определите N-ую метку, которую он должен назначить (1 <= N <= 10^7).
PROBLEM NAME: cowids
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа, N и K.
Формат выходных данныхдвоичное число
Перестановки
✓ 0✗ 7—Войти и решать
Поделиться
Класснуть