#include<bits/stdc++.h>
using namespace std;
long long int emerald(long long int sticks ,long long int diamonds)
{
if(sticks <= 0 || diamonds <= 0 ||(sticks == 1 && diamonds == 1) )
return 0;
else
return max(1+emerald(sticks - 1 , diamonds-2), 1+emerald(sticks-2,diamonds-1));
}
int main()
{
int t;
cin>>t;
while(t--)
{
long long int sticks , diamonds;
cin>>sticks>>diamonds;
cout<<emerald(sticks,diamonds)<<"\n";
}
}
-----------------------------------------------------------------------
Imagine the number of times recursion runs.
Looks like the issue is stack overflow. You are having too many recursive calls.Even if you use memoization, total memory will be 10^8*10^8 for the given test which itself will cause memory limit exceeded.So better try to come up with efficient algorithm both in terms of space and time.
In A problem I don't think they will give so much implementation to do The solution will have 1-2 if/else statement or some loop
the solution should be O(1), your code run wrong because it call emerald() too many times
I can understand the frustration, problem A gave me a lot of trouble too in the contest, what makes me even more angry at myself is that I had a problem similar to this just a week ago, and still I was not able to solve as quickly as a I wanted to in this contest.
Anyway, there is a very simple solution to this problem. If you don't want to hear me explanation, you can just see the solution link, I think my code is pretty self-explanatory — https://mirror.codeforces.com/contest/1366/submission/83417205
Here is the explanation — DON'T over-complicate this problem, the answer is as simple as (a+b)/3, because, eventually it boils down to this, you are using 3 "resources" to make 1 "product" (2a1b, 1a2b), hence the answer is the quotient of (a+b)/3, there is catch though, what if either of a or b is less than (a+b)/3? then our answer in this case would be min(a,b).
Hence, the final answer to this problem is — min((a+b)/3,min(a,b))
I think it should be
min((a+b)/3, min(a, b))
Ah, ya, sorry, made a typo.