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

Команда на турнир#93210

Тренер школьной команды программистов готовится к турниру. В школе всего \(n\) учеников, у каждого есть свой рейтинг \(p_i\) — количество очков, набранных на тренировках.

На турнир нужно отправить ровно \(k\) учеников. Сила команды оценивается как суммарный рейтинг её участников. Тренер хочет, чтобы суммарный рейтинг был максимально возможным.

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

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

В первой строке — два целых числа \(n\) и \(k\) (\(1 \le k \le n \le 2 \cdot 10^5\)) — общее количество учеников и размер команды.

Во второй строке — \(n\) целых чисел \(p_i\) (\(0 \le p_i \le 10^9\)), разделённых пробелами, — рейтинг каждого ученика.

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

Одно целое число — максимальный суммарный рейтинг команды.

Примечание

В первом примере нужно выбрать трёх учеников из пяти. Лучше всего взять с рейтингами 8, 5 и 3 — в сумме 16.

Во втором примере в команду идут все четверо учеников, поэтому ответ — сумма всех рейтингов.

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

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

Книги на полке#93208

Библиотекарь расставляет книги на полке длиной \(W\) сантиметров. У него есть \(n\) книг; \(i\)-я книга имеет размеры \(a_i \times b_i\) сантиметров.

Каждую книгу можно поставить на полку двумя способами: одной стороной к соседней книге (тогда она занимает вдоль полки \(a_i\) сантиметров) или другой стороной (тогда \(b_i\) сантиметров). Способ расстановки выбирается для каждой книги независимо.

Библиотекарь хочет поставить на полку максимально возможное количество книг. Какие именно книги — неважно, лишь бы их число было наибольшим. Суммарная ширина расставленных книг не должна превышать длины полки.

Помогите ему определить это максимальное число книг.

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

В первой строке — два целых числа \(n\) и \(W\) (\(1 \le n \le 2 \cdot 10^5\), \(1 \le W \le 10^{14}\)) — количество книг и длина полки.

В следующих \(n\) строках — по два целых числа \(a_i\) и \(b_i\) (\(1 \le a_i, b_i \le 10^9\)) — размеры \(i\)-й книги.

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

Одно целое число — максимальное количество книг, которые можно расставить на полке.

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

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

Доски в кузов грузовика#93207

На стройплощадку нужно перевезти доски. У бригадира есть грузовик с длинным узким кузовом длиной \(L\) сантиметров — доски укладываются в кузов в один ряд вдоль кузова. На складе лежат \(n\) досок; каждая доска имеет две стороны: толщину \(a_i\) и ширину \(b_i\) сантиметров.

Каждую доску можно положить в кузов двумя способами: плашмя (тогда она занимает вдоль кузова \(a_i\) сантиметров) или на ребро (тогда \(b_i\) сантиметров). Способ укладки выбирается для каждой доски независимо.

Бригадир хочет за один рейс увезти максимальное количество досок. Какие именно — неважно: нужно лишь максимизировать число досок в кузове. Суммарная длина уложенных досок не должна превышать длины кузова.

Определите это максимальное число.

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

В первой строке — два целых числа \(n\) и \(L\) (\(1 \le n \le 2 \cdot 10^5\), \(1 \le L \le 10^{14}\)) — количество досок на складе и длина кузова в сантиметрах.

В следующих \(n\) строках — по два целых числа \(a_i\) и \(b_i\) (\(1 \le a_i, b_i \le 10^9\)) — размеры сторон \(i\)-й доски в сантиметрах.

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

Одно целое число — максимальное количество досок, которые можно увезти за один рейс.

Примечание

В первом примере выгодно каждую доску укладывать той стороной, которая короче. Тогда доски займут 2, 4, 3 и 1 см — всего 10 см, помещаются все 4.

Во втором примере даже самая тонкая доска толще кузова, ни одну доску положить нельзя.

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

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

Рейтинг участников#93206

Школьник Тимур участвует в серии онлайн-соревнований по программированию. За весь год проходит \(n\) соревнований, и Тимур заранее знает, сколько очков он может набрать в каждом из них: за \(i\)-е соревнование он получит \(s_i\) очков.

По правилам рейтинга, в итоговую сумму идут только \(k\) соревнований по выбору участника (остальные просто не засчитываются). Тимур хочет выбрать такие \(k\) соревнований, чтобы получить максимальную суммарную сумму очков.

Помогите ему вычислить эту максимальную сумму.

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

В первой строке — два целых числа \(n\) и \(k\) (\(1 \le k \le n \le 10^5\)) — общее количество соревнований и сколько из них идут в зачёт.

Во второй строке — \(n\) целых чисел \(s_i\) (\(0 \le s_i \le 10^9\)), разделённых пробелами, — количество очков за каждое соревнование.

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

Одно целое число — максимальная суммарная сумма очков за \(k\) выбранных соревнований.

Примечание

В первом примере из пяти соревнований с очками \(1, 5, 3, 8, 2\) надо выбрать три. Лучше всего взять соревнования с очками 8, 5 и 3 — в сумме 16.

Во втором примере в зачёт идут все соревнования, так что ответ — сумма всех очков.

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

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

Сигналы с радиовышки#93205

Вдоль прямой трассы расположено \(n\) посёлков. У каждого посёлка известна его координата на трассе — целое число \(p_i\). Связисты хотят покрыть все посёлки радиосигналом, установив на трассе несколько радиовышек.

Каждая вышка имеет радиус покрытия 1 километр: она покрывает всё, что находится на расстоянии не более 1 от её координаты. То есть вышка, установленная в точке \(x\), покрывает отрезок \([x - 1; \, x + 1]\). Посёлок считается покрытым, если его координата попадает в покрытие хотя бы одной вышки (граничная точка тоже считается покрытой).

Вышки можно ставить в любых точках прямой, в том числе с нецелыми координатами. Нужно установить минимальное количество вышек, чтобы все посёлки получили сигнал.

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

В первой строке — целое число \(n\) (\(1 \le n \le 10^5\)) — количество посёлков.

Во второй строке — \(n\) целых чисел \(p_i\) (\(-10^9 \le p_i \le 10^9\)), разделённых пробелами, — координаты посёлков. Координаты могут повторяться (несколько посёлков в одной точке).

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

Одно целое число — минимальное количество радиовышек, необходимое для покрытия всех посёлков.

Примечание

В первом примере посёлки находятся в точках 1, 3, 5. Одна вышка, установленная в точке 2, покроет отрезок \([1; 3]\) и захватит посёлки в точках 1 и 3. Для посёлка в точке 5 нужна ещё одна вышка, например в точке 4 или в точке 5. Итого 2 вышки.

Во втором примере все посёлки близко друг к другу и покрываются одной вышкой.

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

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

Экспедиция на Марс#93204

Центр управления отправляет на Марс грузовую капсулу. Она может поднять не более \(W\) килограммов полезной нагрузки. Учёные отобрали \(n\) научных приборов, которые хотят отправить в этой миссии; масса каждого прибора равна \(w_i\) килограммов.

Каждый прибор можно либо отправить целиком, либо оставить на Земле — разбирать их на части нельзя. Место в капсуле есть: ограничение только по массе. Цель миссии — отправить максимальное количество разных приборов, чтобы провести как можно больше экспериментов (какие именно приборы полетят — неважно, лишь бы число было максимальным).

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

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

В первой строке — два целых числа \(n\) и \(W\) (\(1 \le n \le 10^5\), \(1 \le W \le 10^9\)) — количество приборов и грузоподъёмность капсулы в килограммах.

Во второй строке — \(n\) целых чисел \(w_i\) (\(1 \le w_i \le 10^4\)), разделённых пробелами, — масса каждого прибора в килограммах.

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

Одно целое число — максимальное количество приборов, которые можно отправить на Марс.

Примечание

В первом примере лучше всего отправить приборы массами \(1 + 2 + 3 + 4 = 10\) кг — ровно помещаются в капсулу, итого 4 прибора. Прибор массой 7 кг остаётся на Земле.

Во втором примере каждый прибор по отдельности весит больше грузоподъёмности капсулы. Ни один прибор отправить нельзя.

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

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

Расписание кружков#93203

В актовом зале школы может проходить только одно мероприятие в каждый момент времени. На проведение актового зала подано \(n\) заявок от разных кружков. Каждая заявка — это интервал времени \([l_i; r_i]\): кружок хочет занять зал с минуты \(l_i\) по минуту \(r_i\) включительно.

Два кружка не могут проходить в зале одновременно: если один занимает время \([l_1; r_1]\), а другой — \([l_2; r_2]\), эти интервалы не должны пересекаться. Если один кружок заканчивается ровно в ту минуту, когда начинается другой, это тоже считается пересечением.

Директор хочет одобрить как можно больше заявок. Какое максимальное количество кружков можно разместить в зале за день?

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

В первой строке — целое число \(n\) (\(1 \le n \le 10^5\)) — количество заявок.

В следующих \(n\) строках — по два целых числа \(l_i\) и \(r_i\) (\(0 \le l_i < r_i \le 10^9\)) — время начала и время окончания каждой заявки.

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

Одно целое число — максимальное количество заявок, которые можно одобрить.

Примечание

В первом примере можно одобрить заявки \([1; 3]\) и \([4; 7]\) — они не пересекаются.

Во втором примере оптимально взять \([2; 3]\) и \([5; 7]\).

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

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

Классифайд - 1#91378

Вася открыл собственный классифайд (доску объявлений). Устроен его классифайд следующим образом: для каждого типа товара продавец с номером \(i\) может выставить на продажу только одну единицу товара и заранее указывает минимальную цену \(S_i\), за которую он готов его продать. Каждый покупатель может купить только одну единицу товара, покупатель с номером \(j\) указывает максимальную цену \(B_j\), за которую он готов купить товар. Раз в день Вася собирает все заявки и распределяет покупателей и продавцов, которые заключат сделку и по какой цене. При этом сделка между продавцом \(i\) и покупателем \(j\) может состояться только если \(S_i \le B_j\) по любой цене от \(S_i\) до \(B_j\) (цену назначает Вася).

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

Формат входных данных
В первой строке задается число наборов тестовых данных \(T\). В этой задаче \(T\) всегда равно 1.

В первой строке описания каждого набора записано число \(N\) (\(1 \le N \le 10\)) — количество продавцов.

В следующей строке записано \(N\) чисел \(S_i\) (\(1 \le S_i \le 100\)).

В следующей строке записано число \(M\) (\(1 \le M \le 10\)).

В следующей строке записано \(M\) чисел \(B_i\) (\(1 \le B_i \le 100\)).

Описания наборов отделяются друг от друга пустой строкой.

Формат выходных данных
Для каждого набора входных данных выведите одно число — максимальную суммарную стоимость проданных товаров.

В этой задаче на проверку необходимо сдать исходный код программы.

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

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

Монотонная подпоследовательность#90465

Монотонная подпоследовательностьстандартный вводстандартный вывод1 секунда256 мегабайт

Рассмотрим последовательность \(a_1, a_2, \ldots, a_n\). Его подпоследовательность \(a_{i_1}, a_{i_2}, \ldots, a_{i_k}\), где \(1 \le i_1 < i_2 < \ldots < i_k \le n\) назвается монотонной, если либо \[a_{i_1} \le a_{i_2} \le \ldots \le a_{i_k},\] либо \[a_{i_1} \ge a_{i_2} \ge \ldots \ge a_{i_k}.\]

Для заданных \(n\) и \(k\), найдите последовательность, состоящую из чисел от 1 до \(n\) таких, что каждое из чисел встречается в ней ровно один раз, а длина самой длинной монотонной подпоследовательности (возрастающей или убывающей) составляет ровно \(k\).

Формат входных данных
Первая строка входных данных содержит целые числа \(n\) и \(k\) (\(1 \le k \le n \le 10^6\)), длина последовательности и требуемая длина самой длинной монотонной подпоследовательности.

Формат выходных данных
Если требуемой последовательности не существует, выведите \(-1\) в первой и единственной строке.

Если требуемая последовательность существует, выведите ее в первой и единственной строке. Если подходящих последовательностей несколько, можно вывести любую из них.

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

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

Why Did the Cow Cross the Road#90432

Коровы Фермера Джона учатся переходить через дорогу эффективно. И ищут цыплят в качестве учителей.

Цыплята очень занятые существа и имеют ограниченное время для помощи коровам. Всего имеется \(C\) цыплят на ферме (\(1 \leq C \leq 20,000\)), последовательно пронумерованных \(1 \ldots C\), и каждый цыплёнок \(i\) может помогать коровам ровно время \(T_i\). Коровы никуда не торопятся. Всего имеется \(N\) коров на ферме (\(1 \leq N \leq 20,000\)), последовательно пронумерованных \(1 \ldots N\), и корова \(j\) способно переходить дорогу между временами \(A_j\) и \(B_j\). В идеале корова \(j\) хочет найти цыплёнка \(i\), который поможет её перейти через дорогу. Для того, чтобы их расписания были совместимы, необходимо чтобы выполнялось неравенство \(A_j \leq T_i \leq B_j\).

Если для каждой коровы может быть взят в пару не более чем один цыплёнок и каждый цыплёнок может быть взят в пару не более чем с одной коровой, помогите найти максимальное количество пар корова-цыплёнок, которого можно достичь.

ФОРМАТ ВВОДА (файл helpcross.in):

Первая строка ввода содержит \(C\) и \(N\). Следующие \(C\) строк содержат \(T_1 \ldots T_C\), а последующие \(N\) строк содержат \(A_j\) и \(B_j\) (\(A_j \leq B_j\)) для \(j = 1 \ldots N\). \(A\), \(B\), \(T\)' – все неотрицательные числа (не обязательно различные) не более 1,000,000,000.

ФОРМАТ ВВОДА (файл helpcross.out):

Вычислите максимально-возможное количество пар корова-цыплёнок.

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

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

Why Did the Cow Cross the Road III#90425

Фермер Джон на старости лет стал параноиком. Он построил огромную изгородь вокруг фермы для защиты своих коров. Коровам такая идея не понравилась.

Соседние коровы ещё имеют возможность войти, но только через одни ворота и с большой очередью, потому что каждой нужно ответить на длинный список вопросов, прежде чем войти.

Для каждой из \(N\) коров, посещающих ферму, вам сообщается время, когда она прибывает к воротам и количество времени, которое её требуется для ответов на вопросы. В каждый момент времени только одна корова опрашивается, поэтому, если много коров прибывает примерно в одно и то же время, они должны ждать своей очереди отвечать на вопросы. Например, если корова прибыла во время 5 и отвечает на вопросы 7 единиц времени, то другая корова, прибывшая во время 8 должна подождать до времени 12, что начать отвечать на вопросы.

Определите минимально возможное время, за которое все коровы войдут на ферму.

ФОРМАТ ВВОДА (файл cowqueue.in):

Первая строка ввода содержит \(N\), положительное целое число, не более 100. Каждая из последующих \(N\) строк описывает одну корову, задавая время прибытия и время, которое требуется ей для ответов на вопросы. Каждое из этих чисел - положительное целое число не более 1,000,000.

ФОРМАТ ВЫВОДА (файл cowqueue.out):

Определите минимально возможное время, в которое все коровы завершат обработку.

Жадный алгоритм Задачи на моделирование Использование сортировки

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

Circular Barn#90420

Будучи фанатом современной архитектуры, Фермер Джон построил новый амбар в форме круга. Внутри амбар составляет кольцо из \(n\) комнат, пронумерованных по часовой стрелке \(1 \ldots n\) по периметру (\(3 \leq n \leq 1,000\)). Каждая комната имеет двери в две соседние комнаты, а также дверь из амбара во внешний мир.

У ФД есть ровно \(n\) коров, и он хочет поместить по одной корове в каждую комнату. Однако своенравные коровы выстроились не как нужно, и возможно несколько коров собрались у одной внешней двери. А именно, \(c_i\) коров стоит перед дверью с номером \(i\). Разумеется, \(\сумма c_i = n\).

Чтобы коровы добрались до своих мест ФД собирается применить следующий подход: каждая корова входит в дверь, перед которой она стоит и идёт по часовой стрелке в свою комнату. В предположении, что проход коровы через \(d\) дверей отнимает у неё \(d^2\) энергии, определите минимальное количество энергии, которое требуется, чтобы распределить коров по одной в комнату.

ФОРМАТ ВВОДА (файл cbarn.in):

Первая строка ввода содержит \(n\). Оставшиеся \(n\) строк содержат \(c_1 \ldots c_n\).

ФОРМАТ ВЫВОДА (файл cbarn.out):

Выведите минимальное количество энергии, потреблённое всеми коровами.

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

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

Circular Barn#90414

Будучи фанатом современной архитектуры, Фермер Джон построил новый амбар в форме круга. Внутри амбар составляет кольцо из \(n\) комнат, пронумерованных по часовой стрелке \(1 \ldots n\) по периметру (\(3 \leq n \leq 100,000\)). Каждая комната имеет двери в две соседние комнаты, а также дверь из амбара во внешний мир.

ФОРМАТ ВВОДА (файл cbarn.in):

Первая строка ввода содержит \(n\). Оставшиеся \(n\) строк содержат \(c_1 \ldots c_n\).

ФОРМАТ ВЫВОДА (файл cbarn.out):

Выведите минимальное количество энергии, потреблённое всеми коровами.

Жадный алгоритм Префиксные суммы(минимумы, ...)

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

Milk Pails#90413

Фермер Джон получил заказ доставить ровно \(M\) единиц молока (\(1 \leq M \leq 1,000\)). К несчастью, его молочная машина сломалась и у него есть три бидона молока целых размеров \(X\), \(Y\), and \(M\) (\(1 \leq X < Y < M\)). Все три бидона изначально пустые. Используя эти три бидона, он может выполнять любое количество операций двух следующих типов:

- Он может заполнить самый маленький бидон (размера \(X\)) полностью до самого верха \(X\) единицами молока, и перелить всё молоко в бидон размера \(M\), если не переполнится бидон с размером \(M\)

- Он может заполнить средний бидон (размера \(Y\)) полностью до верха \(Y\) единицами молока и перелить всё молоко в бидон размера \(M\), если не переполнится бидон с размером \(M\)

ФД понимает, что он не всегда может полностью заполнить бидон с размером \(M\), помогите ему определить максимальное количество молока, которое он может залить в бидон с размером \(M\)

ФОРМАТ ВВОДА (файл pails.in):

Первая и единственная строка ввода содержит \(X\), \(Y\) и \(M\), разделённые одиночными пробелами.

ФОРМАТ ВЫВОДА (файл pails.out):

Выведите максимальное количество молока, которое ФД может залить в бидон размером \(M\).

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

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

Cow Dance Show#90399

После нескольких месяцев репетиций, коровы готовы дать ежегодное танцевальное представление - балет "Cowpelia".

Остался непрояснённым только размер сцены. Сцена размера \(K\) может выдержать \(K\) коров, танцующих одновременно. \(N\) коров в стаде (\(1 \leq N \leq 10,000\)) пронумерованы последовательно \(1 \ldots N\) в порядке, в котором они должны появиться на сцене во время танца. Каждая корова \(i\) планирует танцевать определённое время \(d(i)\). Изначально коровы \(1 \ldots K\) появляются на сцене и начинают танцевать. Когда первая из этих коров завершит свой танец, она покидает сцену и корова \(K+1\) немедленно начинает танцевать и т.д. Поэтому всегда \(K\) коров танцуют, за исключением последнего отрезка шоу, когда коровы уходят, но не добавляются. Шоу завершается, когда последняя корова завершит свой танец в момент времени \(T\).

Понятно, что чем больше значение \(K\), тем меньше время \(T\). Поскольку шоу не может длится очень долго, вам на вводе даётся верхняя граница \(T_{max}\), указывающая максимально возможное значение величины \(T\). Ваша задача - определить минимально возможное подходящее значение \(K\).

ФОРМАТ ВВОДА (файл cowdance.in):

Первая строка ввода содержит \(N\) и \(T_{max}\), где \(T_{max}\) - целое число, не более 1 000 000.

Следующие \(N\) строк задают длительности танцев \(d(1) \ldots d(N)\) для коров \(1 \ldots N\). Каждое из \(d(i)\) - целое число в интервале \(1 \ldots 100,000\).

Гарантируется, что если \(K=N\), шоу закончится вовремя.

ФОРМАТ ВЫВОДА (файл cowdance.out):

Выведите наименьшее возможное значение \(K\) такое, что танцевальное шоу закончится не более чем через \(T_{max}\) единиц времени.

Бинарный поиск по ответу Жадный алгоритм Очередь

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

Angry Cows#90387

Беси создала новую игру. Игрок стреляет коровами на одномерную сцену, состоящую из множества стогов сена расположенных в различных точках на числовой прямой. Каждая корова приземляется с силой достаточной, чтобы разрушить ближайшие к точке приземления стоги. Цель - использовать множество коров так, чтобы разрушить все стоги сена.

Имеется \(N\) стогов сена расположенных в целочисленных позициях \(x_1, x_2, \ldots, x_N\) на числовой прямой. Если корова приземляется с энергией \(R\) в позиции \(x\), это вызывает взрыв "радиуса \(R\)", разрушающий все стоги сена в диапазоне \(x-R \ldots x+R\).

Всего имеется \(K\) коров для выстрелов, каждая с одной и той же энергией \(R\). Определите минимальную целую величину \(R\) такую, что возможно используя эти \(K\) коров разрушить все стоги сена на сцене.

ФОРМАТ ВВОДА (файл angry.in):

Первая строка ввода содержит \(N\) (\(1 \leq N \leq 50,000\)) и \(K\) (\(1 \leq K \leq 10\)). Каждая из оставшихся \(N\) строк содержит целые числа \(x_1 \ldots x_N\) (каждое в интервале \(0 \ldots 1,000,000,000\)).

ФОРМАТ ВЫВОДА (файл angry.out):

Выведите минимальную энергию \(R\), с которой должна приземлиться каждая корова, для того чтобы разрушить все стоги сена.

Бинарный поиск по ответу Жадный алгоритм Задачи на моделирование

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

High Card Wins#90354

Корова Беси - фанат карточных игр. Однако у неё нет достойных противников. Все они играют в полностью предсказуемой манере. Однако надо ещё придумать, как выиграть у них.

Беси и Эльза играют в простую карточную игру, в которой имеется колода из \(2N\) карт, последовательно пронумерованных \(1 \ldots 2N\). Они делят её поровну - \(N\) карт Беси и \(N\) карт Эльзе. Затем они играют \(N\) раундов, в каждом из которых Беси и Эльза выкладывают по одной карте, и тот, у кого карта больше, зарабатывает очко.

Беси может предсказать порядок, в котором будет выкладывать карты Эльза. Определите максимальное количество очков, которое может выиграть Беси.

ФОРМАТ ВВОДА (файл highcard.in):

Первая строка ввода содержит значение N (\(1 \leq N \leq 50,000\)).

Следующие N строк содержат карты, которыми будет играть в каждом из последующих раундов игры. Заметим, что из этой информации легко определить карты, которые на руках у Беси.

ФОРМАТ ВЫВОДА (файл highcard.out):

Выведите в одной строке максимальное количество очков, которое может заработать Беси.

Жадный алгоритм Использование сортировки

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

High Card Wins#90349

ФОРМАТ ВВОДА (файл highcard.in):

Первая строка ввода содержит значение N (\(1 \leq N \leq 50,000\)).

ФОРМАТ ВЫВОДА (файл highcard.out):

Выведите в одной строке максимальное количество очков, которое может заработать Беси.

Жадный алгоритм Задачи на моделирование Использование сортировки

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

High Card Low Card (Platinum)#90348

Беси и Эльза играютв простую карточную игру. Берётся колода из \(2N\) карт, последовательно пронумерованных \(1 \ldots 2N\), и делится на две части по \(N\) карт для Беси и \(N\) карт для Эльзы. Затем они играют \(N\) раундов, в каждом из которых Беси и Эльза выкладывают по одной карте. Изначально, одно очко за каждый раунд выигрывает игрок, у которого карта больше. Однако однажды за всю игру Беси может переключить правила игры так, что до конца игры выигрывать одно очко за раунд будет игрок, карта которого меньше. Беси может также выбрать не использовать эту опцию, оставляя на всю игру правило "выигрывает бОльшая карта" или она может включить это правило перед первыми раундом, и тогда вся игра ведётся по правилу "выигрывает меньшая карта".

Зная порядок, в котором будет выкладывать свои карты Эльза, помогите Беси определить максимальное количество очков, которое она сможет заработать.

ФОРМАТ ВВОДА (файл cardgame.in):

Первая строка ввода содержит значение N (\(2 \leq N \leq 50,000\)).

Следующие N строк содержат карты которым играет Эльзав том порядке как она их будет выкладывать в последовательных раундах игры. Заметим, что по этой информации легко определить, какие карты на руках у Беси.

ФОРМАТ ВЫВОДА (файл cardgame.out):

Выведите одну строку, содержащую максимальное количество очков, которое может заработать Беси.

Жадный алгоритм Использование сортировки

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

High Card Low Card (Gold)#90347

Беси и Эльза играют в простую карточную игру. Берётся колода из \(2N\) карт, последовательно пронумерованных \(1 \ldots 2N\), и делят их поровну - \(N\) карт Беси и \(N\) карт Эльзе. Затем они играют \(N\) раундов, в каждом из которых Беси и Эльза выкладывают по одной карте. В первых \(N/2\) раундах очко зарабатывает тот игрок, у которого карта больше. А в последних \(N/2\) раундах очко выигрывает тот игрок, у которого карта меньше.

По известному порядку выкладывания карт Эльзой определите максимальное количество очков, которое может заработать Беси.

ФОРМАТ ВВОДА (файл cardgame.in):

Первая строка ввода содержит значение N (\(2 \leq N \leq 50,000\); \(N\) чётное).

Следующие N строк содержат карты, которыми будет играть Эльза в каждом из последующих раундов игры. Заметим, что по этой информации, легко определить карты Беси.

ФОРМАТ ВЫВОДА (файл cardgame.out):

Выведите одну строку дающую максимальное количество очков, которое может заработать Беси.

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

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