Can somebody help me with this problem?
Looks like an easy problem, but I can’t find a solution to this.
→ Problem link
Thank you.
We can solve this in O(\sqrt{n}), I’m not aware of a faster algorithm.
Let’s assume a\geq b without loss of generality.
Now let’s try to find the minimum wastage, if we choose a, i times.
The least wastage we can get is (c-ai)\%b, because how many ever b I choose, The excess left will be the same mod b. There are at most b distinct values (c-ai)\%b can take, and is only dependent on the previous state, Hence forms a cycle of size not exceeding b. So we can Iterate i from 0 to b, and find the least value of (c-ai)\%b, But if c-ai becomes less than 0, then, I cannot choose these many a, so we can break there. So the time complexity is O(min(b,c/a)), which is equivalent to O(\sqrt{n}) , as a\geq b.
Code
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int a,b,c;
cin>>a>>b>>c;
int mn=2e9 + 7;
int ans1,ans2;
bool swapped=0;
if(b>a){
swapped=1;
swap(a,b);
}
for(int i=0;i<b;i++){
if((c-(i * a))<0){
break;
}
if((c- (i * a))%b < mn){
mn=(c - (i*a))%b;
ans1=i;
ans2=(c-i*a)/b;
}
}
if(swapped){
cout<<ans2<<" "<<ans1;
}
else{
cout<<ans1<<" "<<ans2;
}
//No application of chicken Mcnugget Theorem.
//Dissapointing
}