Информатика

7 600 задачвместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Luxury River Cruise#89914

Фермер Джон берет Беси и других коров в круиз по сети рек с N портами (1 <= N <= 1,000) пронумерованными от 1 до N, начиная в порту 1. Из каждого порта ведут ровно две реки и движение одностороннее.
В каждом порту нужно выбирать куда плыть - по левой реке или по правой реке, Туристический маршрут состоит из последовательности из M (1 <= M <= 500) направлений (каждое их которых влево или вправо), которую необходимо повторить K раз (1 <= K <= 1,000,000,000).
Помогите ФД определить, где закончится его маршрут.
PROBLEM NAME: cruise
Формат входных данных
* Строка 1: Три разделенных пробелом целых числа N, M, K.
* Строки 2..N+1: Строка i+1 содержит два разделенных пробелом целых числа, представляющих номера портов влево и вправо соответственно.
* Сроки N+2..N+2: M разделенных пробелами символов, 'L' или 'R'. 'L' представляет выбор 'влево' и 'R' представляет выбор 'вправо'.

Формат выходных данных
* Строка 1: Одно целое число - номер порта, в котором завершится круиз
Примечание
После первой итерации последовательности, ФД окажется в порту 2 (1 -> 2 -> 3 -> 2), после второй - в порту 3 (2 -> 3 -> 4 ->3), после третьей - в порту 4 (3 -> 4 -> 1 -> 4).

Задачи на моделирование
—Войти и решать
Fuel Economy#89913

Фермер Джон решил в отпуске проехать через всю страну. Чтобы коровы не скучали, он решил арендовать огромный грузовик и взять коров с собой.
Грузовик имеет огромный бензобак, который может вместить до G (1 <= G <= 1,000,000) единиц топлива. Грузовик потребляет одну единицу топлива на одну единицу расстояния. ФД собирается проехать D (1 <= D <= 1,000,000,000) единиц расстояния.
ФД знает, что ему придется несколько раз останавливаться для дозаправки, поэтому он составил список всех N (1 <= N <= 50,000) заправочных станций вдоль маршрута. Для каждой станции i он записал ее расстояние Xi (0 <= Xi <= D) от начала маршрута, а также цену Yi (1 <= Yi <= 1,000,000) заправки единицы топлива на этой станции.
По заданной информации и тому факту, что ФД начинает свое путешествие имея ровно B (0 <= B <= D) единиц топлива, определите минимальное количество денег, которое он должен заплатить за дозаправки топливом чтобы достичь точки назначения. Если достичь точки назначения невозможно, выведите -1. Заметим, что ответ на задачу может не помещаться в стандартное 32-битное целое.
PROBLEM NAME: fuel
Формат входных данных
* Строка 1: Четыре разделенных пробелом целых числа: N, G, B, D.
* Строки 2..1+N: Каждая строка содержит два целых числа Xi и Yi , описывающих заправочную станцию i.
Формат выходных данных
* Строка 1: Минимальная цена, которую ФД должен заплатить, чтобы доехать до места назначения или -1, если доехать невозможно.
Примечание
ФД проезжает 2 единицы расстояния и останавливается, чтобы заправить 2 единицы топлива (цена 40*2), это позволяет доехать ему до станции в позиции 5, где он заправляет полный бак (цена 7*10). Когда он доезжает до позиции 10, он добавляет еще 2 единицы топлива (цена 12*2). Общая цена равна 174.
Жадный алгоритм
—Войти и решать
Photo#89911

Фермер Джон решил собрать панорамное фото ряда из своих N (1 <= N <= 200,000) коров, пронумерованных от 1 до N. Он сделал M M (1 <= M <= 100,000) снимков, каждый из которых покрывает непрерывный диапазон коров. Снимок i содержит коров с номерами от ai до bi включительно. Коллективное фото может и не покрывать каждую отдельную корову.
ФД заметил интересный феномен: каждый снимок содержит ровно одну корову с пятном. Основываясь на данных снимков, определите максимально возможное количество коров с пятнами. Выведите -1, если невозможно назначить пятна коровам так, чтобы соответствовать данным о снимках.
PROBLEM NAME: photo
Формат входных данных
* Строка 1: Два целых числа N и M.
* Строки 2..M+1: Строка i+1 содержит ai и bi.
Формат выходных данных
* строка 1: Максимально возможное количество коров с пятнами у ФД, или -1, если решения нет.
Примечание
Из последней фотографии мы получаем, что корова 3 или корова 4 обязательно должны быть с пятном. При любом выборе будет выполнено свойство и для первых двух снимков.
Жадный алгоритм
—Войти и решать
Photo#89909

ФД хочет сфотографировать все свои N коров (2 <= N <= 1,000,000,000), которые выстроились в линию и последовательно пронумерованы от 1 до N. Каждая фотография может вместить некоторый последовательный диапазон коров, и ФД хочет, чтобы каждая корова была, как минимум, на одной фотографии.
К несчастью, имеется K недружественных пар коров (1 <= K <= 1000), которые отказываются находиться на одной фотографии. Вам даны позиции этих недружественных пар коров, определите минимальное количество фотографий, которые придется сделать ФД.
PROBLEM NAME: photo
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа, N и K.
* Строки 2..K+1: Строка i+1 содержит два целых числа, Ai и Bi, указывающих, что коровы на позициях Ai и Bi недружественные, и поэтому не могут быть на одной и той же фотографии.
Формат выходных данных
* Файл 1: Одно целое число, указывающее минимальное количество фотографий, которые должен сделать ФД
Примечание
ФД должен сделать 3 фотографии: - Одна в диапазоне от 1 до 2. - Одна в диапазоне от 3 до 5. - Одна в диапазоне от 6 до 7.
Отрезки
—Войти и решать
Haywire#89908

N коров (4 <= N <= 12, N четное), построили примитивную систему для проводной коммуникации пар дружественных коров
Каждая корова имеет ровно 3 друзей в амбаре и коровы должны занять один ряд в амбаре из N стойл. Провод длины L требуется, чтобы соединить друзей в стойлах на расстоянии L. Например, если друзья находятся в стойлах 4 и 7, то требуется провод длины 3, чтобы их соединить.
Каждая пара коров должна быть соединена отдельным проводом. Определите минимальную длину провода, требуемую для организации такой сети наилучшим образом.
PROBLEM NAME: haywire
Формат входных данных
* Строка 1: Цело число N. Коровы пронумерованы 1..N.
* Строки 2..1+N: Каждая строка содержит три разделенных пробелом целых числа в диапазоне от 1 до N. Строка i+1 содержит числовые идентификаторы трех друзей коровы i. Если корова i дружит с коровой j, то и корова j дружит с коровой i.
Формат выходных данных
* Строка 1: Минимальная суммарная длина провода, чтобы соединить все пары дружественных коров.
Примечание
Лучшее упорядочивание коров есть 6, 5, 1, 4, 2, 3, и оно требует только 17 единиц длины провода.
битмаскидпПеребор
—Войти и решать
Bovine Ballet#89907

Чтобы сломать стереотипное представление о коровах как о неловких созданиях, корова Беси пошла на балетные курсы. Ее финальное представление состоится на следующей неделе, и ФД хочет помочь ей, построив прямоугольную сцену, достаточную для всего ее представления.
Танец выполняется на прямоугольной сцене, состоящей из квадратных ячеек размером 1 х 1. Ноги Беси описываются следующим образом:
FR: передняя правая нога FL: передняя левая нога RR: задняя правая нога RL: задняя левая нога
В начале танца все 4 ноги находятся в соседних ячейках и формируют квадрат как показано ниже, причем Беси смотрит на север.
FL FR RL RR
Танец Беси - это последовательность из N инструкций (1 <= N <= 1000), где каждая инструкция предписывает либо переместить одну ногу на одну ячейку, или повернуться на 90 градусов по часовой стрелке.
Инструкции переместить ногу состоят из 3 символов, первые два описывают какую ногу перемещать, а последний символ указывает направление движения (F = вперед, B = назад, R = вправо, L = влево). Например, FRF означает переместить правую ногу вперед на одну ячейку, а RLR - означает переместить заднюю левую ногу вправо. Конечно направление движения относительно того направления, куда сориентирована Беси.
Инструкция на поворот также состоит из 3 символов, первые два указывают единственную ногу Беси, которая останется в той же клетке где была и вокруг которой она повернется на 90 градусов по часовой стрелке. В этом случае последний символ - P (поворот). Например, инструкция "FRP" означает, что Беси должна повернуться на 90 градусов по часовой стрелке вокруг своей стационарной передней правой ноги. Например, если Беси ориентирована на север, и ноги расположены так: .. .. .. .. .. FR .. FL .. .. RL RR
то после инструкции "FRP" ее ноги будут расположены так, а Беси будет ориентирована на восток:
RL FL .. RR .. FR .. .. .. .. .. ..
Вам даны N инструкций танца Беси, вычислите минимальную площадь сцены прямоугольной формы, необходимой для того чтобы ноги Беси находились на ней во время всего танца.
Если Беси шагнет в ту же ячейку, где сейчас находится другая нога, она упадет, и танец закончится, в этом случае выводите -1. Заметим, что это единственный случай, когда Беси упадет. Она хорошо напрактиковалась, и ее ноги могут находиться в самых разных, даже странных комбинациях, например, когда ее задние ноги находятся впереди передних.
PROBLEM NAME: ballet
Формат входных данных
* Строка 1: Цедое число N.
* Строки 2..1+N: Каждая строка содержит одну из 3-символьных инструкций.
Формат выходных данных
* Строка 1: Минимальная площадь прямоугольной сцены, содержащей ноги Беси во время всего танца, или -1, если Беси упадет.
Примечание
Беси нужна сцена 4 x 4, ее ноги будут располагаться так:
.. .. .. .. .. .. .. .. (смотрит на север) .. .. FL FR .. .. RL RR
After FRF:
.. .. .. .. .. .. .. FR (смотрит на север) .. .. FL .. .. .. RL RR
After FRP:
.. RL FL .. .. RR .. FR (смотрит на восток) .. .. .. .. .. .. .. ..
After RLB:
RL .. FL .. .. RR .. FR (смотрит на восток) .. .. .. .. .. .. .. ..
Задачи на моделирование
—Войти и решать
Blink#89906

Недовольный освещением своего амбара, Фермер Джон установил новый канделябюр состоящий из N (3 <= N <= 16) лампочек, размещенных по кругу.
Коровы играют в следующую игру: в момент времени T они переключают состояние всех лампочек, сосед которых слева был переключен в момент времени T-1. Они продолжают это процесс, в течение B единиц времени (1<=B<=10^15). Заметим, что B может быть таким большим, что не поместится в стандартное 32-битное целое.
По заданному начальному состоянию всех лампочек определите их конечное состояние по истечению B единиц времени.
PROBLEM NAME: blink
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа, N и B.
* Строки 2..1+N: Строка i+1 содержит начальное состояние лампочки i, r 0 (off) или 1 (on).
Формат выходных данных
* Строки 1..N: Строка i должна содержать финальное состояние лампочки i, 0 (off) или 1 (on).
Примечание
Состояние лампочек переключалось следующим образом: Time T=0: 1 0 0 0 0 Time T=1: 1 1 0 0 0 Time T=2: 1 0 1 0 0 Time T=3: 1 1 1 1 0 Time T=4: 1 0 0 0 1 Time T=5: 0 1 0 0 1 Time T=6: 1 1 1 0 1
Задачи на моделирование
—Войти и решать
Pogo-Cow#89905

Для ускорения своей призовой коровы Беси, Фермер Джон имеет палку для каждой из ног Беси. Теперь Беси научилась ускоряться, но еще не научилась замедляться.
Для тренировки ФД разметил путь по прямой. В различных позициях этого пути он разместил N целей, в которых Беси должна приземляться (1 <= N <= 1000). Цель I расположена в позиции x(i) и имеет цену P(i) очков, которые получит Беси, если приземлится в этой точке.
Беси начинает прыжки из любой из этих целей по своему выбору, и ей разрешено двигаться только в одном направлении, прыгая от цели к цели. Каждый прыжок должен быть по расстоянию не меньше, чем предыдущий, и приземляться в целевой точке. Беси получает соответствующие очки за каждую цель, которой коснётся, включая ту, с которой начнёт. Определите максимальное количество очков, которое она может получить.

PROBLEM NAME: pogocow
Формат входных данных
* Строка 1: Целое число N.
* Строки 2..1+N: Строка i+1 содержит x(i) и p(i), целые в диапазоне 0..1,000,000.
Формат выходных данных
* Строка 1: Максимальное количество очков, которое может получить Беси.
Примечание
Беси прыгает из позиции x=4 (8 очков) в позицию 5 (6 очков), в позицию 7 (6 очков), в позицию 10(5 очков).

Динамическое программирование
—Войти и решать
Farmer John has no Large Brown Cow#89904

Фермер Джон любит коллекционировать как можно больше типов коров, кроме нескольких типов, которые перечислены в специальном списке из N строк (1 <= N <= 100). Этот список выглядит так:
Farmer John has no large brown noisy cow. Farmer John has no small white silent cow. Farmer John has no large spotted noisy cow.
Каждый элемент списка описывает недопустимый тип в виде короткого списка прилагательных, и содержит одно и то же количество прилагательных (3, в данном примере). Количество прилагательных в строке содержится в диапазоне от 2 до 30.
У ФД имеется корова подходящая под каждую возможную комбинацию прилагательных, не имеющуюся в этом списке. В данном примере первое прилагательное имеет два значения (large, small); второе – три (brown, white, spotted), а третье – два (noisy, silent). Это даёт 2*3*2 = 12 различных комбинаций и у ФД есть корова для каждой из них, кроме тех, которые указаны в списке. Например large, white, noisy – одна из его 9 коров. У ФД не более 1,000,000,000 коров.
Если ФД упорядочит описания своих коров по алфавиту – какая корова будет K-ая по списку?
Частичное оценивание: Из 10 тестов на задачу в тестах 1..4 будет не более двух прилагательных в строке списка. В тестах 1..6 каждое из прилагательных будет иметь ровно 2 различных значения (во всех других тестах каждое прилагательное может иметь от 1 до N различных значений).
PROBLEM NAME: nocow
Формат входных данных
* Строка 1: Два целых числа, N и K.
* Строки 2..1+N: Каждая строка содержит предложение вида "Farmer John has no large spotted noisy cow.". Каждое прилагательное в этом списке – строка не более 10 маленьких латинских букв Конец предложения определяется символами "cow."
Формат выходных данных
* Строка 1: Описание K-ой коровы на ферме.
Примечание
Вот список имеющихся коров в алфавитном порядке
large brown silent large spotted silent large white noisy large white silent small brown noisy small brown silent small spotted noisy small spotted silent small white noisy
7-ая корова в этом списке - "small spotted noisy".
Комбинаторные структуры
—Войти и решать
Crowded Cows#89903

N коров (1 <= N <= 50,000) Фермера Джона пасутся вдоль одномерного забора. Корова с номером I находится в точке x(i) и имеет высоту h(i) (1 <=x(i),h(i) <= 1,000,000,000).
Корове «тесно», если имеется другая корова слева от нее на расстоянии ближе, чем её удвоенная высота внутри расстояния D и также другая корова справа от неё на расстоянии ближе чем её удвоенная высота внутри расстояния D (1 <= D <= 1,000,000,000). ФД хочет посчитать количество коров, которым тесно. Помогите ему.
PROBLEM NAME: crowded
Формат входных данных
* Строка 1: Два целых числа, N и D.
* Строки 2..1+N: Строка i+1 содержит целые числа x(i) и h(i). Расположения всех коров различны.
Формат выходных данных
* Строка 1: Количество коров, которым тесно.
Примечание
«Тесно» коровам в позициях x=5 и x=6.
Использование сортировки
—Войти и решать
Line of Sight#89901

N (1 <= N <= 50,000) коров Фермера Джона распложены в различных точках двумерного пастбища. В середине пастбища расположен круглый элеватор. Коровы на противоположных сторонах элеватора не могут видеть друг друга, поскольку он заслоняет обзор.
Определите количество пар коров, которые могут видеть друг друга по прямой.
Элеватор расположен в точке (0,0) и имеет радиус R. Нет коров расположенных внутри или на границе этого круга. Также нет коров, Расположенных на касательных к этому кругу. R находится в диапазоне 1..1,000,000, и каждая корова находится в точке с целыми координатами в диапазоне -1,000,000..+1,000,000.
PROBLEM NAME: sight
Формат входных данных
* Строка 1: Два целых числа: N и R.
* Строки 2..1+N: Каждая строка содержит два целых числа, указывающих (x,y) координаты коровы
Формат выходных данных
* Строка 1: Количество пар коров, которые видят друг друга.
Примечание
Из 6 возможных пар не видят друг друга две «диагональные» пары коров: (-10,0) и (10,0), а также (0,-10) и (0,10)
Вычислительная геометрия
—Войти и решать
Empty Stalls#89900

Новый амбар Фермера Джона представляет собой большой круг из N стойл (2 <= N <=3,000,000), пронумерованных от 0 до N-1, стойло N-1 соседствует со стойлом 0.
В конце каждого дня коровы ФД возвращаются в амбар, одна за одной, У каждой имеется предпочтительный номер стойла, который она хочет занять. Однако если это место уже занято другой коровой, она идёт вперёд последовательно от этого стойла, пока не найдёт первое не занятое стойло, которое она и займёт. Если она пройдёт стойло N-1, она продолжит поиск со стойла 0.
По заданному предпочтительному номеру для каждой коровы определите минимальный номер стойла, который останется незанятым после того как все коровы вернутся в амбар. Заметим, что ответ на этот вопрос не зависит от того, в каком порядке возвращаются коровы
Для того, чтобы избежать проблем с огромным вводом, данные вводятся в специальном формате, использующем K строк (1 <= K <=10,000) вида
X Y A B
Здесь описываются предпочтительные стойла X Y коров: X коров предпочитают каждое из стойл f(1) .. f(Y), где f(i)= (Ai + B) mod N. Значения A и B лежат в диапазоне 0...1,000,000,000.
Не забудьте про стандартное для всех задач ограничение на память – 64 Мбт.
PROBLEM NAME: empty
Формат входных данных
* Строка 1: Два разделённых пробелом целых числа: N и K.
* Строки 2..1+K: каждая строка содержит целые числа X Y A B, смысл которых описан выше. Общее количество коров описываемых этими числами не превысит N-1. Коровы могут добавляться в одно и тоже стойло разными из этих строк.
Формат выходных данных
* Строка 1: Минимальный индекс не занятого стойла.
Примечание
Все стойла будут заняты кроме стойла с номером 5.
Алгоритмы обработки
—Войти и решать
Goldilocks and the N Cows#89899

На ферме Goldilocks имеется N коров (1 <= N <=20,000), очень чувствительных к температуре.
Для каждой коровы указывается диапазон температур A(i)..B(i), которые допустимы. (0 <= A(i) <= B(i) <= 1,000,000,000). Если температура TB(i), то этой корове слишком жарко и она производит Z единиц молока. Y всегда больше чем и X, и Z.
По данным X Y Z а также наборам допустимых температур для каждой коровы, определите максимальное количество молока, которое может получить Goldilocks установкой оптимальной температуры (единой для всех коров).
Z Y Z – целые в диапазоне от 0 до 1000, а температура может быть установлена в любое целое значение.
Частичное оценивание: Из десяти тестов для этой задачи в тестах 1..4 B(i)<=100 для каждой коровы, и в тестах 1..6 значение N не превышает 1000.
PROBLEM NAME: milktemp
Формат входных данных
* Строка 1: Четыре разделённых пробелом целых числа: N X Y Z.
* Строки 2..1+N: Строка 1+i содержит два разделённых пробелом целых числа : A(i) B(i).
Формат выходных данных
* Строка 1: Максимальное количество молока, которое можно получить установкой оптимальной температуры в амбаре.


Примечание
Если установить температуру в 7 или 8, то коровам с номерами 1 и 4 будет комфортабельно, корове 2 будет жарко, а корове 3 – холодно. Всего будет произведено 31 единица молока.

Сортировка событий
—Войти и решать
Farmer John has no Large Brown Cow#89898

Фермер Джон любит коллекционировать как можно больше типов коров, кроме нескольких типов, которые перечислены в специальном списке из N строк (1 <= N <= 100). Этот список выглядит так:
Farmer John has no large brown noisy cow. Farmer John has no small white silent cow. Farmer John has no large spotted noisy cow.
Каждый элемент списка описывает недопустимый тип в виде короткого списка прилагательных, и содержит одно и то же количество прилагательных (3, в данном примере). Количество прилагательных в строке содержится в диапазоне от 2 до 30.
У ФД имеется корова подходящая под каждую возможную комбинацию прилагательных, не имеющуюся в этом списке. В данном примере первое прилагательное имеет два значения (large, small); второе – три (brown, white, spotted), а третье – два (noisy, silent). Это даёт 2*3*2 = 12 различных комбинаций и у ФД есть корова для каждой из них, кроме тех, которые указаны в списке. Например large, white, noisy – одна из его 9 коров. У ФД не более 1,000,000,000 коров.
Если ФД упорядочит описания своих коров по алфавиту – какая корова будет K-ая по списку?
Частичное оценивание: Из 10 тестов на задачу в тестах 1..4 будет не более двух прилагательных в строке списка. В тестах 1..6 каждое из прилагательных будет иметь ровно 2 различных значения (во всех других тестах каждое прилагательное может иметь от 1 до N различных значений).
PROBLEM NAME: nocow
Формат входных данных
* Строка 1: Два целых числа, N и K.
* Строки 2..1+N: Каждая строка содержит предложение вида "Farmer John has no large spotted noisy cow.". Каждое прилагательное в этом списке – строка не более 10 маленьких латинских букв Конец предложения определяется символами "cow."
Формат выходных данных
* Строка 1: Описание K-ой коровы на ферме.
Примечание
Вот список имеющихся коров в алфавитном порядке
large brown silent large spotted silent large white noisy large white silent small brown noisy small brown silent small spotted noisy small spotted silent small white noisy
7-ая корова в этом списке - "small spotted noisy".
Комбинаторика
—Войти и решать
Combination Lock#89897

Фермер Джон купил комбинаторный замок на двери, чтобы коровы не разбежались. Зная, что его коровы очень умные, ФД хочет сделать нелёгким дело открытия замка простым перебором большого числа различных комбинаций. На замке имеется три диска с числами от 1 до N (1 По заданным комбинациям ФД и мастер-шифру, определите количество различных установок дисков, которые откроют замок. Порядок имеет значение, поэтому комбинация (1,2,3) отличается от комбинации (3,2,1).
PROBLEM NAME: combo
Формат входных данных
* Строка 1: Целое число N.
* Строка 2: Три разделенных пробелом целых числа, указывающих комбинацию ФД
* Строка 3: Три разделенных пробелом целых числа, указывающих комбинацию мастер-шифра (возможно совпадающую с комбинацией ФД).
Формат выходных данных
* Строка 1: Количество различных установок дисков открывающих замок.
Перебор
—Войти и решать
The Cow Run#89896

Фермер Джон забыл заделать дыру в изгороди на своей ферме и его N (1 <= N <= 1,000) коров сбежали и бедокурят. Каждая минута, когда корова находится вне изгороди, она "бедокурит" на 1 доллар. ФД должен посетить каждую корову, чтобы "усмирить" ее и прекратить долларовые потери от нее.
К счастью, коровы находятся вдоль одной прямой на различных растояниях от фермы. ФД знает расстояние Pi (-500,000 <= Pi <= 500,000, Pi != 0) каждой коровы i относительно ворот (позиция 0), из которых он стартует.
ФД двигается на 1 единицу расстояния за минуту и "усмиряет" корову мгновенно. Определите порядок, в котором ФД дожен посещать коров, так чтобы минимизировать свои долларовые потери.
PROBLEM NAME: cowrun
Формат входных данных
* Строка 1: Количество коров, N.
* Строки 2..N+1: Строка i+1 содержит целое число Pi.
Формат выходных данных
* Строка 1: Минимальная общая стоимость долларовых потерь
Примечание
Оптимальный порядок посещения --2, 3, 7, -12. ФД прибудет в позицию -2 на 2-ой минуте и получит ущерб в два доллара от этой коровы.
Потом он проследует в позицию 3 (расстояние 5), итого ущерб = 2+5=7 долларов от второй коровы.
Затем он потратит 4 минут чтобы добраться до коровы в позиции 7, с общей стоимостью потерь от этой коровы 7+4 = 11 долларов.
Наконец, он потратит 19 минут чтобы перейти в точку -12, и стоимость потерь от этой коровы будет 11 + 19 = 30 долларов.
Общие потери от всех коров будут 2 + 7 + 11 + 30 = 50 долларов.
Динамическое программирование
—Войти и решать
Poker Hands#89895

Беси и ее подружки играют в уникальную версию игры в покер с колодой из N (1 <= N <= 100,000) различных рангов, для удобства пронумерованных от 1 до N (в обычной колоде N=13). В этой игре имеется только один тип руки, который корова может играть: можно выбрать карту, помеченную i и карту, помеченную j и играть все карты с каждым значением от i до j. Такой тип руки называется "straight".
У Беси на руках сейчас ai карт ранга i (0 <= ai <= 100000). Помогите ей определить минимальное количество рук, которое она должна сыграть, чтобы избавиться от всех своих карт.
PROBLEM NAME: poker
Формат входных данных
* Строка 1: Целое число N.
* Строки 2..1+N: Строка i+1 содержит значение величины ai.
Формат выходных данных
* Строка 1: Минимальное количество "straights", чтобы Беси избавилась от всех своих карт.
Примечание
Беси может играть следующие straight: 1-5 1-2 4-5 2-2 (2 штуки) 5-5 Всего 6, чтобы избавится от всех карт.
Жадный алгоритм
—Войти и решать
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.
Вычислительная геометрия
—Войти и решать
Necklace#89892

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

Чтобы окончательно решить вопрос кто быстрее, Беси и ее подруга Эльза решили провести гонки вокруг фермы.
Обе коровы стартуют в одном и том же месте, в одно и то же время и начинают бежать в одном направлении. Прогресс каждой коровы описывается серией отрезков, в течение которого данная корова имеет одинаковую скорость. Например, Бэси может бежать со скоростью 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 единиц расстояния, затем бежали вместе в течение одной единицы времени. Беси затем вырвалась вперед (первое изменение лидерства), затем ее обошла Беси (второе изменение лидерства), Беси так и осталась лидером до конца гонки.
Задачи на моделирование
—Войти и решать
Поделиться
Класснуть