codeforces Guest From the Past problem

general
,
1

link to the problem http://codeforces.com/contest/625/problem/A
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.

2

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-

10
11
9
8

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.

Mathematically-

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-

n-k(b-c)

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-

n-k(b-c)=c

==>k=(n-c)/(b-c)

In case of any discrepancy, comment/mail me.

alt text

2 Likes
3

very well explained!

4

Thanks dear :slight_smile: