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

Paired Up#27220

Фермер Джон обнаружил, что корову легче доить, если рядом есть другая корова для моральной поддержки. Поэтому он хочет разбить M своих коров (M <= 10⁹, M - чётное) на M/2 пар. Каждую из этих пар он помещает в отдельное стойло, и все пары коров доятся одновременно.

Каждая из коров даёт различное количество молока. Если коровы в паре дают по A и B литров молока, то для дойки этой пары требуется A+B единиц времени.

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

Входные данные

Первая строка ввода содержит N (1 <= N <= 100000). Каждая из следующих N строк содержит два целых числа x и y, указывающих, что у ФД есть x коров с производством молока по y (1 <= y <= 10⁹) литров. Сумма всех x-ов есть M- общее количество коров.

Выходные данные

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

Примеры

№	Входные данные	Выходные данные
1	3 1 8 2 5 1 2	10

"Два указателя"Жадный алгоритм

✓ 98✗ 387800средняяВойти и решать

Тяжелая, вариант-2#24737

В школьную столовую пришли n учеников разных классов и выпили суммарно k стаканов компота. Кассирша тетя Таня хорошо знает всех учеников, поэтому про i-го пришедшего школьника она знает число a_i — максимальное количество стаканов компота, которое мог выпить этот школьник. Также она знает, i-й школьник выпьет явно не меньше a_i-x стаканов компота. Теперь ей стало интересно: а какое максимальное количество стаканов компота гарантированно выпил один из школьников? То есть она хочет найти такое максимальное число m, что при любом корректном распределении количества выпитых стаканов компота между школьниками, школьник, выпивший максимальное количество стаканов компота, выпил их не менее чем m штук. Помогите ей с этой задачей.

Формат входного файла

В первой строке находятся три натуральных числа n, k, x (1 ≤ n ≤ 100; 1 ≤ k ≤ 2 · 10⁴; 1 ≤ x ≤ 100) — количество школьников, пришедших в столовую, количество стаканов компота, выпитого ими, и максимальное количество стаканов, на которое каждый школьник мог выпить менее своего максимального количества, соответственно.
В следующей строке находятся n целых чисел a_i (x+1 ≤ a_i ≤ 200), разделенных пробелами, — максимальное количество стаканов компота, которое выпил i-й школьник.
Гарантируется, что входные данные корректны.

Формат выходного файла

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

Пример входных и выходных данных

Ввод	Вывод	Комментарий
3 4 1 2 2 3	2	Так как всего было выпито 4 стакана компота, а школьники выпили хотя бы 2-1=1, 2-1=1 и 3-1=2 стакана соответственно, первый школьник выпил ровно 1 стакан, второй — ровно 1 стакан, третий — ровно 2 стакана. Следовательно, ответ равен 2.
3 6 1 2 2 3	2	Каждый из школьников мог выпить по 2 стакана компота. Значит, ответ 3 гарантировать нельзя. Следовательно, ответ равен 2.
3 7 1 2 2 3	3	Так как всего выпито 7 стаканов компота, хотя бы один школьник выпил 3 стакана. Ответ 4, очевидно, недостижим. Следовательно, ответ равен 3.
3 12 2 3 4 6	5	Первый школьник выпил хотя бы 1 стакан и не более 3, второй — хотя бы 2 и не более 4, третий — хотя бы 4 и не более 6. Невозможно выпить 12 стаканов компота, если третий школьник выпьет ≤ 4 стакана, следовательно, ответ равен 5.

Жадный алгоритм Разбор случаев

✓ 21✗ 163900средняяВойти и решать

Тяжелая, вариант-1#24736

В школьную столовую пришли n учеников разных классов и выпили суммарно k стаканов компота. Кассирша тетя Таня хорошо знает всех учеников, поэтому про i-го пришедшего школьника она знает число a_i — минимальное количество стаканов компота, которое мог выпить этот школьник. Также она знает, i-й школьник выпьет явно не больше a_i+x стаканов компота. Теперь ей стало интересно: а какое максимальное количество стаканов компота гарантированно выпил один из школьников? То есть она хочет найти такое максимальное число m, что при любом корректном распределении количества выпитых стаканов компота между школьниками, школьник, выпивший максимальное количество стаканов компота, выпил их не менее чем m штук. Помогите ей с этой задачей.

Формат входного файла

В первой строке входного файла input.txt находятся три натуральных числа n, k, x (1 ≤ n ≤ 100; 1 ≤ k ≤ 2 · 10⁴; 1 ≤ x ≤ 100) — количество школьников, пришедших в столовую, количество стаканов компота, выпитого ими, и максимальное количество стаканов, которое каждый школьник мог выпить сверх своего минимального количества, соответственно.
В следующей строке находятся n целых чисел a_i (1 ≤ a_i ≤ 100), разделенных пробелами, — минимальное количество стаканов компота, которое выпил i-й школьник.
Гарантируется, что входные данные корректны.

Формат выходного файла

В единственной строке выходного файла output.txt требуется вывести максимальное количество стаканов компота m, которое гарантированно выпил один из школьников.

Пример входных и выходных данных

Ввод	Вывод	Комментарий
3 4 1 1 1 2	2	Так как всего было выпито 4 стакана компота, а школьники выпили хотя бы 1, 1 и 2 стакана соответственно, первый школьник выпил ровно 1 стакан, второй — ровно 1 стакан, третий — ровно 2 стакана. Следовательно, ответ равен 2.
3 6 1 1 1 2	2	Каждый из школьников мог выпить по 2 стакана компота. Значит, ответ 3 гарантировать нельзя. Следовательно, ответ равен 2.
3 7 1 1 1 2	3	Так как всего выпито 7 стаканов компота, хотя бы один школьник выпил 3 стакана. Ответ 4, очевидно, недостижим. Следовательно, ответ равен 3.
3 12 2 1 2 4	5	Первый школьник выпил хотя бы 1 стакан и не более 3, второй — хотя бы 2 и не более 4, третий — хотя бы 4 и не более 6. Невозможно выпить 12 стаканов компота, если третий школьник выпьет ≤ 4 стакана, следовательно, ответ равен 5.

Жадный алгоритм Задачи на моделирование

✓ 14✗ 132800средняяВойти и решать

Узник нейропривода#23040

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

И как вы думаете, что попросил Павлик у Дедушки Мороза на новый год? Конечно же нейропривод а так же только что вышедшую под него “Borderlands 5 online”.

Первого января, после получения своего подарка, Павлик начал играть. Паша был лютым геймером, поэтому прокачивался с космической скоростью. Это позволило ему в первый же день игры развести 5 новичков на деньги и шмот. Конечно Дедушке Морозу это не понравилось, и он решил проучить Павлика. Он заблокировал Павлику доступ вернуться в реальность и послал ему в игре злого босса по имени Даня Зевс, элитного игрока команды NA’VI по CS GO в прошлом. Чтобы выбраться в реальность Павлику необходимо победить босса.

У Дани Зевса n здоровья. У Павлика же есть Дробовик с a1 патронами и наносящий а2 урона, пистолет с b1 патронами и наносящий b2 урона и снайперская винтовка с с1 патронами и наносящая с2 урона.

Какое минимальное количество выстрелов необходимо сделать Павлику, чтобы убить босса, если это вообще возможно.

Входные данные

В первой строке записано число n – количество здоровья у Данечки Зевса.

Во второй строке записаны числа а1 и а2 – количество патрон и урон дробовика.

В третей строке записаны числа b1 и b2 – количество патрон и урон пистолета.
В четвертой строке записаны числа с1 и с2 – количество патрон и урон снайперской винтовки.

0<=n,a1,a2,b1,b2,c1,c2<=2*10^9

Выходные данные

Вам необходимо вывести минимальное количество выстрелов, которое необходимо сделать Павлику или -1, если Павлик не сможет убить босса

Пример

Ввод

7 1

3 5

10 2

Вывод

(с) Курбатов Егор 9и

Жадный алгоритм Разбор случаев

✓ 5✗ 291 000средняяВойти и решать