You are not logged in. Please login at www.codechef.com to post your questions!

×

GDOG - Editorial

PROBLEM LINK:

Practice
Contest

Author: Pavel Sheftelevich
Tester: Vlad Mosko
Editorialist: Pawel Kacprzak

DIFFICULTY:

CAKEWALK

PREREQUISITES:

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".

asked 26 Jul '15, 14:36

admin's gravatar image

0★admin ♦♦
19.6k349497539
accept rate: 35%

edited 26 Jul '15, 15:07

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) shivam22963★

The answer is directly : N%(N/(N/K+1)+1)...

link

answered 31 Aug '15, 21:54

sumeetshirgure's gravatar image

6★sumeetshirgure
611
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) raviojha21053★

@raviojha2105

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) akashbhalotia4★

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) babangain3★

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..

link

answered 25 Aug '15, 13:44

rcsldav2017's gravatar image

5★rcsldav2017
1.1k1229
accept rate: 6%

edited 25 Aug '15, 13:45

worst case complexity : K/2 better than editorial solution's time complexity:

here is my code

#include<bits/stdc++.h>

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"<<endl; continue;}

       if(n<k) { cout<<n<<endl; continue;}

       if(n%k==0){ cout<<(n%(k-1))<<endl; continue;}

        while(1){

            fake_k=n/d;

             if(fake_k+1<=k){

                  ans=n%(fake_k+1);

                  break;
               }
               d++;

               if(!fake_k) break;
          }

           printf("%d\n",ans);
      }
     return 0;
 }

Idea of this solution is simple

to analyze this solution you can just take number and see what all value of mod if you are trying divide n with k where n>k

then you will definitely get this..

HAPPY CODING

link

answered 25 Aug '15, 14:01

rcsldav2017's gravatar image

5★rcsldav2017
1.1k1229
accept rate: 6%

still unable to understand..!

link

answered 06 Nov '15, 05:53

mayankmax80's gravatar image

2★mayankmax80
1
accept rate: 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<t; i++="" )="" {="" int="" n="in.nextInt();" int="" k="in.nextInt();" int="" res="n-k;" while="" (="" res="">=0 ) { n=res; res=n-k; } System.out.println(n); } } }

link

answered 05 Dec '15, 00:23

aquabh's gravatar image

4★aquabh
1
accept rate: 0%

whats wrong with my code?

include <iostream>

include <stdio.h>

include <algorithm>

include <iomanip>

include <math.h>

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;

}

link

answered 12 Dec '15, 19:44

shivam130896's gravatar image

1★shivam130896
1
accept rate: 0%

I thought the solution would simply be N%K but that seems to be incorrect. What am I missing?

link

answered 14 May '16, 05:40

tommylau's gravatar image

0★tommylau
1
accept rate: 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++; } } } }

link

answered 25 May '16, 10:10

ashokkumar863's gravatar image

0★ashokkumar863
1
accept rate: 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);

}
}
link

answered 25 May '16, 11:52

pujan7819's gravatar image

3★pujan7819
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;
} }

link

answered 26 Jun '16, 20:16

rishabpathak01's gravatar image

2★rishabpathak01
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; }

link

answered 11 Mar '17, 17:22

vikas_sangwan's gravatar image

2★vikas_sangwan
1
accept rate: 0%

What is wrong with this code? #include <iostream> using namespace std;

int main() { int x,y,t; cin>>t; while(t>0){ cin>>x>>y; if(y==0) cout<<x; else cout<<x%y<<endl; t--; } return 0; }

link

answered 15 Apr '17, 09:34

sprea27's gravatar image

2★sprea27
1
accept rate: 0%

What is wrong with this code?

#include <iostream>
 using namespace std;

 int main() {
 int x,y,t;
 cin>>t;
    while(t>0){
     cin>>x>>y;
      if(y==0)
        cout<<x;
      else
     cout<<x%y<<endl;
     t--;
}
return 0;

}

link

answered 15 Apr '17, 09:40

sprea27's gravatar image

2★sprea27
1
accept rate: 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

link

answered 20 Jun '17, 11:34

vivek091195's gravatar image

0★vivek091195
1
accept rate: 0%

@sprea27 but that will not be maximum that people can have.. maximum can be 20 so why 17?

link

answered 15 Oct '17, 15:14

tpriyanshu90's gravatar image

1★tpriyanshu90
1
accept rate: 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.

link

answered 25 Mar, 15:46

elli0t's gravatar image

3★elli0t
473
accept rate: 4%

Why is my code wrong?


#include<iostream>
using namespace std;
int main()
{
    int t;
    cin>>t;

    for(int i=0; i<t; i++)
    {
    int n,k;
    cin >> 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;
}
}
link

answered 05 Dec, 15:32

sahil0907's gravatar image

0★sahil0907
11
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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