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

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

  1. Зачтено. Вот только два раза писать ввод данных не самое правильное решение. Посмотрите на досуге эту статью. Лучше прямо писать, чего Вы хотите:

Добавить комментарий