codeforces Guest From the Past problem

link to the problem
in the editorial of this problem it is given that number of glass bottles he will be able buy are floor(n-c/b-c) .How this number is floor(n-c/b-c). Please explain. Thanks in advance.

You want the logical proof or mathematical proof?

Logically explaining-

  • When n <=c, its obvious that he cannot buy any more bottles.
  • Hence, in a way, the ‘effective’ money he has is “n-c”
  • The effective cost of a bottle is b-c, as easily deduced.

Take an example-


He has 10 rupees. He can buy a bottle of 9 and get 8 back. Now he has , so he can again buy a bottle and get 8 back. Note that now he is left with 8, and he can do nothing of it. He has 8 money, but effectively its equivalent to 0 (as he cannot use it anywhere). Hence by logic, the effective money is n-c. And effective price is b-c, as easily seen.


Let n be the money initially. Its easy to see, that after buy maximum possible bottles, we are left with money c. Also, if we buy k bottles, then the money we have after buy k bottles is-

Money= n- k(b-c)

Hence we can say that money after buying 1,2,3 bottles is as-

  • n-(b-c)
  • n-2(b-c)
  • n-3(b-c)

Appreciate it that it is an AP. We have initial term n, final term c, and we have to find number of bottles bought (i.e. k).

Now, money after buying k bottles is-


And after buying max possible bottles, the money we have is c. So if k is maximum possible bottles, then the amount we are left with should be c-



In case of any discrepancy, comment/mail me.

alt text


very well explained!

Thanks dear :slight_smile: