Coins codechef

codechef coins dynamicprogramming dp

question link: https://www.codechef.com/problems/COINS

Help me to optimize my code, its giving correct output , but for larger values like 10^8 it is having problem.

#include<bits/stdc++.h>

#define lli long long int
#define ulli unsigned long long int
#define li long int
#define total(n) (n/2+n/3+n/4)

using namespace std;
ulli alucard(lli n)
{	if(n<12)
		return n;
	if(total(n)<=n)
		return n;
	ulli temp=alucard(n/2)+alucard(n/3)+alucard(n/4);
	return temp;
}
int main()
{	
	int t;
	cin>>t;
	while(t--)
	{	lli n;
		cin>>n;
		cout<<alucard(n)<<"\n";
	}
	return 0;
}

 

Samrat
Samrat De
Samrat

Please Log in to answer

Note: Your answer should not be too short. Please wait a few seconds for the editor to load



Please make sure the answer is not too short

1 Answer

nky_007
nky_007 23:04, Mar 25
Narendra Kumar Yadav

In the question test cases aren't given in the input. So use 

        while(scanf("%lld",&n)!=EOF)

        {

        }

instead of taking any test case.

Hint : Use some data structure (say map) to store values instead of calculating again and again.




Please make sure the answer is not too short
2 Upvotes
Comments
No Comments yet