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


Плюсануть
Поделиться
Класснуть
Запинить


Условие задачи Прогресс
ID 38122. Acowdemia III
Темы: Множества    Жадный алгоритм   

Фермер Джон открыл пастбище с целью помочь Беси и её друзьям.
Пастбище ФД можно рассматривать как большую 2D-решётку квадратных ячеек. Каждая ячейка помечена таким образом:

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

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

ФОРМАТ ВВОДА:
Первая строка содержит N и M (2 ≤ N,M ≤ 1000).
Каждая из следующих N строк содержит M символов, описывая пастбище.

ФОРМАТ ВЫВОДА:
Определите максимальное количество пар коров, которые могут стать друзьями.
 
№ Входные данные Выходные данные
1 4 5
.CGGC
.CGCG
CGCG.
.CC.C
 4

Если мы пометим корову в строке i и столбце j координатами (i,j), тогда в этом примере есть коровы в (1,2), (1,5), (2,2), (2,4), (3,1), (3,3), (4,2), (4,3), and (4,5). Один из способов, чтобы 4 коровы стали друзьями таков:

Коровы из (2,2) и (3,3) едят траву в (3,2).
Коровы из (2,2) и (2,4) едят траву в (2,3).
Коровы из (2,4) и (3,3) едят траву в (3,4).
Коровы из (2,4) и (1,5) едят траву в (2,5).
ID 38141. Год Коровы - 2
Темы: Жадный алгоритм   

Известно, знаки зодиака в Китайском календаре следуют 12-летнему циклу: Ox, Tiger, Rabbit, Dragon, Snake, Horse, Goat, Monkey, Rooster, Dog, Pig, Rat, и затем опять Ox. Менее известен тот факт, что в конце каждого года Ox открывается временной портал, позволяющий коровам переместиться в любой другой год Ox в прошлом или будущем.

Корова Беси хочет посетить N своих предшественников, которые жили много раньше (\(1<=N<=0x10000\)). 0x10000 - это число в 16-ричной системе счисления, что равно 65536 в десятичной.

К несчастью, путешествия во времени утомительны, и Беси предпочитает сделать не более K прыжков во времени (\(1<=K<=N\)). Помогите Беси определить минимальное количество лет, которое потребуется Беси, чтобы посетить всех предшественников и вернуться в текущий год, совершив не более K прыжков во времени по пути.

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



Входные данные
Первая строка ввода содержит N и K. Следующие N строк содержат N различных целых чисел в интервале \(1…10^9\), указывающих сколько лет назад жил каждый из предшественников Беси.

Выходные данные
Выведите минимальное количество лет, которое потребуется Беси, чтобы посетить всех своих предшественников и вернуться в настоящий год.
 
 
Примеры
№ Входные данные Выходные данные Примечание
1 5 3
101
85
100
46
95		 36

Один из способов для Беси посетить всех своих предшественников за 36 лет таков:

  1. Войти в портал в текущем году и вернуться на 48 лет в прошлое.
  2. Подождать 12 лет затем войтив портал в 36 лет в прошлом и пропутешествовать 108 лет в прошлое.
  3. Подождать 24 года, затем зайти в портал в 84 года в прошлом и пропутешествовать обратно в текущий год.

ID 34851. Чехарда
Темы: Цикл while    Жадный алгоритм   

Дорожка замощена плитками в один ряд, плитки пронумерованы числами от 1 до 1000. На плитках с номерами A, B и C (A < B < C) сидят три кузнечика, которые играют в чехарду по следующим правилам:
1. На одной плитке может находиться только один кузнечик.
2. За один ход один из двух крайних кузнечиков (то есть с плитки A или с плитки C) может перепрыгнуть через среднего кузнечика (плитка B) и встать на плитку, которая находится ровно посередине между двумя оставшимися кузнечиками (то есть между B и C или A и B соответственно). Если между двумя оставшимися кузнечиками находится чётное число плиток, то он может выбрать любую из двух центральных плиток.
Например, если кузнечики первоначально сидели на плитках номер 1, 5, 10, то первым ходом кузнечик с плитки номер 10 может перепрыгнуть на плитку номер 3 (она находится посередине между 1 и 5), или кузнечик с плитки номер 1 может перепрыгнуть на плитку номер 7 или 8 (эти две плитки находятся посередине между плитками 5 и 10).
Даны три числа: A, B, C. Определите, какое наибольшее число ходов может продолжаться игра.

Формат входных данных
Программа получает на вход три целых числа A, B и C (1 <= A < B < C <= 1000), записанных в отдельных строках.
Формат выходных данных
Выведите одно число — наибольшее количество ходов, которое может продолжаться игра.
 

Ввод Вывод Примечание
1
4
6		 2 В примере сначала кузнечик с плитки №6 прыгает на плитку №3. Затем кузнечик с плитки №4 прыгает на плитку №2.

ID 38337. Cookie Clicker
Темы: Жадный алгоритм   

В игре Cookie Clicker игрок зарабатывает печеньки (cookies), щёлкая мышкой по изображению большой печеньки. Тратя заработанные печеньки, игрок может покупать различные усовершенствования (ферму, фабрику и т. д.), которые также производят дополнительные печеньки.

Рассмотрим упрощённый вариант этой игры. Пусть игрок может сделать один щелчок мышкой в секунду, что приносит ему одну печеньку. Также в любой момент времени игрок может потратить C печенек на покупку фабрики (при этом у игрока должно быть не меньше C печенек, после покупки фабрики количество его печенек моментально уменьшается на C ). Каждая купленная фабрика увеличивает ежесекундное производство печенек на P штук (то есть если у игрока одна фабрика, то он получает 1  + P печенек в секунду, две фабрики — 1  +  2 P печенек, три фабрики — 1  +  3 P печенек и т. д.). Игрок может приобрести неограниченное число фабрик стоимостью C печенек каждая. Фабрика начинает производить дополнительные печеньки сразу же, например, если после какой-то секунды игры у игрока стало C печенек, то игрок может купить фабрику и уже на следующей секунде его производство печенек увеличится на P штук.

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

Входные данные
Программа получает на вход три целых положительных числа, записанных в отдельных строках: С (стоимость фабрики), P (производительность одной фабрики) и N (необходимое количество печенек).

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

Примеры
№ Входные данные Выходные данные Пояснение
1 50
3
100		 75 Через 50 секунд после начала игры у игрока будет 50 печенек, и он сможет купить фабрику. После этого он будет получать 4 печеньки в секунду, и на производство 100 печенек понадобится еще 25 секунд.
2 99
10
100		 100 Игрок сможет набрать 100 печенек за 100 секунд, при этом фабрику покупать нет смысла.

ID 38343. Округлите равенство
Темы: Жадный алгоритм    Вещественные числа   

Дано верное равенство вида a1+a2+…+aN=b1+b2+…bM, где a1,a2,…,aN, b1,b2,…,bM – некоторые действительные (не обязательно целые) числа. Требуется «округлить» это равенство, т.е. получить новое верное равенство c1+c2+…+cN=d1+d2+…+dM, где c1,c2,…,cN,d1,d2,…,dM — целые числа, и при этом c1 получено округлением числа a1 до целого вверх или вниз (так, например, число 1.7 разрешается округлить как до 1, так и до 2), c2 получено округлением a2, …, cN – округлением aN, d1 – округлением b1, …, dM – округлением bM. Если какое-то из чисел в исходном равенстве было целым, оно должно остаться без изменений.

Входные данные
Во входном файле задано сначала число N, затем N чисел a1, a2, …, aN, затем число M, затем числа b1, b2, …, bM. Каждое число задается на отдельной строке. M и N – натуральные числа, не превышающие 1000. Остальные числа — вещественные, каждое из них по модулю не превышает 1000 и содержит не более 6 цифр после десятичной точки. При этом a1+a2+…+aN=b1+b2+…bM.

Выходные данные
Если «округлить» равенство можно, то в выходной файл выведите сначала числа c1,c2,…,cN, а затем числа d1,d2,…,dM. Все числа должны быть целыми и выведены без десятичной точки. Числа должны разделяться пробелами или переводами строки. Если решений несколько, выведите любое из них.

Если округлить исходное равенство до верного целочисленного равенства невозможно, выведите одно число 0.

Примеры
№ Входные данные Выходные данные Пояснение
1 3
0.15
-3.000
2.7
1
-0.15		 1
-3
2
0		 Обратите внимание, что число –3 может округляться только в –3, в то время как 0.15 можно округлить как до 0, так и до 1, 2.7 – до 2 или до 3, –0.15 – до –1 или до 0. Приведенное решение не является единственным: так же верным является, например, такое округление: 1+(–3)+2=0
 
2 2
1.7
2.5
3
1
2.000
1.20		 2
2
1
2
1		 Приведенное решение 1+3=1+2+1 не является единственным. Верными ответами также являются 2+2=1+2+1 и 2+3=1+2+2.
 
3 1
0.5
1
0.5		 0
0		 Здесь верными являются как ответ 1=1, так и 0=0.

ID 38473. Взвешивание камней
Темы: Алгоритмы сортировки    Дерево отрезков, RSQ, RMQ    Жадный алгоритм   

Джек нашел N камней и упорядочил их в порядке возрастания их массы. Массы всех камней различны. Самый легкий камень получил номер 1, следующий ≤ 2 и так далее, самый тяжелый получил номер N.

У Джека есть чашечные весы и он решил положить все камни на них в каком-то порядке. Известен порядок, в котором он будет класть камни, и какой камень на какую чашу попадет.

Ваша задача — определить состояние весов после добавления каждого камня. Точные массы камней не известны — даются только их номера.

Входные данные
Первая строка содержит целое число N (1  N ≤ 100000).

Каждая из следующих N строк содержит по два целых числа: R (1 ≤ R ≤ N) и S (1 ≤ S ≤ 2). R - номер камня, который будет положен на чашу S. Все R будут различны.

Выходные данные
Выведите N строк -  по одной для каждого камня. Если после добавления соответствующего камня чаша 1 тяжелее, выведите “<”. Если сторона 2 тяжелее, выведите “>”. Если невозможно определить, в каком состоянии будут весы, выведите “?”.

Примеры
№ Входные данные Выходные данные
1 5
1 2
3 1
2 1
4 2
5 1		 
<
>
>
?
>

ID 38546. Распродажа
Темы: Условный оператор    Жадный алгоритм   

Магазины в рекламных целях часто устраивают распродажи. Так, например,одна из крупных сетей магазинов канцелярских товаров объявила два рекламных предложения: "купи N одинаковых товаров и получи еще один товар бесплатно"и "купи K товаров по цене K−1 товара".

Для проведения олимпиады организаторам требуется распечатать условия для участников, на что уходит очень много бумаги. Каждая пачка стоит B рублей. Какое максимальное количество пачек бумаги можно приобрести на A рублей, правильно используя рекламные предложения?

Входные данные
Во входном файле записаны целые числа N, K, A и B (1 ≤ N ≤ 100, 2 ≤ K ≤ 100, 1 ≤ A ≤ 109, 1 ≤ B ≤ 109), разделенные пробелами.

Выходные данные
Выведите одно целое число - максимальное количество пачек бумаги, которое смогут купить организаторы олимпиады.

Примечание
В первом примере, дважды используя второе рекламное предложение, можно купить 8 пачек бумаги, заплатив за 6.

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

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

Примеры
№ Входные данные Выходные данные
1 4 4 13 2 8
2 3 4 8 3 2
3 3 4 7 1 9

ID 38571. Автобусы
Темы: Сортировка подсчетом    Жадный алгоритм    Сканирующая прямая   

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

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

Автобусная сеть страны охватывает N городов, занумерованных целыми числами от 1 до N.

Идеальное расписание содержит M ежедневных рейсов, i-й рейс начинается в городе Fi в момент времени Xi и заканчивается в некотором другом городе Gi в момент времени Yi. Продолжительность каждого рейса ненулевая и строго меньше 24 часов. Рейс i выполняется одним из автобусов, находящихся в момент времени Xi в городе Fi.

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

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

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

Входные данные
В первой строке задаются целые числа N и М (1 ≤ N, M ≤ 100 000) — количество городов и рейсов автобусов соответственно.

В каждой из следующих M строк содержится описание рейса автобуса: номер города отправления Fi, время отправления Xi, номер города назначения Gi (Fi ≠ Gi), время прибытия Yi, отделенные друг от друга одним пробелом. Время прибытия и отправления задается в формате HH:MM, где HH — часы от 00 до 23, MM — минуты от 00 до 59.

Выходные данные
Выведите одно число — минимально необходимое количество автобусов. Если расписание невозможно обслуживать в течение неограниченного периода времени конечным числом автобусов, выведите число -1.

Примеры
№ Входные данные Выходные данные
1 4 6
1 10:00 2 12:00
1 10:00 3 09:00
3 12:00 4 23:00
2 11:00 4 13:00
4 12:00 1 11:00
4 12:00 1 10:30		 8

ID 38572. То березка, то рябина…
Темы: Бинарный поиск в массиве    Бинарный поиск по ответу    Жадный алгоритм   

В целях улучшения ландшафтной архитектуры и экологической обстановки управление городского хозяйства разработало проект программы озеленения центрального проспекта. Согласно проекту, с одной стороны проспекта планируется высадить в ряд деревья K различных видов, для чего были закуплены саженцы деревьев, причем i-го вида было закуплено ai саженцев.

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

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

Входные данные
В первой строке вводятся два целых числа: K — количество различных видов деревьев (1 ≤ K ≤ 100 000), и P — требуемое количество подряд идущих деревьев разных видов (2 ≤ P ≤ K). Последующие K строк  входных данных содержат целые числа ai, задающие количество закупленных саженцев деревьев i-го вида  (1 ≤ ai ≤ 109), по одному числу в каждой строке.

Выходные данные
Выведите единственное число — максимальное количество деревьев, посадка которых в ряд в некотором порядке достигает эстетического совершенства.

 

Примеры
№ Входные данные Выходные данные
1 3 3
1
200 
1		 4

ID 38920. Эльфы и олени
Темы: Эвристические методы    Бинарный поиск по ответу    Быстрая сортировка    Жадный алгоритм   

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

Но волшебные олени – строптивые животные, поэтому не любые два эльфа могут ехать на любом олене. А именно, каждый олень характеризуется некоторой строптивостью ai, а каждый эльф – темпераментом bi. Два эльфа j и k могут ехать на i-м олене в том и только в том случае, если либо bj < ai < bk, либо bk < ai < bj.

Чтобы его появление было максимально зрелищным, Санта-Клаус хочет, чтобы в его упряжке было как можно больше оленей. Про каждого оленя Санта знает его строптивость, а про каждого эльфа – его темперамент.

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

Входные данные
В первой строке вводятся два целых числа m и n – количество оленей и эльфов, соответственно ( 1 ≤ m, n ≤ 100 000).

Вторая строка содержит m целых чисел ai – строптивость оленей ( 0 ≤ ai ≤ 109). В третьей строке записаны n целых чисел bi – темперамент эльфов ( 0 ≤ bi ≤ 109).

Выходные данные
В первой строке  выведите одно число k – максимальное количество оленей, которое Санта-Клаус может включить в свою упряжку. В следующих k строках выведите по три целых числа: di, ei, 1, ei, 2 – для каждого оленя в упряжке выведите его номер и номера эльфов, которые на нем поедут. Если решений несколько, выведите любое.

И эльфы, и олени пронумерованы, начиная с единицы, в том порядке, в котором они заданы во входных данных.

Примеры
№ Входные данные Выходные данные
1 4 6
2 3 4 5
1 3 2 2 5 2		 2
1 1 2
3 4 5

ID 27220. Paired Up
Темы: "Два указателя"    Жадный алгоритм   

Фермер Джон обнаружил, что корову легче доить, если рядом есть другая корова для моральной поддержки. Поэтому он хочет разбить M своих коров (M <= 109, M - чётное) на M/2 пар. Каждую из этих пар он помещает в отдельное стойло, и все пары коров доятся одновременно.
Каждая из коров даёт различное количество молока. Если коровы в паре дают по A и B литров молока, то для дойки этой пары требуется A+B единиц времени.
Помогите ФД определить минимально возможное количество времени на весь процесс дойки, в предположении, что коровы разбиты на пары наилучшим образом.
 
 
Входные данные
Первая строка ввода содержит N (1 <= N <= 100000). Каждая из следующих N строк содержит два целых числа x и y, указывающих, что у ФД есть x коров с производством молока по y (1 <= y <= 109) литров. Сумма всех x-ов есть M- общее количество коров.

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

 
Примеры
№ Входные данные Выходные данные
1
3
1 8
2 5
1 2
 10

ID 39672. Том Сойер и слово на заборе
Темы: Хеш    Жадный алгоритм    Префиксные суммы(минимумы, ...)   

Во время покраски забора Том Сойер написал на нем слово s. Однако затем он решил, что слова-палиндромы смотрятся красивее.
Теперь он хочет дописать к имеющемуся слову s справа другое слово g так, чтобы получившееся слово sg было палиндромом. Однако в целях экономии краски длина g должна быть как можно меньше.
Помогите Тому Сойеру определить слово g.

Входные данные:
В первой строке дано слово s (1 <= |s| <= 200000), состоящее из строчных латинских букв.

Выходные данные:
Выведите минимально возможное по длине слово g, которое нужно дописать, чтобы слово sg на заборе стало палиндромом. Если дописывать ничего не надо, то выведите '-'.

Примеры:
 

Входные данные Выходные данные
abc ba
a -

ID 40022. Межрегиональная олимпиада
Темы: Бинарный поиск в массиве    Динамическое программирование    Жадный алгоритм   

На межрегиональной олимпиаде по программированию роботов соревнования проводятся в один тур и в необычном формате. Задачи участникам раздаются последовательно, а не все в самом начале тура, и каждая i-я задача (1 ≤ i ≤ n) становится доступной участникам в свой момент времени si. При поступлении очередной задачи каждый участник должен сразу определить, будет он ее решать или нет. В случае, если он выбирает для решения эту задачу, то у него есть ti минут на то, чтобы сдать ее решение на проверку, причем в течение этого времени он не может переключиться на решение другой задачи. Если же участник отказывается от решения этой задачи, то в будущем он не может к ней вернуться. В тот момент, когда закончилось время, отведенное на задачу, которую решает участник, он может начать решать другую задачу, ставшую доступной в этот же момент, если такая задача есть, или ждать появления другой задачи. При этом за правильное решение i-й задачи участник получает ci баллов.

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

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

Входные данные
Первая строка содержит одно целое число n (1 ≤ n ≤ 105) количество задач на олимпиаде.

Последующие n строк содержат описания задач, по три числа на каждой строке: si момент появления i-й задачи в минутах, ti время, отведенное на ее решение в минутах, и ci сколько баллов получит участник за решение этой задачи (1 ≤ si, ti, ci ≤ 109).

Выходные данные
Первая строка  должна содержать одно число – максимальное количество баллов, которое сможет получить Артур на олимпиаде.

Вторая строка должна содержать одно целое число m - количество задач, которые надо решить при оптимальном выборе.

Третья строка должна содержать m разделенных пробелом целых чисел - номера этих задач в порядке их решения. Задачи пронумерованы, начиная с единицы, в порядке их описания во входном файле.

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

Примеры
№ Входные данные Выходные данные
1 2
1 1 1
2 2 2		 3
2
1 2
2 3
1 2 1
3 2 1
2 4 3		 3
1
3

ID 43034. Сортировщик Томми
Темы: "Два указателя"    Жадный алгоритм    Конструктив   

У Томми есть детская игрушка «cортировщик», с расположенными подряд n колышками. На каждом колышке сейчас не более одного диска (то есть на каком-то колышке диск есть, а на каком-то его нет). Томми хочет переложить имеющиеся диски на колышках таким образом, чтобы они образовывали неубывающую последовательность при просмотре слева направо. То есть на каждом следующем колышке количество дисков должно быть не меньше, чем на предыдущем.  Какое минимальное количество дисков Томми необходимо переложить?

Обратите внимание, что какие- то колышки по окончанию сортировки могут быть пустыми. Какие-то колышки могут содержать более 1 диска.



Входные данные
Программа получает на вход в первой строке целое число n (1 <= n <= 105), количество колышек на «cортировщике». Следующая строка содержит n целых чисел a1, a2, ... an – наличие диска на соответствующем колышке (0 <= ai <= 1). число 0 означает, что на i-м колышке нет диска, 1 – диск есть.

Выходные данные
Выведите ответ на задачу.
 
Примеры
№ Входные данные Выходные данные
1 
8
0 0 1 1 1 1 1 1
 
0
2 
11
1 1 0 0 1 0 0 1 1 1 0
 
3

ID 43714. Радостная фигура
Темы: Использование сортировки    Жадный алгоритм   

Маленький Миша любит играть счетными палочками. Счетные палочки он берет у своей сестры первоклассницы. Так как он редко возвращает их назад, маме приходится часто покупать новые палочки. Поэтому не все палочки у Миши одинаковые, но все палочки имеют целочисленную длину.
Сегодня Миша строит из палочек следующую фигуру. Он начал из угла комнаты. Мы с вами обозначим, условно, этот угол координатой (0, 0). Дальше Миша выкладывает палочку параллельно одной из двух стен, исходящей из данного угла. Будем считать, что стены ровные и образуют друг с другом в точке (0, 0) угол 90 градусов. При этом, Миша никогда не выкладывает две подряд палочки одновременно параллельно одной и той же стене (другими словами, он всегда чередует направление палочек).
Миша, хоть и маленький и не знает геометрии, но все же всегда радуется, если конец его фигуры находится как можно дальше от стартового угла. Помогите Мише выложить фигуру, которая его обрадует. Любые две палочки, которые выкладывает Миша всегда имеют минимум одну точку касания или пересечения.

Входные данные
Программа получает на вход несколько строк. Первая строка содержит целое число n (1<= n <= 100000) — количество палочек, которые есть у Миши. Вторая строка содержит n целых чисел a1,...,an (1 <= ai <= 10000) - длины Мишиных палочек.

Выходные данные
Выведите одно целое число — квадрат максимального расстояния от угла с координатой (0,0) до конечной точки фигуры, которую построил Миша.
 
 

Примеры
№ Входные данные Выходные данные
1 3
1 2 3		 26
2 4
1 1 2 2		 20

ID 43718. Мишины кубики
Темы: Использование сортировки    Жадный алгоритм    Задача на реализацию    Простые задачи на перебор    "Два указателя"   

У маленького Миши есть кубики, на каждом из которых написана одна английская строчная буква. Вчера он выкладывал кубики в два ряда. В первом ряду у Миши n кубиков с буквами, во втором - m кубиков с буквами. Так получилось, что в двух этих рядах нет совпадающих букв. Другими словами, ни одна буква не содержится одновременно в обоих рядах.
Сегодня маленький Миша решил продолжить играть с кубиками. Но теперь он берет один любой кубик из какого-либо ряда и составляет из них третий ряд, добавляя кубик всегда в конец. Маленький Миша никогда не берет более k кубиков подряд из одного и того же ряда. Миша закончил играть тогда, когда у него закончились кубики в каком-то одном ряду (в первом или во втором).
Наблюдавший за игрой папа заметил, что играя таким образом у Миши получилась лексикографически наименьшая строка. По известным двум строкам, которые образуются путем прочтения букв первого и второго ряда и числу k определите строку, которую получил маленький Миша.

Строка x лексикографически меньше строки y только и только тогда, когда выполняется одно из следующих условий:
- x является префиксом y, но x != y;
- в первой позиции, где x и y различаются, в строке x находится буква, которая стоит в алфавите раньше, чем соответствующая буква y.


Входные данные
Программа получает на вход несколько строк. В первой строке записаны три числа: n - количество кубиков в первом ряду, m - количество кубиков во втором ряду, k - целое число(1 <= n, m, k <= 100). Во второй строке записана строка a длиной n - строка, образованная прочтением букв, написанных на кубиках первого ряда. В третьей строке - строка b длиной m - строка, образованная прочтением букв, написанных на кубиках второго ряда.

Выходные данные
Выведите ответ на задачу.
 
 

Примеры
№ Входные данные Выходные данные
1 6 4 2
aaaaaa
bbbb		 aabaabaa

ID 47509. Максимус спасает Элстейд
Темы: Жадный алгоритм    Массивы    Алгоритмы сортировки   

Одарённый невероятной магией и всезнанием Максимус заметил группу из n монстров, приближающихся к городку Элдстейд. Своими волшебными способностями он мгновенно определил расстояние в километрах от города до каждого монстра. Он также заметил, что все монстры двигаются с постоянной скоростью. У Максимуса есть оружие, способное уничтожить одного монстра после полной зарядки. Зарядка занимает ровно одну минуту. Чтобы победить монстра, оружие должно быть полностью заряжено к моменту приближения монстра к городу. Другими словами, невозможно убить монстра достигшего города, даже если в этот момент оружие закончило полную зарядку.
Максимус задается вопросом, сможет ли он сам спасти город от всех монстров или ему нужна помощь.
Напишите программу, которая поможет Максимусу мгновенно определить максимальное количество монстров, которое он сможет уничтожить до того момента, как хотя бы один монстр достигнет города.

Входные данные
Первая строка содержит число n - количество монстров. Во второй строке записано n чисел dist[i] - начальное расстояние в километрах от города для i-го монстра. Третья строка содержит n чисел speed[i] - скорость i-го монстра в километрах в минуту.

Ограничения

  • n == длина массива dist == длина массива speed
  • 1 <= n <= 105
  • 1 <= dist[i], speed[i] <= 105


Выходные данные
Выведите ответ на задачу.
 
 
Примеры
№ Входные данные Выходные данные Примечание
1 
3
1 3 4 
1 1 1
 
3
 Вначале расстояния между монстрами равны [1,3,4]. Максимус уничтожает первого монстра.
Через минуту расстояния между монстрами становятся [X,2,3]. Максимус уничтожает второго монстра.
Через минуту расстояния между монстрами будут [X,X,2]. Максимус уничтожает третьего монстра.
Все три монстра могут быть уничтожены.
 
2 
4
1 1 2 3
1 1 1 1
 
1
 Вначале расстояния между монстрами равны [1,1,2,3]. Максимус уничтожает первого монстра.
Через минуту расстояния между монстрами становятся равными [X,0,1,2], и второй монстр достиг города.
Максимус может уничтожить только 1 монстра.

 
ID 48049. Вечер кёрлинга
Темы: Жадный алгоритм    Использование сортировки   

Сегодня вечером по телевизору на разных каналах будут показывать n матчей по кёрлингу, причём i-й матч начинается в момент времени li и заканчивается в момент времени ri. 

Василиса хочет посмотреть как можно больше матчей от начала до конца. При этом если какой-то матч заканчивается в момент времени ri, то она может после него посмотреть любой матч j, который начинается не раньше момента времени ri, то есть lj >  ri (Василиса может моментально переключить каналы в момент окончания матча и начать смотреть новый матч). Также она хочет сделать перерыв длины хотя бы t между какими-то двумя играми, чтобы поужинать, то есть должны найтись два последовательных матча i и j, которые просмотрит Василиса, удовлетворяющие условию lj - ri => t. Перерыв не может быть до или после всех просмотренных игр.

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

Формат входных данных
Первая строка входных данных содержит число n  (2 ≤ n ≤ 100 000) -  количество показываемых матчей.
Вторая строка входных данных содержит число t (1 ≤ n ≤ 109) -  минимальная длина перерыва, который должна сделать Василиса.
В следующих n строках содержится по два числа li  и ri  ( 1 ≤ li < ri ≤ 109) -  начало и конец i-го матча.

Формат выходных данных
Программа должна вывести число m - максимально возможное количество матчей, которые просмотрит Василиса. Во второй строке выведите m чисел через пробел - номера матчей, которые должна посмотреть Василиса, в порядке просмотра.
Если Василиса не может составить расписание хотя бы из двух матчей так, чтобы между какими-то двумя матчами был перерыв хотя бы t, то выведите число -1.

Замечание
В первом примере ответом будет последовательность матчей 6, 3, 5. Василиса сначала посмотрит матч 6, 
который заканчивается в момент времени 4, потом переключится на матч 3, который продолжается с 4 до 6. 
Затем она сделает перерыв с 6 по 10, после чего просмотрит матч номер 5 с 10 до 12. Получилось расписание из 3 матчей с перерывом, продолжительность которого равна 4. Заметим, что в данном примере правильным ответом также будет последовательность матчей 6, 4, 5, в этом случае продолжительность перерыва между матчами 4 и 5 будет равна 3.

Во втором примере всего два матча, первый заканчивается в 5, а второй начинается в 9, то есть составить расписание, в котором был бы перерыв продолжительностью не менее t=5, нельзя.
 
ID 48921. Пазл
Темы: Паросочетания    Жадный алгоритм    Динамическое программирование    Динамическое программирование   

Участникам, использующим язык Python3, рекомендуется отправлять решения на проверку с использованием интерпретатора PyPy3.

Школьники Алиса и Ибрагим — лучшие друзья. У Ибрагима скоро день рождения, и по этому поводу Алиса решила подарить ему новый пазл. Пазл можно представить в виде матрицы из \(2\) строк и \(n\) столбцов, каждый элемент которой \(0\) или \(1\). За один ход можно поменять местами два элемента, стоящие в соседних клетках.

Более формально, будем считать, что строки матриц пронумерованы сверху вниз от \(1\) до \(2\), а столбцы — слева направо от \(1\) до \(n\). Обозначим клетку на пересечении строки \(x\) и столбца \(y\) за \((x, y)\). Будем считать две клетки \((x_1, y_1)\) и \((x_2, y_2)\) соседними, если \(|x_1 - x_2| + |y_1 - y_2| = 1\).

Алисе не нравится, какой рисунок образуют клетки пазла в данный момент. Она придумала свой рисунок, с которым и планирует подарить Ибрагиму новый пазл, но для этого нужно привести пазл в соответствующее состояние.

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

Формат входных данных
В первой строке вводится одно целое число \(n\) (\(1 \leq n \leq 200\,000\)) — количество столбцов в пазле.

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

Следующие две строки описывают желаемый рисунок Алисы в том же формате.

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

 

В первом примере из условия подойдет следующая последовательность обменов:

\((2, 1), (1, 1)\)

\((1, 2), (1, 3)\)

\((2, 2), (2, 3)\)

\((1, 4), (1, 5)\)

\((2, 5), (2, 4)\)

Можно показать, что меньшим числом обменов обойтись нельзя, поэтому ответ равен \(5\).

Во втором примере из условия никакая последовательность ходов не приводит пазл к нужному виду.
ID 29546. Fenced In
Темы: Алгоритмы сортировки    Жадный алгоритм   

Коровы Фермера Джона боятся больших пространств. Поэтому разгородил своё поле на некоторое количество маленьких регионов, построив вертикальные (север-юг) и горизонтальные (восток-запад) изгороди.
Поле представляет собой прямоугольник с угловыми вершинами в точках (0,0) and (A,B). ФД построил n вертикальных изгородей (0≤n≤25,000) в различных позициях a1…an (0<ai<A); каждая изгородь проходит от точки (ai,0) до точки (ai,B). Он также построил m горизонтальных изгородей (0≤m≤25,000) в в различных позициях b1…bm (0<bi<B); каждая изгородь, проходит из (0,bi) в (A,bi). Каждая вертикальная изгородь пересекается с каждой горизонтальной изгородью, разделив поле на (n+1)(m+1) регионов.
 
К несчастью, ФД забыл построить ворота в своих изгородях, сделав невозможным коровам покидать свой регион. Он хочет исправить ситуацию, удалив куски изгороди, чтобы позволить коровам перемещаться между соседними регионами. Он хочет выбрать некоторые пары соседних регионов и удалить всю длину изгороди между ними. А ещё он хочет обеспечить, чтобы коровы могли попасть в любую часть поля.
 
Например, ФД мог построить изгороди так:
 
+---+--+
|      |   |
+---+--+
|     |    |  
|     |    |
+---+--+
и открыть их так:
 
+---+--+
|          |  
+---+  +  
|          |  
|          |
+---+--+
Помогите ФД определить минимальную суммарную длину изгородей, которые он должен удалить, чтобы достичь своей цели.
 
ФОРМАТ ВВОДА:
Первая строка ввода содержит числа A, B, n, and m (1≤A,B≤1,000,000,000). Следующие n строк содержат a1…an. Следующие m строк содержат b1…bm.

ФОРМАТ ВЫВОДА:
Выведите минимальную длину изгороди, которую ФД должен удалить. Заметим что это число может не поместиться в 32-битное целое и Вам нужно использовать 64-битное целое (например, "long long" в C/C++ )
 
Ввод Вывод
15 15 5 2
2
5
10
6
4
11
3
 44

ID 49744. Чтение книг
Темы: Бинарный поиск по ответу    Жадный алгоритм    Использование сортировки   

У Максима есть n книг различных жанров. В i-й книге ai страниц. Сегодня он хочет прочитать  не менее xj страниц, при этом, чтобы не запутаться в историях, он хочет прочитать как можно меньше книг. 
Помогите Максиму  определить минимальное количество книг, которые он должен прочитать, чтобы общее число прочитанных страниц было не менее xj. Если это невозможно, выведите -1. Максим не может читать одну и ту же книгу дважды. 

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

Первая строка содержит натуральное число n (1 ≤ 𝑛 ≤ 105) - количество книг, которые есть у Максима. Вторая строка  содержит n целых чисел a1, a2, ..., an (1≤ ai ≤104) - количество страниц в i-й книге. Третья строка содержит натуральное число xj (1 ≤ xj ≤ 2⋅109) - количество страниц, которое хочет прочитать Максим.


Формат выходных данных
Выведите ответ на задачу.
ID 50404. Стабильные параллели
Темы: Жадный алгоритм   

Паша и Тёма приехали преподавать в зимний ноутбучный университет. Теперь им необходимо разобраться с учениками.

Есть \(n\) учеников, пронумерованных от \(1\) до \(n\). Уровень знаний \(i\)-го ученика равен \(a_i\). Всех учеников нужно распределить на стабильные параллели. Параллель называется стабильной, если после сортировки всех учеников параллели в порядке возрастания их уровня знаний у любых двух подряд идущих учеников разница уровня знаний не превосходит \(x\).

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

Формат входных данных
В первой строке вводятся три целых числа \(n\), \(k\), \(x\) (\(1 \le n \le 200\,000, 0 \le k \le 10^{18}, 1 \le x \le 10^{18}\)) — количество учеников, сколько учеников можно пригласить дополнительно и максимальная допустимая разница уровня знаний.

Во второй строке вводится \(n\) целых чисел \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^{18}\)) — уровни знаний учеников.

Формат выходных данных
В единственной строке выведите одно число — искомое минимальное число стабильных параллелей, на которое можно разбить учеников.


Примечание

В первом примере из условия можно пригласить учеников с уровнями знаний, равными \(2\) и \(11\). Тогда учеников можно разделить на следующие стабильные параллели:

  1. \([1, 1, 2, 5, 8, 11, 12, 13]\),

  2. \([20, 22]\).

Во втором примере из условия новых учеников приглашать нельзя, поэтому потребуется \(3\) параллели:

  1. \([1, 1, 5, 5, 20, 20]\)

  2. \([60, 70, 70, 70, 80, 90]\)

  3. \([420]\)

 
ID 50405. PriceFixed
Темы: Жадный алгоритм    "Два указателя"   

Девочка Лена — самая экономная девочка в Москве. Поэтому когда папа поручил ей закупку продуктов для поездки на дачу, она сразу отправилась в самый лучший магазин — <<PriceFixed>>. У этого магазина есть несколько особенностей:

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

  • Все товары в нем стоят одинаково — ровно 2 рубля.

  • Для каждого из \(i\) товаров предусмотрена скидка для опытных покупателей: если вы уже приобрели \(b_i\) товаров (любого типа, не обязательно типа \(i\)), то на все последующие покупки \(i\)-го товара будет действовать скидка \(50\%\) (то есть, \(i\)-й товар можно будет покупать за 1 рубль!).

Лене нужно купить \(n\) товаров: \(i\)-го товара нужно купить \(a_i\) штук. Помогите Лене понять, какую минимальную сумму денег ей нужно будет потратить, если она будет выбирать порядок покупки товаров оптимальным образом.

Формат входных данных
В первой строке вводится число \(n\) \((1 \leq n \leq 100\,000)\) — количество различных товаров в списке.

В следующих \(n\) строках вводятся описания товаров. Каждое описание состоит из двух чисел \(a_i\) и \(b_i\), (\(1 \leq a_i \leq 10^{14}\), \(1 \leq b_i \leq 10^{14}\)) — требуемое число товаров типа \(i\) и сколько товаров нужно купить, чтобы получить скидку на товар \(i\).

Сумма всех \(a_i\) в тесте не превосходит \(10^{14}\).

Формат выходных данных
Выведите искомую минимальную сумму, которая требуется Лене для совершения всех покупок.


Примечание

В первом примере из условия Лена может купить товары в таком порядке:

  1. единицу товара 3 за 2 рубля,

  2. единицу товара 1 за 2 рубля

  3. единицу товара 1 за 2 рубля,

  4. единицу товара 2 за 1 рубль (она может купить его со скидкой, так как уже куплено 3 товара),

  5. единицу товара 1 за 1 рубль (она может купить его со скидкой, так как уже куплено 4 товара).

Суммарно она потратит 8 рублей. Можно показать, что меньше потратить невозможно.

Во втором примере из условия Лена может купить товары в таком порядке:

  1. единицу товара 1 за 2 рубля,

  2. две единицы товара 2 по 2 рубля за каждую,

  3. единицу товара 5 за 2 рубля,

  4. единицу товара 3 за 1 рубль,

  5. две единицы товара 4 по 1 рублю за каждую,

  6. единицу товара 1 за 1 рубль.

Суммарно при таком порядке приобретения товаров Лена потратит 12 рублей.
ID 50541. Решение задач
Темы: Жадный алгоритм    Алгоритмы сортировки   

В этой задаче Вася готовится к олимпиаде. Учитель дал ему \(N\) (\(1 \le N \le 100\)) задач для тренировки. Для каждой из этих задач известно, каким умением \(a_i\) нужно обладать для её решения. Это означает, что если текущее умение Васи больше либо равно заданного умения для задачи, то он может ее решить. Кроме того, после решения \(i\)-й задачи Васино умение увеличивается на число \(b_i\).

Исходное умение Васи равно \(A\). Решать данные учителем задачи он может в произвольном порядке. Какое максимальное количество задач он сможет решить, если выберет самый лучший порядок их решения?

Формат входных данных
Сначала вводятся два целых числа \(N\), \(A\) (\(1 \le N \le 100\), \(0 \le A \le 100\)) — количество задач и исходное умение. Далее идут \(N\) пар целых чисел \(a_i\), \(b_i\) (\(1 \le a_i \le 100\), \(1 \le b_i \le 100\)) — соответственно сколько умения нужно для решения \(i\)-й задачи и сколько умения прибавится после её решения.

Формат выходных данных
Выведите одно число — максимальное количество задач, которое Вася может решить.

 

Примечание
В первом тесте Вася сможет решить все задачи, выбрав, например, порядок 2, 1, 3. Во втором тесте ему необходимо сначала разобраться с 1 и 3 задачами, после чего он осилит 2.