Nice! Can you give a short explanation on how it works? How did you land upon that equation?
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.
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.
1 Like
The testdata has been updated to include this now.
SAVAGE !!! LOL 
So simple n%k would not work and you have to find a number between 1 and k for which n%k is maxmimum.
t = int(input())
for i in range(t):
n,k = map(int,input().split())
data = []
for j in range(1,k+1):
data.append(n%j)
print(max(data))
We can start from k and instead going down to 1 we can go to whatever maximum mod m we are getting. Because going further down will only yield [0, m-1]
This will result in faster closing of loop.
Hereās my code:
#include <iostream>
using namespace std;
int main(){
int t, n, k, i, m;
cin >> t;
while(t-->0){
cin >> n >> k;
m = n%k;
for(i=k; i>m; --i){
if(n%i>m) m = n%i;
}
cout << m << endl;
}
return 0;
}why am I getting partially solved though I have 100% for subtasks?
Can anyone please explain?
Here is my code
#include < iostream>
using namespace std;int main() {
int tests = 0;
cin>>tests;
while(testsā)
{
long long int N = 0, K = 0, res = 0;
cin>>N;
cin>>K;
res = 0;
while(K>0)
{
if(N%K > res)
{
res = N%K;
}
Kā;
}
cout<<res<<endl;
}
return 0;
}
What is wrong in my code? It is giving RE(NZEC)
def func(n,k):
if k==1:
return 0
else:
return max(n%k,func(n,k-1))
for i in range(int(input())):
n,k=map(int,input().split())
print(func(n,k))
Simple java solution 
import java.util.;
import java.lang.;
import java.io.*;
/* Name of the class has to be āMainā only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc=new Scanner(System.in);
try{ int t=sc.nextInt();
for(int k=0;k<t;k++)
{
int n=sc.nextInt();
int m=sc.nextInt();
int x=0;
for(int i=1;i<=m;i++)
{
x=Math.max(x,n%i);
}
System.out.println(x);
}
}catch(Exception e){};
}
}
why u are taking y==0 ,itās start from 1 that is given in question,and you did not understand the question ,read again.
Try this
#include<bits/stdc++.h>
using namespace std;
int main() {
int T;
cin>>T;
while(Tā) {
int N,K;
cin>>N>>K;
int count=0;
if(N==K) {
cout<<count<<"\n";
}
else if(N<K) {
cout<<N<<"\n";
}
else {
for(int i=1;i<=K;i++) {
count=N%i>count?N%i:count;
}
cout<<count<<"\n";
}
}
}
look at my codeā¦
#include
using namespace std;
int main() {
int t;
cin>>t;
while(tā)
{
int n,k;
cin>>n>>k;
int rem,max=0;
for(int i=1;i<=k;i++)
{
rem=n%i;
if(rem>max)
{
max=rem;
}
}
cout<<max<<endl;
}
return 0;
}
thanks for your explaination
Can Somebody Explain why we should return n when k>n ?
The dog would not get any coin because chest wasnāt open.
1 Like
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t-->0){
int n = sc.nextInt();
int k = sc.nextInt();
int max = 0;
for(int i=1;i<=k;i++){
int temp = n%i;
if(temp>max){
max=temp;
}
}
System.out.println(max);
}
}
}
k is only a maximum, not the exact people called,
so we can set k = n+1 and in that case,answer = n
1 Like
Itās interesting to consider a full table of various bark strengths against a moderate size number of coins, say 28.
| bark | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 |
| coins/dog | 0 | 0 | 1 | 0 | 3 | 4 | 0 | 4 | 1 | 8 | 6 | 4 | 2 | 0 | 13 | 12 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | 28 | 28 | 28 |
| coins/pers | 28 | 14 | 9 | 7 | 5 | 4 | 4 | 3 | 3 | 2 | 2 | 2 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 |
This is a useful study for thinking about how to find the right answer without much further commentary, so my comments below can be ignored if desired.
Apart from seeing that calling more people than there are coins gets the full pot for the dog, there are long stretches where the people are getting the same number of coins each and the only one we need to test is the lowest value of that stretch, which gives the most coins for the dog.
So for example 2 coins per person stretches from 10 people to 14 people (28/2), but 10 would be the right maximizing choice out of that set. And can we find the value 10 directly? Yes, itās one more than the start of 3-coin region, which is [28/3]=9 and below.
We transition to single values of coins/person below the square root of the total coins - where the number of coins/person reaches and exceeds the number of people. And trivially the dog will never get more coins than the number of people.
This suggests a strategy of stepping down through interesting bark strengths until the best result so far is more than the bark strength under consideration.
1 Like
Hey, since the problem states that Tuzik should call people such that he get the maximum coins.
Now in the problem test case 1 for 5 coins he calls 2 people and he is left with one coin.
But isnāt he supposed to call 3 people such that they will each get 1 coin each and Tuzik will be left with two coins.
Thank you for the clarification!!
what is wrong in my code?
#include
using namespace std;
int main() {
// your code goes here
int t;
cin>>t;
while(tā)
{
int n,k;
cin>>n>>k;
int i=1;
while(i*i<=n && i<=k) i++;
cout<<(n%(i-1))<<endl;
}
return 0;
}