Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

Landscaping#89840

Фермер Джон строит сад. Сад состоит из последовательности из N цветочниц (1 <= N <= 100). Каждая цветочница изначально содержит A_i цветов. ФД хочет изменить сад таким образом, чтобы каждая цветочница стала содержать B_i цветов. A_i и B_i - числа от 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 содержит разделенные пробелом целые числа A_i и B_i.
Формат выходных данных
* Строка 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—Войти и решать

Cow Coupons#89818

Фермер Джон хочет купить новых коров! На продаже имеется N (1 <= N <= 50,000) коров, а у ФД может потратить не более, чем M (1 <= M <=10^14) единиц денег. Корова I стоит P_i денег (1 <= P_i <= 10^9). У ФД имеется K купонов (1<=K<=N). Когда он использует купон для покупки коровы I, то цена будет C_i вместо P_i (1<=C_i<=P_i). Для каждой коровы ФД должен использовать ровно один купон.
Какое максимальное количество коров может купить ФД?
PROBLEM NAME: coupons
Формат входных данных
* Строка 1: Три разделенных пробелом целых числа: N, K, M.
* Строки 2..N+1: Срока i+1 содержит два целых числа: P_i C_i.
Формат выходных данных
* Строка 1: Одно целое число, максимальное количество коров, которое может купить ФД.
Примечание
ФД использует купон при покупке коровы 3 и купит коров 1, 2, 3 за цену 3 + 2 + 1 = 6.

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

✓ 0✗ 11—Войти и решать

Rope Folding#89817

У Фермера Джона есть длинная веревка длины L (1 <= L <= 10,000), которую он использует на ферме. На веревке завязаны N (2 <= N <= 100) узлов на различных расстояниях, в том числе на обоих концах.
ФД заметил, что имеются определенные точки на веревке, в которой он может перегнуть веревку назад, так что узлы на обоих частях веревки станут точно рядом друг с другом.

Пожалуйста, помогите ФД посчитать количество точек перегиба, в которых соблюдается это свойство. Допускается складывание веревки в любом из узлов (кроме начала и конца веревки). Лишние узлы на более длинной части веревки не принимаются во внимание (то есть необходимо обеспечить выравнивание узлов в области, где есть обе части веревки). Делать можно только одно складывание за один раз. ФД не умеет складывать веревку много раз.
PROBLEM NAME: folding
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа, N и L.
* Строки 2..1+N: Каждая строка содержит одно целое число в интервале 0...L Указывающее расположение одного узла. Две из этих строк будут всегда 0 и L.
Формат выходных данных
* Строка 1: Количество корректных позиций перегиба веревки.
Примечание
Корректные позиции перегиба 1, 2, 3, 8.

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

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

Moo#89815

Коровы придумали новую игру “Moo”. Они стоят в ряд, где каждая корова отвечает за то, чтобы назвать конкретную букву как можно быстрей.
Последовательность букв определена до бесконечности. Ее начало представлено ниже:
m o o m o o o m o o m o o o o m o o m o o o m o o m o o o o o
Эта последовательность проще всего описывается рекурсивно. Пусть S(0) будет последовательность из трех символов "m o o". S(k) получается конкатенацией: копии последовательности S(k-1), затем “m o … o” c k+2 символами ‘o’ и затем еще одна копия последовательности S(k-1). Например:
S(0) = "m o o" S(1) = "m o o m o o o m o o" S(2) = "m o o m o o o m o o m o o o o m o o m o o o m o o"
Очевидно, так можно построить строку любой длины и эта строка используется для игры в “Moo”.
Беси, которая про себя думает, что она умная корова, хочет предсказать, Каким будет символ на позиции N – ‘m’ или ‘o’. Помогите ей!
PROBLEM NAME: moo
Формат входных данных
* Строка 1: Одно целое число N (1 <= N <= 10^9).
Формат выходных данных
* Строка 1: Единственная строка вывода должна содержать один символ, ‘m’ или ‘o’.

Рекуррентные последовательности

✓ 6✗ 1—Войти и решать

Wifi Setup#89814

N (1 <= N <= 2000) коров Фермера Джона расположены на прямой линии (дороге от амбара до пастбища). ФД хочет расставить вдоль этой прямой точки беспроводного доступа в Internet, так чтобы все коровы были в зоне покрытия.
Стоимость wifi-станции зависит от расстояния, ан которое она может передавать сигнал. Станция с мощностью(радиусом действия) r стоит A + B*r , где A - фиксированная цена установки станции B - стоимость на 1 расстояния, на которое передается информация.
Если такая станция установлена в позиции x, то она может передавать данные до любой коровы, расположенной в интевале x-r...x+r. Допускается станция с мощностью передачи 0, но, поскольку r=0, она будет работать только для коровы, размещенной в самой точке x размещения станции.
По заданным величинам A и B, а также координатам коров, определите самый дешевый способ, которым ФД сможет обеспечить беспроводное покрытие всех своих коров.
PROBLEM NAME: wifi
Формат входных данных
* Строка 1: Три разделенных пробелом целых числа: N A B (0 <= A, B <= 1000).
* Строки 2..1+N: Каждая строка содержит одно целое число в диапазоне 0..1,000,000 описывающее размещение одной коровы.
Формат выходных данных
* Строка 1: Минимальная стоимость обеспечения беспроводным покрытием всех коров.
Примечание
Оптимальное решение - построить базовую станцию в позиции 3.5 (с мощностью/радиусом действия 3.5) и другую станции в позиции 100 с мощностью (радиусом действия) 0. Первая станция обеспечит покрытие коров 1 и 2, вторая - коровы 3.

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

✓ 0✗ 2—Войти и решать

Running Away From the Barn#89811

Время дойки на ферме Джона, но коровы сбежали. Ферма Джона - это множество из N (1 <= N <= 200,000) пастбищ, пронумерованных от 1 до N, и связанных N - 1 двунаправленными дорожками. Амбар расположен в пастбище 1 и любое пастбище достижимо от амбара.
Коровы бегут в сторону "от амбара" и они пробегают расстояние не больше чем L. Для каждого пастбища ФД хочет знать, в скольки различных пастбищах могут оказаться коровы, сбежавшие с этого пастбища.
Замечание: используйте 64-битные целые (int64 в Pascal, long long в C/C++ и long в Java) для хранения расстояний.
PROBLEM NAME: runaway
Формат входных данных
* Строка 1: 2 целых числа, N и L (1 <= N <= 200,000, 1 <= L <= 10^18)
* Строки 2..N: i-ая строка содержит два целых числа p_i и l_i. p_i (1 <= p_i < i) - первое пастбище на кратчайшем пути между пастбищем i и амбаром l_i (1 <= l_i <= 10^12) - длина этого пути
Формат выходных данных
* Строки 1..N: По одному числу в строке. Число в строке i - количество пастбищ, которые могут быть достигнуты из пастбища i, выбирая дороги, строго удаляясь от амбара (пастбище 1) с суммарной длиной не превышающей L.
Примечание
Корова из пастбища 1 может добежать до пастбищ 1, 2, 4. Корова из пастбища 2 может добежать до пастбищ 2, 3. Пастбища 3 и 4 - конечные, оттуда некуда бежать, можно только остаться в них.

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

✓ 0✗ 1—Войти и решать

Gangs of Instanbull_Cowstantinople#89810

Коровы сформировали банды, пронумерованные от 1 до M.
Теперь эти банды борются за контроль над большим пастбищем.
Каждую минуту одна корова идет в поле. Если это поле пустое, считается, что ее банда взяла контроль над ним. Если поле уже под контролем этой банды, то корова просто начинает на нем пастись. Иначе возникает конфликт между новой коровой, и той коровой из другой банды, которая там паслась.
В результате этого конфликта обе коровы "аннигилируются" (то есть выходят из своих банд и покидают это поле). Поле становится пустым и бесконтрольным. Никакая банда его не контролирует.
Беси знает сколько коров в каждой банде. Беси хочет чтобы ее банда контролировала поле после завершения конфликта.
Помогите Беси определить, может ли ее банда (номер 1) контролировать поле в конце.
Если это возможно, Беси хочет знать максимальное количество коров из ее банды, которое может остаться на поле в конце.
Выведите это количество и лексикографически раннюю перестановку коров, которая приведет к этому числу.
Перестановка X называется более ранней чем перестановка Y, если есть некоторое k, для которого X[k] < Y[k] и X[i]=Y[i] для всех i < k.
PROBLEM NAME: gangs
Формат входных данных
* Строка 1: N (1 <= N <= 100) и M (1 <= M <= N) разделенные пробелом. N - общее число коров во всех бандах. M - общее число банд.
* Строки 2..1+M: (1+i)-ая строка указывает количество коров в банде i. В каждой банде есть хотя бы одна корова.
Формат выходных данных
* Строка 1: Выведите YES на одной строке, если банда Беси может взять контроль над полем, иначе выведите NO.
* Строка 2: Если банда Беси сможет взять контроль над полем выведите здесь максимальное количество коров, которые там будут пастись после окончания конфликта.
* Строки 3..2+N: На (i+2)-ой вывести индекс банды коровы, которая должна появится на i-ой минуте на поле в лексикографически ранней перестановке которая обеспечит максимальное количество коров в поле после конфликта.
Примечание
Только одна корова из банды Беси может остаться на поле

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

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

First!#89809

Беси опять играет со строками. Она обнаружила, что изменяя порядок алфавита она може добиться, чтобы некоторая строка стала лексикографически раньше всех.
Например, среди строк
"omm", "moo", "mom", "ommnom"
она может сделать первой строку "mom", используя стандартный алфавит. и она может сделать первой строку "omm" используя алфавит "abcdefghijklonmpqrstuvwxyz". Однако Беси не знает как сделать первым слово "moo" или "ommnom"
Помогите Беси вычислить строки из ввода, которые можно сделать первыми изменив порядок букв в алфавите.
Чтобы определить, что строка X лексикографически раньше cтроки Y найдите индекс первого символа в котором они различаются j. Если такого индекса нет, тогда X лексикографически меньше чем Y, если X короче чем Y, иначе, X лексикографически раньше чем Y, если X[j] находится в алфавите раньше чем Y[j].

PROBLEM NAME: first
Формат входных данных
* Строка 1: целое N (1 <= N <= 30,000),количество строк, с которыми играет Беси
* Строки 2..1+N: Каждая строка содержит не пустую строку символов. Общее количество символов во всех строках не превысит 300,000. Все символы на вводе - маленькие латинские буквы от 'a' до 'z'. Во вводе нет повторяющихся строк.

Формат выходных данных
* Строка 1: одно число K, количество строк, которые могут быть лексикографически первыми.
* Строки 2..1+K: (1+i)-ая строка должна содержать i-ую строку, которая может быть лексикографически первой. Строки нужны выводить в том же порядке, в котором они следовали на вводе.
Примечание
Только "omm" и "mom" могут стать первыми.

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

✓ 1✗ 1—Войти и решать

Scrambled Letters#89808

Фермер Джон поддерживает алфавитно упорядоченный список имен своих N
(1 <= N <= 50,000) коров. Каждое имя коровы представлено уникальной
строкой от 1 до 20 маленьких латинских символов.

Беси, всегда создающая проблемы, переупорядочила имена коров в этом
списке, и также поменяла буквы в некоторых именах.

По заданному этому модифицированному списку определите для каждого
имени в списке самую маленькую и самую большую позицию, которую
могло занимать это имя в изначальном списке.

PROBLEM NAME: scramble

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

* Строка 1: Одно целое число N.

* Строки 2..1+N: Каждая из этиз строк содержит реорганизованное имя
одной из коров

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

* Строки 1..N: Строка i должна указывать, для входной строки i,
самую маленькую и самую большую позицию в исходном списке
на котором могла быть оригинальная версия строки i.

Примечание

Строка 'a' может быть только первой, а строка 'xyz' - только последней,
вне зависимости как переупорядочены их буквы .
Строки "essieb" и "elsie" могут занимать 2 или 3-ю позицию в зависимости
от той буквы, которая была первой в оригинальном имени:
например "bessie" (позиция 2) и "bessie" (позиция 3)
и наоборот
"sisbee" (позиция 3) и "ilees" (позиция 2)).

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

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

Meet and Greet#89807

Коровы очень вежливы, каждый раз при встрече они приветствуют коллегу дружеским 'moo'.
Бэси и Эльза ходят вдоль прямой вперед и назад. Начинают в точке 0 и двигаются с одинаковой скоростью. По описаниям движения каждой из коров определите количество 'moo', которыми они обменялись.
Беси и Эльза могут останавливать движение в различные точки времени, и никогда не гуляют более чем 1,000,000 единиц времени.
PROBLEM NAME: greetings
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа, B (1 <= B <= 50,000) и E (1 <= E <= 50,000).
* Строки 2..1+B: Эти B строк описывают движение Беси. Каждая строка содержит положительное целое, за которым следует символ "L" или "R", обозначающий пройденное Беси расстояние влево или вправо.
* Строки 2+B..1+B+E: Эти E строк описывают движение Эльзы. Каждая строка содержит положительное целое, за которым следует символ "L" или "R", обозначающий пройденное Эльзой расстояние влево или вправо.
Формат выходных данных
* Строка 1: Одно целое число, указывающее количество 'moo', которыми обменялись две коровы. Их начальное совместное положение в точке 0, не вызывает 'moo'.
Примечание
Беси и Эльза встречаются в моменты времени 7, 9, 13

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

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

Tile Exchanging#89805

Problem 3: Tile Exchanging [Ray Li]
Фермер Джон хочет покрыть пол в своем амбаре коллекцией квадратных плиток, которые он купил в магазине. К несчастью, Он не измерял точно размер своего амбара перед покупкой, поэтому сейчас он должен обменять часть плиток на другие, тоже квадратные, но других размеров.
N квадратных плиток которые ФД купил изначально имеют длины сторон A₁...A_N. Он хочет обменять часть из этих плиток так, чтобы общая сумма площадей всех плиток была ровно M.
При этом необходимо соблюсти правила обмена, установленные магазином: - плитка со стороной с длиной A_i может быть обменяна на другую плитку со стороной с длиной B_i за цену (A_i-B_i)* (A_i-B_i). Однако менять можно только ранее купленные плитки. Нельзя Менять плитку, полученную в результате обмена некоторой из ранее купленных плиток. Например, нельзя обменять плитку со стороной 3 на плитку со стороной 2 и потом плитку со стороной 2 поменять на плитку со стороной 1.
Определите минимальное количество денег, которое требуется ФД, чтобы сделать сумму площадей плиток равной M. Выведите –1, если невозможно получить площадь M.
PROBLEM NAME: tilechng
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа, N (1<=N<=10) и M (1<=M<=10,000).
* Строки 2..1+N: Каждая строка содержит одно целое число (от A₁ до A_N, описывающих длины сторон входных квадратных плиток (1<=A_i<=100).
Формат выходных данных
* Строка 1: Минимальная стоимость обменов чтобы получить площадь M, или –1, если получить площадь M невозможно.
Примечание
Обменяем первую плитку со стороной 3 на плитку со стороной 2 square, а вторую плитку со стороной 3 на плитку со стороной 1. Это дает суммарную площадь 4+1+1=6 за цену 4+1=5.

Задача о рюкзаке

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