CMPLS - Complete the Sequence!

Problem Link:-

   
http://www.spoj.com/problems/CMPLS/

Prerequisite:-

Method of differences

Solution:-

	#include<bits/stdc++.h>
	using namespace std;
	int s,c;
	int a[100];
	int main(){
	int t;
	cin>>t;
	while(t--){
	cin>>s>>c;
	for(int i=0;i<s;i++)
	cin>>a[i];
	vector<int>v[100];
	int flag=0;
	for(int i=0;i<s;i++){
	v[0].push_back(a[i]);
	if(i>0&&a[i]!=a[i-1])
	flag=1;
	}
	int k=1;
	while(flag==1&&v[k-1].size()>1){
	flag=0;
	for(int i=1;i<v[k-1].size();i++){
	v[k].push_back(v[k-1][i]-v[k-1][i-1]);
	if(i>1&&v[k][i-1]!=v[k][i-2]){
	flag=1;
	}
	}
	k++;
	}
	int l=v[k-1].size();
	for(int i=0;i<c;i++){
	v[k-1].push_back(v[k-1][l-1]);
	}
	for(int i=k-2;i>=0;i--){
	for(int j=c;j>0;j--){
	v[i].push_back(v[i][v[i].size()-1]+v[i+1][v[i+1].size()-j]);
	}
	}
	for(int i=v[0].size()-c;i<v[0].size();i++)
	cout<<v[0][i]<<" ";
	cout<<endl;
	}
	return 0;
	}

view raw CMPLS hosted with ❤ by GitHub

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