MUFFINS3 - Editorial

Explanation on point. Thank you so much @ajaypanthagani

1 Like

You are considering that smallest size of cupcakes will be two and so goon and chectk the maximum size of cupcakes.

But itā€™s take 1.01 second :neutral_face: :neutral_face:

#include<bits/stdc++.h>
using namespace std;

#define ll long long int
int main() {
int T;
cin>>T;
while(Tā€“) {
ll N;
cin>>N;
int size,lft,var=0;
if(N==2)
cout<<N<<endl;
else {
for(int i=2;i<= N/2 + 1;i++) {
if(N%i!=0) {
lft=N%i;
if(var<=lft) {
var=lft;
size=i;
}
}
}
cout<<size<<endl;
}

}
}

the number will substract by itself which results 0 ie no cupcakes is leftā€¦

nice explanation, Thanks for explanation!

I tried with this but its giving TLE :cry:

 #include <iostream>
#include <math.h>
using namespace std;
int result(int num)
{
    int max=-1;
    for(int i=1;i<=num;++i)
    {
        if(abs(num%i)>max)
        max=abs(num%i);
    }
    return max;
}

int main() {
	// your code goes here
	int t,n;
	cin>>t;
	while(t--)
	{
	    cin>>n;
	    cout<<(n-result(n))<<endl;
	}
	return 0;
}

I think i have explained pretty well through example.

Take example of n = 11.
Number of muffins = 11
Package Size = 1 2 3 4 5 6 7 8 9 10 11
Cupcakes Remaining = 0 1 2 3 1 5 4 3 2 1 0 (we get remaining Cupcakes by n % package size)

now, take the case of n = 15
Package Size = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Cupcakes Remaining = 0 1 0 3 0 3 1 7 6 5 4 3 2 1 0

clearly, you can see if package size is n / 2 + 1 we get max number of cupcakes for chef i.e if package size is 6 in
case of 11 muffins remaining cupcakes is 5 and if package size is 8 in case of 15 muffins remaining cupcakes is 7
which is the max the chef can get. So for n number of muffins package size should be n / 2 + 1 so that chef can get
max number of muffins in hand.

4 Likes

same bro! have you got the cause?

1 Like

Thanksā€¦This explanation is pretty simple.

nope :frowning_face:

here there are two variables namely, the chef choses how many he wants to eat , and chef chooses the size of the package

if chef always want to get maximum on the more he can eat, then chef would always choose the size of the package as 1 right ? , so the maximum is N-1,

why is there so much explaination and confusion of n%a, n%2 round?

such a confusing question, from my side i think the answer is just n-1, chef can always choose the package size to be 1, and he can always choose to give only one cupcake, and the maximum he will have is n-1.simple

Wonderful Explanation! Even a beginner can also be able to understand it very easily. Thank you @ajaypanthagani for this explanation

1 Like

yes obviously !!

The answer is very simple after many testing
the always come is number by 2 +1

#include <iostream>
using namespace std;

int main() {
	// your code goes here
	int t;
	cin>>t;
	long int n;
	while(t--)
	{
	    cin>>n;
	        cout<<(n/2)+1<<"\n";
	}
	return 0;
}

Perfect ! Got it.
Thank you!

Explanation:
Chef want to eat maximum remaining cupcakes so, we have to find the divisor that gives maximum remainder

We can find the maximum possible remainder(N%A) using loop from 1 to N but it will give us Time Limit Exceed(TLE) error as the time limit is 1sec

As we have to find an integer A(devisor) which is between 1 and N
For any value of N(Can be even or odd), A would be between (N/2 < A < N)

So, the possible value of A would be = (N/2)+1

Thank you so much @ajaypanthagani for explaining in a simple way

HOW?

hindi me smjhe sir

Right I used the same logic and got the error