COINS - Bytelandian gold coins

Prerequisite:-

Dynamic programming

Solution:-

	#include<bits/stdc++.h>
	using namespace std;
	long long ans(long long n,vector<long long>&dp){
	if(n==0)
	return 0;
	if(dp[n])
	return dp[n];
	return dp[n]=max(n,ans(n/2,dp)+ans(n/3,dp)+ans(n/4,dp));
	}
	int main(){
	long long n;
	while(scanf("%lld",&n)!=EOF){
	//cin>>n;
	//cout<<"n= "<<n<<endl;
	vector<long long>dp(n+1,0);
	cout<<ans(n,dp)<<endl;
	}
	return 0;
	}

view raw COINS - Bytelandian gold coins hosted with ❤ by GitHub

ALIEN - Aliens at the train

prerequisite: -  Kadane's algorithm, window sliding technique

Solution:-

	#include<bits/stdc++.h>
	using namespace std;
	int main(){
	int t;
	cin>>t;
	while(t--){
	int n,b;
	cin>>n>>b;
	int a[n];
	for(int i=0;i<n;i++)
	cin>>a[i];
	int glsum=0,tempsum=0,glcnt=0,tempcnt=0;
	for(int i=0,j=0;i<n&&j<n;){
	if(i>j){
	j++;
	continue;
	}
	if(tempsum+a[j]<=b){
	tempcnt++;
	tempsum+=a[j];
	j++;
	}
	else{
	if(tempcnt>glcnt){
	glcnt=tempcnt;
	glsum=tempsum;
	}
	else if(tempcnt==glcnt&&glsum>tempsum){
	glsum=tempsum;
	}
	tempsum-=a[i];
	tempcnt--;
	i++;
	}
	}
	if(tempcnt>glcnt){
	glcnt=tempcnt;
	glsum=tempsum;
	}
	else if(tempcnt==glcnt&&glsum>tempsum){
	glsum=tempsum;
	}
	cout<<glsum<<" "<<glcnt<<endl;
	}
	return 0;
	}

view raw ALIEN - Aliens at the train hosted with ❤ by GitHub