×

# GDOG - Editorial

Author: Pavel Sheftelevich
Editorialist: Pawel Kacprzak

CAKEWALK

Simple math

# PROBLEM:

You have $N$ coins. You are about to call any number of people between $1$ and $K$ and divide the coins to them in such a way that each person gets the same amount of coins and this amount is maximal. You take all coins left after this process. Your task is to compute the maximal number of coins which you can get.

# QUICK EXPLANATION:

For each possible number of people, compute the amount of coins which are left after the process. Finally, return the maximum from these values.

# EXPLANATION:

Let assume that you decided to call exactly $k$ people and you want to divide $N$ coins to them in the way described in the statement. It means, that each person gets the same amount of coins and this amount is maximal from all possible ones. You can simulate this process by giving one coin to all people at once until you have less than k coins, because then you cannot divide them equally. The number of coins which each person has after the process equals $N \mathbin{/} k$, where $\mathbin{/}$ is the integer division, i.e. $7 \mathbin{/} 3 = 2$. Based on this fact, it is easy to see that there are $r = N - k \cdot (N \mathbin{/} k)$ coins left after the process and this is the amount of coins which you get. Here $r$ is called a remainder after dividing $N$ by $k$ and it is very common in computation. Most programming languages have built in operation for computing a reminder. It is often represented by $\texttt{%}$ or $\texttt{mod}$.

Since $K$ is not so big, we can iterate over all possible values of it and for each of them, compute the remainder of $N \mathbin{/} k$, where k is the current number of people, and at the end print the maximum from these remainders.

Time complexity:

We are iterating over K values and for each of them we do constant time operations, so the total complexity is $O(K)$.

# AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution can be found here
Tester's solution can be found here

This question is marked "community wiki".

19.6k349497539
accept rate: 35%

# include <iostream>

using namespace std; int main() { long n,k,m,r; int t; cin>>t; while(t--) {cin>>n>>k; m=n/k; r=n-(m*k); cout<<r<<endl;

   }
return 0;


}

WHAT WRONG IN MY CODE???

(30 Dec '15, 18:50)

 4 The answer is directly : N%(N/(N/K+1)+1)... answered 31 Aug '15, 21:54 61●1 accept rate: 0% Nice! Can you give a short explanation on how it works? How did you land upon that equation? (26 Jun '16, 16:58) 1)When K>N, it will always return N. 2)When K>(N/2) but K<=N, it will always return (N/2)+1. 3)When K<=(N/2), it's a little tricky, but bear with me. Here it goes- our main goal is to choose a number num (1<=num<=K), so that (N%num) will be max for the given range of K. Now how do we do this? We choose num such that num is the smallest number such that N/K = N/num. (27 Jun '17, 15:32) This solution is wrong. Try with N = 100 and K = 7. Your solution will give answer as 2, but the correct answer is 4 (which is 100%6). The testdata has been updated to include this now. (31 May, 18:43) admin ♦♦0★ The testdata has been updated to include this now. SAVAGE !!!! LOL :) (16 Oct, 22:38)
 0 can anyone post much optimize method for this problem?? as this problem has very few test cases it works for this only... suppose problems has large test cases...10000 than this solution give tle.. answered 25 Aug '15, 13:44 1.1k●12●29 accept rate: 6%
 0 worst case complexity : K/2 better than editorial solution's time complexity: here is my code #include using namespace std; int main(){ int t,n,k; scanf("%d",&t); while(t--){ scanf("%d%d",&n,&k); int ans=0,d=1,fake_k; if(k==1) {cout<<"0"<k then you will definitely get this.. HAPPY CODING answered 25 Aug '15, 14:01 1.1k●12●29 accept rate: 6%
 0 still unable to understand..! answered 06 Nov '15, 05:53 1 accept rate: 0%
 0 What's wrong with my code? import java.util.Scanner; class GDOG { public static void main(String args[]) { Scanner in=new Scanner(System.in); int t=in.nextInt(); for ( int i=0; i=0 ) { n=res; res=n-k; } System.out.println(n); } } } answered 05 Dec '15, 00:23 4★aquabh 1 accept rate: 0%

whats wrong with my code?

# include <string.h>

using namespace std; int main() { int t,i; cin>>t; for (int z=1; z<=t; z++) {

    int n,k;
cin>>n>>k;

for (i=n; i>=1; --i)
{
if (k*i<=n)
{
break;

}

}

cout<<n-(k*i)<<endl;
}
return 0;


}

1
accept rate: 0%

 0 I thought the solution would simply be N%K but that seems to be incorrect. What am I missing? answered 14 May '16, 05:40 0★tommylau 1 accept rate: 0%
 0 Not working why??? import java.util.Scanner; class puppy{ public static void main(String args[]){ Scanner ashok=new Scanner(System.in); int test=ashok.nextInt(); int i; for(i=1;i<=test;i++){ int coins=ashok.nextInt(); int people=ashok.nextInt(); int j=1,x=1,count=1; while(j>0){ count=peoplex; if(count>coins){ System.out.println(coins-(people(x-1))); break; } //if(count==coins){ //System.out.println("0"); //break; //} x++; } } } } answered 25 May '16, 10:10 1 accept rate: 0%
 0 / * To change this license header, choose License Headers in Project Properties. * To change this template file, choose Tools | Templates * and open the template in the editor. / package javaapplication60; / Author : Pujan / import java.util.Scanner; class stack { public static void main(String[] args) { Scanner in = new Scanner(System.in); int x,y;  x = in.nextInt(); y=in.nextInt(); int temp = x/y; int temp1 = x%y; System.out.println("Max coins which people will get: "+temp); System.out.println("Coins which are left: "+temp1); } }  answered 25 May '16, 11:52 1 accept rate: 0%

# include<iostream>

using namespace std; int main() { int t; cin>>t; while(t--) { int n,k; cin>>n>>k; int r=0; while(k) { if((n-(n/k)k)>r) { r=n-(n/k)k; } else break; k--; } cout<<r<<endl;
} }

1
accept rate: 0%

# include<iostream>

using namespace std; int main() { long t,n,k,ans,i,a; cin>>t; while(t--) { cin>>n>>k; ans=0; for(i=2;i<=k;i++) { a=n%i; if(ans<a) ans=a; } cout<<ans<<"\n";

  }


return 0; }

1
accept rate: 0%

 0 What is wrong with this code? #include using namespace std; int main() { int x,y,t; cin>>t; while(t>0){ cin>>x>>y; if(y==0) cout<
 0 What is wrong with this code? #include using namespace std; int main() { int x,y,t; cin>>t; while(t>0){ cin>>x>>y; if(y==0) cout<
 0 @sprea27 Your code will fail in many cases, one of them is- When N=200, K=20 Your code will give (N%K)=0, Actual answer will be (100%17)=15 answered 20 Jun '17, 11:34 1 accept rate: 0%
 0 @sprea27 but that will not be maximum that people can have.. maximum can be 20 so why 17? answered 15 Oct '17, 15:14 1 accept rate: 0%
 0 Okay after scratching my head for sometime I got what the problem is about. The problem statement is somewhat misleading. The value of k is the number of people around the dog. We have to iterate over k to check how many people he should call so that the remainder is maximum. So simple n%k would not work and you have to find a number between 1 and k for which n%k is maxmimum. answered 25 Mar, 15:46 3★elli0t 47●3 accept rate: 4%
 0 Why is my code wrong? #include using namespace std; int main() { int t; cin>>t; for(int i=0; i> n >> k; int q,r; for(int j=1; j<=n+1; j++) { if(k>n/j) { q = (n/j)+1; r = n%q; break; } } cout << r << endl; } }  answered 05 Dec, 15:32 1●1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,198
×281
×41

question asked: 26 Jul '15, 14:36

question was seen: 6,925 times

last updated: 05 Dec, 15:32