August 2015 – Live with passion

11909

Asif NaeemAugust 23, 2015

#include <iostream>
#include <cmath>
#include <cstdio>

#define PI acos(-1)
using namespace std;
//using the formulae a/sin A = b/sin B = c/sin C
int main()
{
	double L,W,H,angle;
	double changed_hight,res,changed_base,empty_area;
	while(scanf("%lf%lf%lf%lf",&L,&W,&H,&angle)!=EOF)
	{
		changed_hight= sin(angle*PI/180)*L/sin((90-angle)*PI/180);

		if(angle==0)
		{
			printf("%.3lf mL\n",L*W*H);
		}
		else if(angle==90)
		{
			printf("%.3lf mL\n",0);
		}
		else if(changed_hight<=H)
		{
			empty_area=changed_hight*L*W/2;
			res = L*W*H-empty_area;
			printf("%.3lf mL\n",res);
		}
		else
		{
			changed_base = H * sin((90-angle)*PI/180)/sin(angle*PI/180);
			res = H*changed_base*W/2;
			printf("%.3lf mL\n",res);
		}
	}
	return 0;
}

#include <iostream>

#include <cmath>

#include <cstdio>

#define PI acos(-1)

using namespace std;

//using the formulae a/sin A = b/sin B = c/sin C

int main()

{

double L,W,H,angle;

double changed_hight,res,changed_base,empty_area;

while(scanf("%lf%lf%lf%lf",&L,&W,&H,&angle)!=EOF)

{

changed_hight= sin(angle*PI/180)*L/sin((90-angle)*PI/180);

if(angle==0)

{

printf("%.3lf mL\n",L*W*H);

}

else if(angle==90)

{

printf("%.3lf mL\n",0);

}

else if(changed_hight<=H)

{

empty_area=changed_hight*L*W/2;

res = L*W*H-empty_area;

printf("%.3lf mL\n",res);

}

else

{

changed_base = H * sin((90-angle)*PI/180)/sin(angle*PI/180);

res = H*changed_base*W/2;

printf("%.3lf mL\n",res);

}

return 0;

}

1208

Asif NaeemAugust 23, 2015

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

using namespace std;

struct Edge{
	int source,destination,weight;
};
//to keep track of parent and rank of union find
struct subset{
	int parent;
	int rank;
};
bool graph[100][100];
vector<Edge> edges;
subset* subsets;

bool cmp(Edge a,Edge b)
{
	return a.weight<b.weight;
}

int find(int node)
{
	if(subsets[node].parent!=node)
		return find(subsets[node].parent);
	return subsets[node].parent;
}

void Union(int x,int y)
{
	int xroot = find(x);
	int yroot = find(y);

	if(subsets[xroot].rank<subsets[yroot].rank)
		subsets[xroot].parent=yroot;
	else if(subsets[yroot].rank<subsets[xroot].rank)
		subsets[yroot].parent=xroot;
	else
	{
		subsets[yroot].parent=xroot;
		subsets[xroot].rank+=1;
	}

}
int main()
{
	int t,no_Of_Vertices,a;
	int counter,kase=1;
	stringstream ss;
	string s;
	Edge tEdge;
	Edge result[100];

	cin>>t;
	getchar();
	while(t--)
	{
		cin>>no_Of_Vertices;
		getchar();
		subsets = (subset*)malloc(sizeof(subset)*no_Of_Vertices);
		memset(graph,0,sizeof(graph));
		edges.clear();
		counter=0;
		for(int I=0;I<no_Of_Vertices;I++)
		{
			getline(cin,s);
			ss.clear();
			ss<<s;
			for(int K=0;K<no_Of_Vertices;K++)
			{
				ss>>a;
				if(ss.peek()==',')
					ss.ignore();
				if(a)
				{
					if(graph[I][K]==0)
					{
						graph[I][K]=graph[K][I]=1;
						tEdge.source=I;
						tEdge.destination=K;
						tEdge.weight=a;
						edges.push_back(tEdge);
					}
				}
			}
		}

		sort(edges.begin(),edges.end(),cmp);
		for(int I=0;I<no_Of_Vertices;I++)
		{
			subsets[I].parent=I;
			subsets[I].rank=0;
		}
		int i=0;
		while(counter<no_Of_Vertices-1)
		{
			tEdge = edges[i++];

			int x = find(tEdge.source);
			int y = find(tEdge.destination);

			if(x!=y)
			{
				result[counter++]=tEdge;
				Union(x,y);
			}
		}
		cout<<"Case "<<kase++<<":\n";
		char ch='A';
		for(int i=0;i<counter;i++)
		cout<<char(ch+result[i].source)<<"-"<<char(ch+result[i].destination)<<" "<<result[i].weight<<"\n";
	}

	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

#include <iostream>

#include <vector>

#include <cstdio>

#include <cstring>

#include <string>

#include <sstream>

#include <algorithm>

using namespace std;

struct Edge{

int source,destination,weight;

};

//to keep track of parent and rank of union find

struct subset{

int parent;

int rank;

};

bool graph[100][100];

vector<Edge> edges;

subset* subsets;

bool cmp(Edge a,Edge b)

{

return a.weight<b.weight;

}

int find(int node)

{

if(subsets[node].parent!=node)

return find(subsets[node].parent);

return subsets[node].parent;

}

void Union(int x,int y)

{

int xroot = find(x);

int yroot = find(y);

if(subsets[xroot].rank<subsets[yroot].rank)

subsets[xroot].parent=yroot;

else if(subsets[yroot].rank<subsets[xroot].rank)

subsets[yroot].parent=xroot;

else

{

subsets[yroot].parent=xroot;

subsets[xroot].rank+=1;

}

int main()

{

int t,no_Of_Vertices,a;

int counter,kase=1;

stringstream ss;

string s;

Edge tEdge;

Edge result[100];

cin>>t;

getchar();

while(t--)

{

cin>>no_Of_Vertices;

getchar();

subsets = (subset*)malloc(sizeof(subset)*no_Of_Vertices);

memset(graph,0,sizeof(graph));

edges.clear();

counter=0;

for(int I=0;I<no_Of_Vertices;I++)

{

getline(cin,s);

ss.clear();

ss<<s;

for(int K=0;K<no_Of_Vertices;K++)

{

ss>>a;

if(ss.peek()==',')

ss.ignore();

if(a)

{

if(graph[I][K]==0)

{

graph[I][K]=graph[K][I]=1;

tEdge.source=I;

tEdge.destination=K;

tEdge.weight=a;

edges.push_back(tEdge);

}

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

for(int I=0;I<no_Of_Vertices;I++)

{

subsets[I].parent=I;

subsets[I].rank=0;

}

int i=0;

while(counter<no_Of_Vertices-1)

{

tEdge = edges[i++];

int x = find(tEdge.source);

int y = find(tEdge.destination);

if(x!=y)

{

result[counter++]=tEdge;

Union(x,y);

}

cout<<"Case "<<kase++<<":\n";

char ch='A';

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

cout<<char(ch+result[i].source)<<"-"<<char(ch+result[i].destination)<<" "<<result[i].weight<<"\n";

}

return 0;

}

To get accepted I had to use PI = acos(-1). Lets assume X = middle portion; Y = dotted region; Z = stripped region; Three independent equations are: X+ 4*Y + 4*Z = a*a……………………………………………….(1) Y + 2*Z = a*a – PI*a*a/4………………………………………..(2) X/2 + Y + Z/2 = (PI*a*a)/4 – ΔPAR………………………..(3)

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

#define PI acos(-1)
#define ll long long

#define THIRD (12-2*PI-3*sqrt(3))/12 //0.0433886732
#define SECOND (PI+6*sqrt(3)-12)/12 //0.12782449020255

using namespace std;

int main()
{
	double a,b,c,d;
	//cout<<THIRD<<"\n";
	while(scanf("%lf",&a)!=EOF)
	{
		b = 4*SECOND*a*a;
		c = 4*THIRD*a*a;
		d = a*a - b - c;
		printf("%.3lf %.3lf %.3lf\n",d,b,c);
	}
	return 0;
}

#include <iostream>

#include <cstdio>

#include <cstring>

#include <vector>

#include <cmath>

#include <cstdlib>

#define PI acos(-1)

#define ll long long

#define THIRD (12-2*PI-3*sqrt(3))/12 //0.0433886732

#define SECOND (PI+6*sqrt(3)-12)/12 //0.12782449020255

using namespace std;

int main()

{

double a,b,c,d;

//cout<<THIRD<<"\n";

while(scanf("%lf",&a)!=EOF)

{

b = 4*SECOND*a*a;

c = 4*THIRD*a*a;

d = a*a - b - c;

printf("%.3lf %.3lf %.3lf\n",d,b,c);

}

return 0;

}

12779

Asif NaeemAugust 20, 2015

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

using namespace std;

#define eps 1e-6
#define MX  1000000000
#define ll long long
struct POINT{int x,y;};

long long gcd(ll a,ll b)
{
	if(a%b==0)
	return b;
	else
	return gcd(b,a%b);
}

POINT pp[4];


bool find_perp_distance(POINT u,POINT v,POINT s,ll &B,ll &C,double &val)
{
	//form equation of st line uv (ax+by+c=0)
	double a,b,c,r;
	a = u.y-v.y;//y1-y2
	b = v.x-u.x;
	c = -(a*u.x+b*u.y);
	//distance from a point d = (a*x+b*y+c)/sqrt(a*a+b*b)
	r = fabs(a*s.x+b*s.y+c)/sqrt(a*a+b*b);

	//here if v can be considered as the edge of the square or diameter of the inscribed circle
	//so the area of the circle = d*d/4 * PI
	//cout<<r<<"\n";
	if(r<eps)
		return 0;
	if(r < val)
	{
		B=a*s.x+b*s.y+c;
		B=B*B;
		C=a*a+b*b;
		val=r;
	}
	return 1;
}
int main()
{
	int a,ans,b;
	double compare;
	ll B,C,g;
	bool f1,f2;
	while(cin>>a)
	{
		cin>>b;
		pp[0].x=a;
		pp[0].y=b;
		for(int i=1;i<=3;i++)
		{
			cin>>a>>b;
			pp[i].x=a;pp[i].y=b;
		}
		ans=0;
		for(int i=0;i<=3;i++)
		{
			ans+=(pp[i].x+pp[i].y);
		}

		if(ans==0)
		break;
		compare = MX;
		//find perpendicular distance from first point to the st line of 2nd and 3rd point
		f1 = find_perp_distance(pp[0],pp[1],pp[2],B,C,compare);
		f2 = find_perp_distance(pp[1],pp[2],pp[3],B,C,compare);

		if(f1*f2==0)
		{
			cout<<-1<<"\n";
			continue;
		}
		C*=4;
		g = gcd(B,C);
		B/=g;
		C/=g;
		cout<<"("<<B<<"/"<<C<<")*pi\n";
	}

	return 0;
}

#include <stdio.h>

#include <iostream>

#include <math.h>

using namespace std;

#define eps 1e-6

#define MX 1000000000

#define ll long long

struct POINT{int x,y;};

long long gcd(ll a,ll b)

{

if(a%b==0)

return b;

else

return gcd(b,a%b);

}

POINT pp[4];

bool find_perp_distance(POINT u,POINT v,POINT s,ll &B,ll &C,double &val)

{

//form equation of st line uv (ax+by+c=0)

double a,b,c,r;

a = u.y-v.y;//y1-y2

b = v.x-u.x;

c = -(a*u.x+b*u.y);

//distance from a point d = (a*x+b*y+c)/sqrt(a*a+b*b)

r = fabs(a*s.x+b*s.y+c)/sqrt(a*a+b*b);

//here if v can be considered as the edge of the square or diameter of the inscribed circle

//so the area of the circle = d*d/4 * PI

//cout<<r<<"\n";

if(r<eps)

return 0;

if(r < val)

{

B=a*s.x+b*s.y+c;

B=B*B;

C=a*a+b*b;

val=r;

}

return 1;

}

int main()

{

int a,ans,b;

double compare;

ll B,C,g;

bool f1,f2;

while(cin>>a)

{

cin>>b;

pp[0].x=a;

pp[0].y=b;

for(int i=1;i<=3;i++)

{

cin>>a>>b;

pp[i].x=a;pp[i].y=b;

}

ans=0;

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

{

ans+=(pp[i].x+pp[i].y);

}

if(ans==0)

break;

compare = MX;

//find perpendicular distance from first point to the st line of 2nd and 3rd point

f1 = find_perp_distance(pp[0],pp[1],pp[2],B,C,compare);

f2 = find_perp_distance(pp[1],pp[2],pp[3],B,C,compare);

if(f1*f2==0)

{

cout<<-1<<"\n";

continue;

}

C*=4;

g = gcd(B,C);

B/=g;

C/=g;

cout<<"("<<B<<"/"<<C<<")*pi\n";

}

return 0;

}

11824

Asif NaeemAugust 18, 2015

#include <iostream>
#include <cstdio>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <algorithm>

#define LMT 5000000
#define ll long long

using namespace std;

bool cmp(int a,int b)
{
	return a>b;
}

ll _pow(int a,int p)
{
	ll ans=1;
	while(p--)
	{
		ans=ans*a;
		if(ans>=LMT)
		return LMT;
	}
	return ans;
}
int main()
{
	vector<int> vb;
	int t,n,k;
	ll total,r;
	scanf("%d",&t);
	bool exceed;
	while(t--)
	{
		vb.clear();
		total=0;
		while(scanf("%d",&n)&&n)
		{
			vb.push_back(n);
		}
		sort(vb.begin(),vb.end(),cmp);
		exceed=0;
		for(int i=0;i<vb.size();i++)
		{
			r =_pow(vb[i],i+1);
			r*=2;
			if(r>LMT)
			{
				exceed=1;break;
			}
			total+=r;
			if(total>LMT)
			{
				exceed=1;break;
			}
		}
		if(exceed)
		printf("Too expensive\n");
		else
		printf("%lld\n",total);
	}
	return 0;
}

#include <iostream>

#include <cstdio>

#include <cstring>

#include <vector>

#include <cmath>

#include <cstdlib>

#include <algorithm>

#define LMT 5000000

#define ll long long

using namespace std;

bool cmp(int a,int b)

{

return a>b;

}

ll _pow(int a,int p)

{

ll ans=1;

while(p--)

{

ans=ans*a;

if(ans>=LMT)

return LMT;

}

return ans;

}

int main()

{

vector<int> vb;

int t,n,k;

ll total,r;

scanf("%d",&t);

bool exceed;

while(t--)

{

vb.clear();

total=0;

while(scanf("%d",&n)&&n)

{

vb.push_back(n);

}

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

exceed=0;

for(int i=0;i<vb.size();i++)

{

r =_pow(vb[i],i+1);

r*=2;

if(r>LMT)

{

exceed=1;break;

}

total+=r;

if(total>LMT)

{

exceed=1;break;

}

if(exceed)

printf("Too expensive\n");

else

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

}

return 0;

}

10188

Asif NaeemAugust 14, 2015

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


using namespace std;
string s,ans;
string str,str1;
int n,m;
bool accept()
{
	if(n!=m)
		return 0;
	if(str==str1)
		return 1;
	return 0;
}

bool presentation()
{
	string num1="",num2="";
	for(int i=0;i<str.size();i++)
	{
		if(isdigit(str[i]))
		num1.append(1u,str[i]);
	}
	for(int i=0;i<str1.size();i++)
	{
		if(isdigit(str1[i]))
		num2.append(1u,str1[i]);
	}
	if(num1==num2)
	return 1;
	return 0;
}
int main()
{
	int kase=1;
	char c;
	while(scanf("%d",&n),n)
	{
		getchar();
		str="";str1="";
		for(int i=0;i<n;i++)
		{
			getline(cin,s);
			str.append(s);
		}
		scanf("%d",&m);
		getchar();
		for(int i=0;i<m;i++)
		{
			getline(cin,ans);
			str1.append(ans);
		}

		if(accept())
			 printf ("Run #%d: Accepted\n", kase++);
		else if(presentation())
			printf ("Run #%d: Presentation Error\n",kase++);
		else
			printf ("Run #%d: Wrong Answer\n",kase++);
	}
	return 0;
}

#include <iostream>

#include <cstdio>

#include <cstring>

#include <string>

#include <vector>

#include <cmath>

#include <cstdlib>

using namespace std;

string s,ans;

string str,str1;

int n,m;

bool accept()

{

if(n!=m)

return 0;

if(str==str1)

return 1;

return 0;

}

bool presentation()

{

string num1="",num2="";

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

{

if(isdigit(str[i]))

num1.append(1u,str[i]);

}

for(int i=0;i<str1.size();i++)

{

if(isdigit(str1[i]))

num2.append(1u,str1[i]);

}

if(num1==num2)

return 1;

return 0;

}

int main()

{

int kase=1;

char c;

while(scanf("%d",&n),n)

{

getchar();

str="";str1="";

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

{

getline(cin,s);

str.append(s);

}

scanf("%d",&m);

getchar();

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

{

getline(cin,ans);

str1.append(ans);

}

if(accept())

printf ("Run #%d: Accepted\n", kase++);

else if(presentation())

printf ("Run #%d: Presentation Error\n",kase++);

else

printf ("Run #%d: Wrong Answer\n",kase++);

}

return 0;

}

11917

Asif NaeemAugust 12, 2015

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

using namespace std;

int main()
{
	int t,n,d,D;
	scanf("%d",&t);
	string sub,s;
	int kase=1,res;
	while(t--)
	{
		scanf("%d",&n);
		map<string,int> mp;
		for(int i=1;i<=n;i++)
		{
			cin>>s;
			scanf("%d",&d);
			mp[s]=d;
		}
		scanf("%d",&D);
		cin>>sub;
		res = mp[sub];
		if(res==0 || res>(D+5))
		printf("Case %d: Do your own homework!\n",kase++);
		else if(res>D && res<=(D+5))
		printf("Case %d: Late\n",kase++);
		else if(res && res<=D)
		printf("Case %d: Yesss\n",kase++);
	}
	return 0;
}

#include <iostream>

#include <cstdio>

#include <sstream>

#include <string>

#include <map>

using namespace std;

int main()

{

int t,n,d,D;

scanf("%d",&t);

string sub,s;

int kase=1,res;

while(t--)

{

scanf("%d",&n);

map<string,int> mp;

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

{

cin>>s;

scanf("%d",&d);

mp[s]=d;

}

scanf("%d",&D);

cin>>sub;

res = mp[sub];

if(res==0 || res>(D+5))

printf("Case %d: Do your own homework!\n",kase++);

else if(res>D && res<=(D+5))

printf("Case %d: Late\n",kase++);

else if(res && res<=D)

printf("Case %d: Yesss\n",kase++);

}

return 0;

}

1282

Asif NaeemAugust 12, 2015

Theory: The idea for solving the problem is: for any fibonacci word F(n) = F(n-1)+F(n-2) = F(n-2)+F(n-3)+F(n-2), so word F(n-2) is both suffix and prefix of word F(n). After observing a little more we can find that F(n-2) will always be the prefix for all the rest of the fibonacci word.Now find the minimum F(n-3)

Continue Reading “1282” →

11475

Asif NaeemAugust 11, 2015

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

#define INF 1000000
#define ll long long

using namespace std;

int main()
{
	char s[100005];
	string str;
	int len,i,j,idx;
	int *failureFunc;

	while(scanf("%s",s)!=EOF)
	{
		len=strlen(s);
		str="";
		for(int y=len-1;y>=0;y--)
		str.append(1u,s[y]);

		failureFunc=(int *)malloc(sizeof(int)*len);

		failureFunc[0]=0;
		i=0;
		j=1;
		while(j<len)
		{
			if(str[i]==str[j])
			{
				i+=1;
				failureFunc[j]=i;
				j+=1;
			}
			else
			{
				if(i)
				{
					i=failureFunc[i-1];
				}
				else
				{
					failureFunc[j]=0;
					j+=1;
				}
			}
		}

		//match s and str(asume as pattern)
		i=0;j=0;
		int mx_idx=-1;
		while(i<len)
		{
			if(s[i]==str[j])
			{
				i+=1;j+=1;
				mx_idx=j;
			}
			else
			{
				if(j)
				j=failureFunc[j-1];
				else
				i+=1;
			}
		}

		string res="";
		for(int y=j;y<str.size();y++)
		res.append(1u,str[y]);

		printf("%s",s);
		cout<<res<<"\n";
	}
	return 0;
}

#include <iostream>

#include <cstdio>

#include <cstring>

#include <vector>

#include <cmath>

#include <cstdlib>

#define INF 1000000

#define ll long long

using namespace std;

int main()

{

char s[100005];

string str;

int len,i,j,idx;

int *failureFunc;

while(scanf("%s",s)!=EOF)

{

len=strlen(s);

str="";

for(int y=len-1;y>=0;y--)

str.append(1u,s[y]);

failureFunc=(int *)malloc(sizeof(int)*len);

failureFunc[0]=0;

i=0;

j=1;

while(j<len)

{

if(str[i]==str[j])

{

i+=1;

failureFunc[j]=i;

j+=1;

}

else

{

if(i)

{

i=failureFunc[i-1];

}

else

{

failureFunc[j]=0;

j+=1;

}

//match s and str(asume as pattern)

i=0;j=0;

int mx_idx=-1;

while(i<len)

{

if(s[i]==str[j])

{

i+=1;j+=1;

mx_idx=j;

}

else

{

if(j)

j=failureFunc[j-1];

else

i+=1;

}

string res="";

for(int y=j;y<str.size();y++)

res.append(1u,str[y]);

printf("%s",s);

cout<<res<<"\n";

}

return 0;

}

Month: August 2015

11909

1208

10209

12779

11824

10188

11917

1282

11475

Archives

Categories