e-olymp 7240. Степан — бізнесмен

Задача

Ужляндія, як відомо, країна з розвиненими торговими відносинами.

Степан вирішив спробувати зайнятися торгівлею і підзаробити собі на відпустку продажем комп’ютерної техніки. Для цього йому необхідно закуповувати техніку у інших продавців. Перш ніж почати роботу, він вирішив постежити за подіями на ринку Ужляндії і придумати, як отримувати найбільший прибуток.

Степан дізнався, що кожен продавець продає один комп’ютер, і кожен покупець готовий купити рівно один комп’ютер. Всього на ринку торгують [latex]N[/latex] продавців, вартість комп’ютера у [latex]i[/latex]-го з них дорівнює [latex]A_{i}[/latex] Ужляндських монет, причому ціни можуть відрізнятися у різних продавців. Крім того, він знайшов для себе [latex]M[/latex] потенційних покупців, кожен з яких хоче купити комп’ютер за [latex]B_{i}[/latex] монет. При цьому сам Степан може купити і продати будь-яку кількість комп’ютерів.

Степану необхідно отримати найбільший прибуток (вигідно купити і вигідно продати). Тому він звернувся за допомогою до Вас — кращому програмісту Ужляндії.

Формат вхідних даних

Перший рядок вхідного файлу містить розділення одиночним пропуском два цілих числа [latex]N, M (1 \leqslant N, M \leqslant 10^{5})[/latex] — кількість продавців на ринку Байтландіі і кількість потенційних покупців відповідно.
Другий рядок містить [latex]N[/latex] цілих чисел [latex]A_{i} (0 \leqslant A_{i} \leqslant 10^{9})[/latex] — вартості, за якими продавці готові продавати комп’ютери.
Третій рядок містить [latex]M[/latex] цілих чисел [latex]B_{i} (0 \leqslant B_{i} \leqslant 10^{9})[/latex] — суми, які потенційні покупці готові віддати при покупці комп’ютера.

Формат вихідних даних

Перший рядок вихідного файлу має містити одне ціле число [latex]S[/latex] — розмір максимальної вигоди в монетах, яку може отримати Степан.

Тести

Вхідні дані Вихідні дані Пояснення до прикладів
1 2 3
1 1
3 3 3
4 Степан купує комп’ютери у 1-го і 2-го
продавців і продає їх будь-яким
двом покупцям.
2 6 5
5 10 8 4 7 2
3 1 11 18 9
27 Степану найбільш вигідно купити комп’ютери у 1-го, 4-го і 6-го продавців і продати 3-му, 4-му і 5-му покупцям.
3 4 5
6 7 9 8
3 3 5 1 2
0 Степану невигідно закуповувати техніку, адже ціни продавців перевищують суми, які готові віддати покупці.
4 4 5
4 4 4 4
6 4 3 9 2
7 Степану байдуже в кого купувати комп’ютери, але продати вигідно їх він зможе лише 1-му і 4-му покупцям.
5 3 3
5 1 3
9 8 6
14 Степан купує всі комп’ютери, адже всіх їх він зможе вигідно продати.
6 4 1
2 5 4 6
8
6 Покупець лише один, тому Степан має купити комп’ютер тільки у 1-го продавця.
7 3 6
1 7 4
0 0 0 0 0 0
0 Клієнти є, але ніхто з них не збирається платити, тож Степан не отримає прибутку.
8 4 2
0 7 4 6
0 3
3 Перший продавець віддає свій комп’ютер безкоштовно, а другий покупець готовий заплатити. Отже, Степан може заробити.
9 1 5
5
5 7 9 3 4
4 Хоча покупців багато, але продавець лише один. Степан має продати комп’ютер 3-му клієнту.

Код

Розв’язок

Щоб отримати маскимальну вигоду, Степан має купувати комп’ютери за найменшою ціною, а продавати якомога дорожче. Отже, потрібно створити масиви і відсортувати їх: масив вартостей, за якими продавці готові продавати комп’ютери — за зростанням; масив сум, які потенційні покупці готові віддати при покупці комп’ютера — за спаданням. Далі створюємо цикл, за допомогою якого розраховуємо вигоду від реалізації кожного комп’ютера. Оскільки масиви відсортовані, то, як тільки прибуток стане від’ємним або нульовим, можемо припинити розрахунки і вивести розмір максимальної вигоди.

Посилання

Код на ideone
Задача на e-olymp
Зарахований розв’язок на e-olymp

Related Images:

e-olymp 178. Каждый третий бесплатно

Задача

Барлимен Баттербар — владелец небезызвестного трактира «Гарцующий пони», расположенного в городке Бри. Именно сюда частенько наведываются уставшие после сражений орки, чтобы отведать кружечку-другую своего любимого напитка – гномоукладчика. Однако в последнее время стали появляться другие заведения, что привело к уменьшению количества клиентов трактира. Чтобы вернуть себе клиентов, Барлимен решил сделать в своем трактире акцию, что каждый заказавший определенное количество кружек гномоукладчика, получает еще один бесплатно. Естественно, чем меньше будет это количество, тем более привлекательной будет эта акция для клиентов, но с другой стороны, если оно будет слишком маленьким, то хозяин не сможет получать прибыль (а может даже и будет терпеть убытки).

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

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

Каждый тест задан в одной строке и содержит два целых числа: цену закупки одной кружки гномоукладчика $b$ и цену $c$ [latex](0 \leq b \lt c \leq 10^9)[/latex], по которой трактирщик ее продает. Последний тест содержит [latex]b = c = 0[/latex] и не обрабатывается.

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

Для каждого теста вывести в отдельной строке искомое минимальное количество кружек.

Тесты

Входные данные Выходные данные
5 8
100 1000
13 18
0 0
2
1
3
10 11
1 10
10 20
0 0
11
1
2
4 5
2 5
0 5
0 0
5
1
1

 

Код программы

Решение

Вводим первую пару. Условием работы цикла поставим ненулевой $c$ (так как из условия $b$ больше или равно нулю, а $c$ больше $b$ строго).

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

Однако, выразив прибыль как разность цены продажи и закупки, этот способ можно интерпретировать и как поиск минимального количества «разностей», превышающих закупочную цену одной кружки. Тогда можно увидеть схожесть этого действия с делением (15 / 3 — это столько же, сколько троек вмещает в себе пятнадцать). То есть нам нужно делить закупочную цену кружки на прибыль с неё. Но так как нам нужно всегда при этом иметь прибыль, будем брать целую часть от деления, и прибавлять к ней единицу (округлять вверх — не вариант в случае, например, когда цена продажи вдвое больше цены закупки — тогда ответом будет «одна кружка», что нам не подходит, потому что хоть трактир не будет в убытке, но он не получит и прибыли). Выводим формулу:

[latex]m = \bigg \lfloor \frac{b}{c — b} \bigg \rfloor + 1[/latex],

где $m$ — минимальное количество кружек.

Ссылки

e-olymp

Ideone

Related Images: