Greedy Puppy - Need Clarity on problem statement

help
, , ,
1

Problem : https://www.codechef.com/problems/GDOG

Hi,

I don’t have clarity in the above mentioned problem statement. I also gone through some correct submissions but I didn’t found the way problem was handled. So anyone willing to help can give clarity for my below approach.

My approach

n-((n/k)*k) or (n%k) (why this expression gives Wrong Answer)

Thanks

2

Your approach is wrong.
Actually You have to choose i (1<=i<=k) : n%i is maximum

3

Thanks for your help.

I too seen this approach in successful submission. But why this is being followed?

If ‘k’ persons are there, then they will divide the coins equally. And the dog will pick the left over coins. Can you explain the specific thing where this approach went wrong with an example.

4

n=9 k=3
if he calls 3 person he would get 0 coins. and if he calls 2 persons he would get 1 coin.
As mentioned in the question, You have to maximize the last over coins, so you will have to check for every possibility.

1 Like
5

Okay. Now I understood that,

from 1 to K, in which number of people the dog can earn more coins.

Initially I thought the K peoples are called and find the coins dog can earn.

Thanks for your time and explanation…