July 2015 – Live with passion

11466

Asif NaeemJuly 28, 2015

There should be a better approach to improve the time complexity.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <cmath>

#define ull unsigned long long
#define ll long long

using namespace std;

bool prime[35000000];
vector<int> prm;


int main()
{
	double n;
	int mxprime,cnt;
	ull num;
	for(int i=2;i<35000000;i++)
	{
		if(prime[i]==0)
		{
			prm.push_back(i);
			for(int j=i+i;j<35000000;j+=i)
			{
				prime[j]=1;
			}
		}
	}
	while(scanf("%lf",&n),n!=0)
	{
		mxprime=-1;
		if(n<0)
		num=n*(-1);
		else
		num=n;
		if(n==1 || n==2 || n==3)
		{
			printf("-1\n");
		}
		else
		{
			int idx=prm.size();
			cnt=0;
			for(int i=0;i<idx;i++)
			{
				if(num<prm[i])
				break;
				if(num%prm[i]==0)
				{
					mxprime= (mxprime>prm[i]?mxprime:prm[i]);
					cnt+=1;
				}
				while(num%prm[i]==0)
				{
					num/=prm[i];
				}
			}
			if(num==1)
			{
				if(n!=mxprime)
				{
					if(cnt>1)
					printf("%d\n",mxprime);
					else
					printf("-1\n");
				}

				else
				printf("-1\n");
			}
			else
			{
				if(mxprime<num)
				printf("%llu\n",num);
				else
				{
					if(cnt>1)
					printf("%d\n",mxprime);
					else
					printf("-1\n");
				}
			}
		}

	}
	return 0;
}

#include <iostream>

#include <cstdio>

#include <cstring>

#include <string>

#include <vector>

#include <cmath>

#define ull unsigned long long

#define ll long long

using namespace std;

bool prime[35000000];

vector<int> prm;

int main()

{

double n;

int mxprime,cnt;

ull num;

for(int i=2;i<35000000;i++)

{

if(prime[i]==0)

{

prm.push_back(i);

for(int j=i+i;j<35000000;j+=i)

{

prime[j]=1;

}

while(scanf("%lf",&n),n!=0)

{

mxprime=-1;

if(n<0)

num=n*(-1);

else

num=n;

if(n==1 || n==2 || n==3)

{

printf("-1\n");

}

else

{

int idx=prm.size();

cnt=0;

for(int i=0;i<idx;i++)

{

if(num<prm[i])

break;

if(num%prm[i]==0)

{

mxprime= (mxprime>prm[i]?mxprime:prm[i]);

cnt+=1;

}

while(num%prm[i]==0)

{

num/=prm[i];

}

if(num==1)

{

if(n!=mxprime)

{

if(cnt>1)

printf("%d\n",mxprime);

else

printf("-1\n");

}

else

printf("-1\n");

}

else

{

if(mxprime<num)

printf("%llu\n",num);

else

{

if(cnt>1)

printf("%d\n",mxprime);

else

printf("-1\n");

}

return 0;

}

11369

Asif NaeemJuly 27, 2015

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>

#define ll long long

using namespace std;

vector<int> vb;

bool cmp(int a,int b)
{
	return a>b;
}
int main()
{
	int t,n,a;
	cin>>t;
	ll sum;
	while(t--)
	{
		cin>>n;
		vb.clear();
		for(int i=0;i<n;i++)
		{
			cin>>a;
			vb.push_back(a);
		}
		sort(vb.begin(),vb.end(),cmp);
		if(n<3)
		printf("0\n");
		else
		{
			sum=0;
			for(int i=2;i<n;i+=3)
			sum+=vb[i];
		}
		printf("%lld\n",sum);
	}
	return 0;
}

#include <iostream>

#include <cstdio>

#include <cstring>

#include <string>

#include <vector>

#include <algorithm>

#define ll long long

using namespace std;

vector<int> vb;

bool cmp(int a,int b)

{

return a>b;

}

int main()

{

int t,n,a;

cin>>t;

ll sum;

while(t--)

{

cin>>n;

vb.clear();

for(int i=0;i<n;i++)

{

cin>>a;

vb.push_back(a);

}

sort(vb.begin(),vb.end(),cmp);

if(n<3)

printf("0\n");

else

{

sum=0;

for(int i=2;i<n;i+=3)

sum+=vb[i];

}

printf("%lld\n",sum);

}

return 0;

}

11059

Asif NaeemJuly 26, 2015

#include <iostream>
#include <cstdio>
#include <cstring>

#define ll long long
//-1000000000000000000
using namespace std;

int main()
{
	int n,kase=1;
	int a[20];
	ll max_end_here,max_so_far;

	while(scanf("%d",&n)!=EOF)
	{
		for(int i=0;i<n;i++)
		{
			scanf("%d",&a[i]);
		}
		max_so_far=0;
		for(int i=0;i<n;i++)
		{
			for(int j=i;j<n;j++)
			{
				max_end_here=1;
				for(int k=i;k<=j;k++)
				{
					max_end_here*=a[k];
				}
				if(max_so_far<max_end_here)
					max_so_far = max_end_here;
			}
		}
		printf("Case #%d: The maximum product is %lld.\n\n",kase++,max_so_far);
	}
	return 0;
}

#include <iostream>

#include <cstdio>

#include <cstring>

#define ll long long

//-1000000000000000000

using namespace std;

int main()

{

int n,kase=1;

int a[20];

ll max_end_here,max_so_far;

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

{

for(int i=0;i<n;i++)

{

scanf("%d",&a[i]);

}

max_so_far=0;

for(int i=0;i<n;i++)

{

for(int j=i;j<n;j++)

{

max_end_here=1;

for(int k=i;k<=j;k++)

{

max_end_here*=a[k];

}

if(max_so_far<max_end_here)

max_so_far = max_end_here;

}

printf("Case #%d: The maximum product is %lld.\n\n",kase++,max_so_far);

}

return 0;

}

10714

Asif NaeemJuly 25, 2015

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>

//#define INF 10000000
using namespace std;

int main()
{
	int t,diff,mn,mx;
	int len,num,a,c,d;
	int early,late;
	scanf("%d",&t);

	while(t--)
	{
		scanf("%d%d",&len,&num);
		mn=0;
		mx=0;
		for(int i=0;i<num;i++)
		{
			scanf("%d",&a);
			diff= len-a;
			c = max(diff,a);
			d = min(diff,a);
			mx = max(mx,c);
			mn = max(mn,d);
			//early=max(d,mn);
		}
		printf("%d %d\n",mn,mx);
	}
	return 0;
}

#include <iostream>

#include <cstdio>

#include <cstring>

#include <string>

//#define INF 10000000

using namespace std;

int main()

{

int t,diff,mn,mx;

int len,num,a,c,d;

int early,late;

scanf("%d",&t);

while(t--)

{

scanf("%d%d",&len,&num);

mn=0;

mx=0;

for(int i=0;i<num;i++)

{

scanf("%d",&a);

diff= len-a;

c = max(diff,a);

d = min(diff,a);

mx = max(mx,c);

mn = max(mn,d);

//early=max(d,mn);

}

printf("%d %d\n",mn,mx);

}

return 0;

}

10533

Asif NaeemJuly 24, 2015

#include <iostream>
#include <cstdio>
#include <sstream>
#include <string>

using namespace std;

bool prime[1000001];
bool firstPrime[1000001];
int primeCount[1000001];

bool checkdigit(int a)
{
	int sum;
	if(a<10)
	return 1;
	else
	{
		sum=0;
		while(a)
		{
			sum+=a%10;
			a/=10;
		}
		if(firstPrime[sum]==0)
		return 1;
		else
		return 0;
	}
	return 0;
}
int main()
{
	int cnt=0;
	prime[0]=1;
	prime[1]=1;
	firstPrime[0]=1;
	firstPrime[1]=1;
	primeCount[0]=cnt;
	primeCount[1]=cnt;
	for(int i=2;i<1000001;i++)
	{
		if(prime[i]==0)
		{
			if(!checkdigit(i))
				prime[i]=1;
			else
			{
				cnt+=1;
			}
			for(int j=i+i;j<1000001;j+=i)
			{
				prime[j]=1;
				firstPrime[j]=1;
			}
		}
		primeCount[i]=cnt;
	}
	int t,a,b,add;
	scanf("%d",&t);
	while(t--)
	{
		add=0;
		scanf("%d%d",&a,&b);
		if(firstPrime[a]==0 && checkdigit(a))
		add=1;
		printf("%d\n",primeCount[b]-primeCount[a]+add);
	}
	return 0;
}

#include <iostream>

#include <cstdio>

#include <sstream>

#include <string>

using namespace std;

bool prime[1000001];

bool firstPrime[1000001];

int primeCount[1000001];

bool checkdigit(int a)

{

int sum;

if(a<10)

return 1;

else

{

sum=0;

while(a)

{

sum+=a%10;

a/=10;

}

if(firstPrime[sum]==0)

return 1;

else

return 0;

}

return 0;

}

int main()

{

int cnt=0;

prime[0]=1;

prime[1]=1;

firstPrime[0]=1;

firstPrime[1]=1;

primeCount[0]=cnt;

primeCount[1]=cnt;

for(int i=2;i<1000001;i++)

{

if(prime[i]==0)

{

if(!checkdigit(i))

prime[i]=1;

else

{

cnt+=1;

}

for(int j=i+i;j<1000001;j+=i)

{

prime[j]=1;

firstPrime[j]=1;

}

primeCount[i]=cnt;

}

int t,a,b,add;

scanf("%d",&t);

while(t--)

{

add=0;

scanf("%d%d",&a,&b);

if(firstPrime[a]==0 && checkdigit(a))

add=1;

printf("%d\n",primeCount[b]-primeCount[a]+add);

}

return 0;

}

A few things figuring out helped to solve this problem. for n+2 gon there are maximum n*(n+1)/2 -1 (summation of n natural numbers -1 = S) diagonals and minimum S-(n-1) diagonals, that means for S-(n-1) number of diagonals we need minimum n+2 polygon. Example : there is no diagonal for triangle , 2 diagonals for Quadrilaterals

Continue Reading “10784” →

644

Asif NaeemJuly 23, 2015

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>

using namespace std;

struct node{
	bool end;
	node *nxt[2];
	node()
	{
		end=false;
		for(int i=0;i<2;i++)
		nxt[i]=NULL;
	}
}*root;
int main()
{
	string str,s;
	int id;
	node *cur,*tmp;
	int kase=1;
	while(cin>>str)
	{
		bool decodable=1;
		root=new node();
		cur=root;
		int i;
		for( i=0;i<str.size()-1;i++)
		{
			id=str[i]-'0';
			if(cur->nxt[id]==NULL)
			{
				cur->nxt[id]=new node();
			}
			cur=cur->nxt[id];
		}
		id=str[i]-'0';
		if(cur->nxt[id]==NULL)
		{
			cur->nxt[id]=new node();
		}
		cur=cur->nxt[id];
		cur->end=1;
		while(cin>>s)
		{
			if(s=="9")
			break;
			if(decodable==0)
			continue;
			tmp=root;
			int j;
			for( j=0;j<s.size()-1;j++)
			{
				id=s[j]-'0';
				if(tmp->nxt[id]==NULL)
					tmp->nxt[id]=new node();
				tmp=tmp->nxt[id];
				if(tmp->end==1)
				{
					decodable=0;
					j=s.size();
				}
			}
			id=s[j]-'0';
			if(tmp->nxt[id]==NULL)
				tmp->nxt[id]=new node();
			else
				decodable=0;
			tmp=tmp->nxt[id];
			tmp->end=1;
		}
		if(decodable)
		cout<<"Set "<<kase++<<" is immediately decodable\n";
		else
		cout<<"Set "<<kase++<<" is not immediately decodable\n";
	}
	return 0;
}

#include <iostream>

#include <cstdio>

#include <cstring>

#include <string>

using namespace std;

struct node{

bool end;

node *nxt[2];

node()

{

end=false;

for(int i=0;i<2;i++)

nxt[i]=NULL;

}

}*root;

int main()

{

string str,s;

int id;

node *cur,*tmp;

int kase=1;

while(cin>>str)

{

bool decodable=1;

root=new node();

cur=root;

int i;

for( i=0;i<str.size()-1;i++)

{

id=str[i]-'0';

if(cur->nxt[id]==NULL)

{

cur->nxt[id]=new node();

}

cur=cur->nxt[id];

}

id=str[i]-'0';

if(cur->nxt[id]==NULL)

{

cur->nxt[id]=new node();

}

cur=cur->nxt[id];

cur->end=1;

while(cin>>s)

{

if(s=="9")

break;

if(decodable==0)

continue;

tmp=root;

int j;

for( j=0;j<s.size()-1;j++)

{

id=s[j]-'0';

if(tmp->nxt[id]==NULL)

tmp->nxt[id]=new node();

tmp=tmp->nxt[id];

if(tmp->end==1)

{

decodable=0;

j=s.size();

}

id=s[j]-'0';

if(tmp->nxt[id]==NULL)

tmp->nxt[id]=new node();

else

decodable=0;

tmp=tmp->nxt[id];

tmp->end=1;

}

if(decodable)

cout<<"Set "<<kase++<<" is immediately decodable\n";

else

cout<<"Set "<<kase++<<" is not immediately decodable\n";

}

return 0;

}

12293

Asif NaeemJuly 23, 2015

The solution can be found by observation that if one player finds the total number of ball that is equal (2^n -1) then the player is looser. i.e. we find for n=3 it is true, so, if n=3 1st player looses, for n=4 1st player wins n=5 1st player wins, for n=6 1st player wins, for n=7 1st player

Continue Reading “12293” →

11311

Asif NaeemJuly 23, 2015

#include <stdio.h>
#include <iostream>

using namespace std;

int main()
{
	int n,a,b,c,d,aa,bb,ans,t;
	cin>>t;
	while(t--)
	{
		cin>>a>>b>>c>>d;
		aa=a-c-1;
		bb=b-d-1;
		ans=aa^bb^c^d;
		if(ans==0)
		cout<<"Hansel\n";
		else
		cout<<"Gretel\n";
	}
	return 0;
}

#include <stdio.h>

#include <iostream>

using namespace std;

int main()

{

int n,a,b,c,d,aa,bb,ans,t;

cin>>t;

while(t--)

{

cin>>a>>b>>c>>d;

aa=a-c-1;

bb=b-d-1;

ans=aa^bb^c^d;

if(ans==0)

cout<<"Hansel\n";

else

cout<<"Gretel\n";

}

return 0;

}

11716

Asif NaeemJuly 22, 2015

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>

using namespace std;

int main()
{
	int t,l,m;
	string str;
	cin>>t;
	getchar();

	while(t--)
	{
		char gr[105][105];
		getline(cin,str);
		l=str.size();
		m=sqrt(l);
		if(m*m!=l)
		{
			cout<<"INVALID\n";
		}
		else
		{
			int k=0;
			for(int i=0;i<m;i++)
			{
				for(int j=0;j<m;j++)
				{
					gr[i][j]=str[k];
					k+=1;
				}
			}

			for(int i=0;i<m;i++)
			{
				for(int j=0;j<m;j++)
					cout<<gr[j][i];
			}
			cout<<"\n";
		}
	}
	return 0;
}

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <string>

using namespace std;

int main()

{

int t,l,m;

string str;

cin>>t;

getchar();

while(t--)

{

char gr[105][105];

getline(cin,str);

l=str.size();

m=sqrt(l);

if(m*m!=l)

{

cout<<"INVALID\n";

}

else

{

int k=0;

for(int i=0;i<m;i++)

{

for(int j=0;j<m;j++)

{

gr[i][j]=str[k];

k+=1;

}

for(int i=0;i<m;i++)

{

for(int j=0;j<m;j++)

cout<<gr[j][i];

}

cout<<"\n";

}

return 0;

}

Month: July 2015

11466

11369

11059

10714

10533

10784

644

12293

11311

11716

Archives

Categories