December 2015 – Live with passion

10298

Asif NaeemDecember 31, 2015

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

using namespace std;

int lps[1000005];

void prefixArray(string s)
{
	memset(lps,0,sizeof(lps));
	int len=0;//length of prev longest prefix
	int i=1;
	lps[0]=0;
	int length = s.size();
	while(i<length)
	{
		if(s[i]==s[len])
		{
			len+=1;
			lps[i]=len;
			i+=1;
		}
		else
		{
			if(len!=0)
			{
				len = lps[len-1];
			}
			else
			{
				lps[i]=0;
				i+=1;
			}
		}
	}
}
int main()
{
	string s;
	int lastval,minimal_length_of_repeated_string;
	while(cin>>s)
	{
		if(s==".")
		break;
		prefixArray(s);
		lastval = lps[s.size()-1];
		minimal_length_of_repeated_string = s.size()-lastval;
		if(s.size()%minimal_length_of_repeated_string==0)
		printf("%d\n",s.size()/minimal_length_of_repeated_string);
		else
		printf("1\n");
	}
	return 0;
}

#include <iostream>

#include <cstring>

#include <cstdio>

#include <string>

using namespace std;

int lps[1000005];

void prefixArray(string s)

{

memset(lps,0,sizeof(lps));

int len=0;//length of prev longest prefix

int i=1;

lps[0]=0;

int length = s.size();

while(i<length)

{

if(s[i]==s[len])

{

len+=1;

lps[i]=len;

i+=1;

}

else

{

if(len!=0)

{

len = lps[len-1];

}

else

{

lps[i]=0;

i+=1;

}

int main()

{

string s;

int lastval,minimal_length_of_repeated_string;

while(cin>>s)

{

if(s==".")

break;

prefixArray(s);

lastval = lps[s.size()-1];

minimal_length_of_repeated_string = s.size()-lastval;

if(s.size()%minimal_length_of_repeated_string==0)

printf("%d\n",s.size()/minimal_length_of_repeated_string);

else

printf("1\n");

}

return 0;

}

13032

Asif NaeemDecember 28, 2015

#include <iostream>
#include <cstdio>
#include <cmath>
#include <climits>
#include <inttypes.h>
#include <cstring>
#include <string>
#include <algorithm>

#define INF 1000000
#define _MOD 1000000007
#define ul unsigned long long

using namespace std;

int arr[105];
unsigned long long ncr[105][105];
/*
void init()
{
	ncr[1][1]=1;
	for(int i=2;i<105;i++)
	{
		ncr[i][1]=i;
		for(int j=2;j<=i;j++)
		{
			ncr[i][j] = ( (ncr[i-1][j-1]%_MOD) + (ncr[i-1][j]%_MOD) )%_MOD;
		}
	}
}
*/
int main()
{
	int t,kase=1,n;
	ul ans;
	scanf("%d",&t);
	//init();
	while(t--)
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&arr[i]);
		}
		sort(arr+1,arr+n+1);
		ans = 1;
		for(int i=1;i<=n;i++)
		{
			if(arr[i]<i)
			{
				ans = 0;
				break;
			}
			ans = (ans*(arr[i]-i+1))%_MOD;
		}
		printf("Case %d: %llu\n",kase++,ans);
	}
	return 0;
}

#include <iostream>

#include <cstdio>

#include <cmath>

#include <climits>

#include <inttypes.h>

#include <cstring>

#include <string>

#include <algorithm>

#define INF 1000000

#define _MOD 1000000007

#define ul unsigned long long

using namespace std;

int arr[105];

unsigned long long ncr[105][105];

void init()

{

ncr[1][1]=1;

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

{

ncr[i][1]=i;

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

{

ncr[i][j] = ( (ncr[i-1][j-1]%_MOD) + (ncr[i-1][j]%_MOD) )%_MOD;

}

int main()

{

int t,kase=1,n;

ul ans;

scanf("%d",&t);

//init();

while(t--)

{

scanf("%d",&n);

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

{

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

}

sort(arr+1,arr+n+1);

ans = 1;

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

{

if(arr[i]<i)

{

ans = 0;

break;

}

ans = (ans*(arr[i]-i+1))%_MOD;

}

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

}

return 0;

}

11008

Asif NaeemDecember 28, 2015

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

#define INF 1000000

using namespace std;

int X[20],Y[20];
int totalpointsOfline[20][20];
int m,n,restTrees;
int dp[66000];

void init()
{
	memset(totalpointsOfline,0,sizeof(totalpointsOfline));
	for(int i=0;i<n;i++)
	{
		for(int j=i+1;j<n;j++)
		{
			for(int k=n-1;k>=0;k--)
			{
				totalpointsOfline[i][j]<<=1;
				if( (Y[j]-Y[i])*(X[k]-X[i])==(Y[k]-Y[i])*(X[j]-X[i]))
				totalpointsOfline[i][j]+=1;
			}
		}
	}
	memset(dp,-1,sizeof(dp));
}

int _min(int a,int b)
{
	return a<b?a:b;
}

int DP(int totalTrees)
{
	if(dp[totalTrees]!=-1)
	return dp[totalTrees];

	int cnt=0;
	for(int i=0;i<n;i++)
	{
		if(totalTrees&(1<<i))
		cnt+=1;
	}
	if(cnt<=restTrees)
	return dp[totalTrees]=0;

	if(cnt==1)
	return dp[totalTrees]=1;

	int MX = INF;
	for(int i=0;i<n;i++)
	{
		if(totalTrees&(1<<i))
		{
			for(int j=i+1;j<n;j++)
			{
				if(totalTrees&(1<<j))
				{
					MX = _min(MX,DP( totalTrees&(~totalpointsOfline[i][j]) )+1);
				}
			}
		}
	}
	return dp[totalTrees]=MX;
}
int main()
{
	int t,kase=1;
	int idx,a,b;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&m);
		init();
		for(int i=0;i<n;i++)
		{
			scanf("%d%d",&X[i],&Y[i]);
		}
		init();
		restTrees = n-m;
		printf("Case #%d:\n",kase++);
		printf("%d\n",DP((1<<n)-1));
		if(t)
		printf("\n");
	}
	return 0;
}

#include <iostream>

#include <cstdio>

#include <cmath>

#include <climits>

#include <cstring>

#include <string>

#define INF 1000000

using namespace std;

int X[20],Y[20];

int totalpointsOfline[20][20];

int m,n,restTrees;

int dp[66000];

void init()

{

memset(totalpointsOfline,0,sizeof(totalpointsOfline));

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

{

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

{

for(int k=n-1;k>=0;k--)

{

totalpointsOfline[i][j]<<=1;

if( (Y[j]-Y[i])*(X[k]-X[i])==(Y[k]-Y[i])*(X[j]-X[i]))

totalpointsOfline[i][j]+=1;

}

memset(dp,-1,sizeof(dp));

}

int _min(int a,int b)

{

return a<b?a:b;

}

int DP(int totalTrees)

{

if(dp[totalTrees]!=-1)

return dp[totalTrees];

int cnt=0;

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

{

if(totalTrees&(1<<i))

cnt+=1;

}

if(cnt<=restTrees)

return dp[totalTrees]=0;

if(cnt==1)

return dp[totalTrees]=1;

int MX = INF;

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

{

if(totalTrees&(1<<i))

{

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

{

if(totalTrees&(1<<j))

{

MX = _min(MX,DP( totalTrees&(~totalpointsOfline[i][j]) )+1);

}

return dp[totalTrees]=MX;

}

int main()

{

int t,kase=1;

int idx,a,b;

scanf("%d",&t);

while(t--)

{

scanf("%d%d",&n,&m);

init();

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

{

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

}

init();

restTrees = n-m;

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

printf("%d\n",DP((1<<n)-1));

if(t)

printf("\n");

}

return 0;

}

11003

Asif NaeemDecember 25, 2015

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

using namespace std;

int n;
int dp[1002][3002];
int capacity[1002];
int weight[1002];

void init()
{
	for(int i=0;i<1002;i++)
		for(int j=0;j<3002;j++)
			dp[i][j]=0;
}

int _max(int a,int b)
{
	return a>b?a:b;
}
int _min(int a,int b)
{
	return a<b?a:b;
}
int main()
{
	int idx;
	while(scanf("%d",&n),n)
	{
		init();
		for(int i=1;i<=n;i++)
		{
			scanf("%d%d",&weight[i],&capacity[i]);
			dp[i][capacity[i]]=1;
		}
		for(int i=2;i<=n;i++)
		{
			for(int j=0;j<3002;j++)
			{
				if(j>=weight[i])
				{
					idx = _min(j-weight[i],capacity[i]);
					dp[i][idx]=_max(dp[i][idx],dp[i-1][j]+1);
				}
				dp[i][j]=_max(dp[i][j],dp[i-1][j]);
			}
		}
		int height=0;;
		for(int i=0;i<3002;i++)
		{
			height=_max(height,dp[n][i]);
		}
		cout<<height<<"\n";
	}
	return 0;
}

#include <iostream>

#include <cstdio>

#include <cstring>

#include <string>

using namespace std;

int n;

int dp[1002][3002];

int capacity[1002];

int weight[1002];

void init()

{

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

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

dp[i][j]=0;

}

int _max(int a,int b)

{

return a>b?a:b;

}

int _min(int a,int b)

{

return a<b?a:b;

}

int main()

{

int idx;

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

{

init();

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

{

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

dp[i][capacity[i]]=1;

}

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

{

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

{

if(j>=weight[i])

{

idx = _min(j-weight[i],capacity[i]);

dp[i][idx]=_max(dp[i][idx],dp[i-1][j]+1);

}

dp[i][j]=_max(dp[i][j],dp[i-1][j]);

}

int height=0;;

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

{

height=_max(height,dp[n][i]);

}

cout<<height<<"\n";

}

return 0;

}

11002

Asif NaeemDecember 22, 2015

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

using namespace std;

bool dp[65][65][6005];
int arr[65][65];
int n;

void init()
{
	for(int i=0;i<65;i++)
		for(int j=0;j<65;j++)
		{
			arr[i][j]=0;
			for(int k=0;k<6005;k++)
				dp[i][j][k]=0;
		}
}


int main()
{
	int cnt,tmp,tmp2,val;
	while(scanf("%d",&n),n)
	{
		init();
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=i;j++)
				scanf("%d",&arr[i][j]);
		}
		cnt = n;
		for(int i=n+1;i<=2*n-1;i++)
		{
			cnt-=1;
			for(int j=1;j<=cnt;j++)
			{
				scanf("%d",&arr[i][j]);
			}
		}
		cnt = 0;
		dp[2*n-1][1][ arr[2*n-1][1]+3000 ] = 1;
		for(int i=2*n-1;i>=n+1;i--)
		{
			cnt+=1;
			for(int j=1;j<=cnt;j++)
			{
				for(int k=0;k<6005;k++)
				{
					if(dp[i][j][k]==true)
					{
						tmp = arr[i-1][j];
						val = k+tmp;
						dp[i-1][j][val]=true;
						val = k-tmp;
						dp[i-1][j][val]=true;
						tmp2 = arr[i-1][j+1];
						val = k+tmp2;
						dp[i-1][j+1][val]=true;
						val = k-tmp2;
						dp[i-1][j+1][val]=true;
					}
				}
			}
		}// end of for loop
		cnt=n+1;
		for(int i=n;i>=2;i--)
		{
			cnt-=1;
			for(int j=1;j<=cnt;j++)
			{
				for(int k=0;k<6005;k++)
				{
					if(dp[i][j][k]==true)
					{
						tmp = arr[i-1][j-1];
						tmp2 = arr[i-1][j];
						if(j==1)
						{
							val = k+tmp2;
							dp[i-1][j][val]=true;
							val = k-tmp2;
							dp[i-1][j][val]=true;
						}
						else if(j==cnt)
						{
							val = k+tmp;
							dp[i-1][j-1][val]=true;
							val = k-tmp;
							dp[i-1][j-1][val]=true;
						}
						else
						{
							val = k+tmp;
							dp[i-1][j-1][val]=true;
							val = k-tmp;
							dp[i-1][j-1][val]=true;
							val = k+tmp2;
							dp[i-1][j][val]=true;
							val = k-tmp2;
							dp[i-1][j][val]=true;
						}
					}
				}
			}
		}//end for loop
		int mn = 7000;
		for(int i=3000;i>=0;i--)
		{
			if(dp[1][1][i]==true)
			{
				mn=3000-i;
				break;
			}
		}
		int mx = 7000;
		for(int i=3001;i<6005;i++)
		{
			if(dp[1][1][i]==true)
			{
				mx=i-3000;
				break;
			}
		}
		cout<<(mn<mx?mn:mx)<<"\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

122

123

124

125

126

127

128

129

130

131

132

#include <iostream>

#include <cstdio>

#include <cstring>

#include <vector>

#include <string>

using namespace std;

bool dp[65][65][6005];

int arr[65][65];

int n;

void init()

{

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

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

{

arr[i][j]=0;

for(int k=0;k<6005;k++)

dp[i][j][k]=0;

}

int main()

{

int cnt,tmp,tmp2,val;

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

{

init();

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

{

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

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

}

cnt = n;

for(int i=n+1;i<=2*n-1;i++)

{

cnt-=1;

for(int j=1;j<=cnt;j++)

{

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

}

cnt = 0;

dp[2*n-1][1][ arr[2*n-1][1]+3000 ] = 1;

for(int i=2*n-1;i>=n+1;i--)

{

cnt+=1;

for(int j=1;j<=cnt;j++)

{

for(int k=0;k<6005;k++)

{

if(dp[i][j][k]==true)

{

tmp = arr[i-1][j];

val = k+tmp;

dp[i-1][j][val]=true;

val = k-tmp;

dp[i-1][j][val]=true;

tmp2 = arr[i-1][j+1];

val = k+tmp2;

dp[i-1][j+1][val]=true;

val = k-tmp2;

dp[i-1][j+1][val]=true;

}

}// end of for loop

cnt=n+1;

for(int i=n;i>=2;i--)

{

cnt-=1;

for(int j=1;j<=cnt;j++)

{

for(int k=0;k<6005;k++)

{

if(dp[i][j][k]==true)

{

tmp = arr[i-1][j-1];

tmp2 = arr[i-1][j];

if(j==1)

{

val = k+tmp2;

dp[i-1][j][val]=true;

val = k-tmp2;

dp[i-1][j][val]=true;

}

else if(j==cnt)

{

val = k+tmp;

dp[i-1][j-1][val]=true;

val = k-tmp;

dp[i-1][j-1][val]=true;

}

else

{

val = k+tmp;

dp[i-1][j-1][val]=true;

val = k-tmp;

dp[i-1][j-1][val]=true;

val = k+tmp2;

dp[i-1][j][val]=true;

val = k-tmp2;

dp[i-1][j][val]=true;

}

}//end for loop

int mn = 7000;

for(int i=3000;i>=0;i--)

{

if(dp[1][1][i]==true)

{

mn=3000-i;

break;

}

int mx = 7000;

for(int i=3001;i<6005;i++)

{

if(dp[1][1][i]==true)

{

mx=i-3000;

break;

}

cout<<(mn<mx?mn:mx)<<"\n";

}

return 0;

}

11040

Asif NaeemDecember 21, 2015

#include <iostream>
#include <cstdio>

using namespace std;

int arr[10][10];

void init()
{
	for(int i=1;i<10;i++)
	{
		for(int j=1;j<10;j++)
			arr[i][j]=0;
	}
}
int main()
{
	int t,cnt,tmp;
	scanf("%d",&t);
	while(t--)
	{
		cnt=1;
		init();
		for(int i=9;i>=1;i-=2)
		{
			for(int j=1;j<=cnt;j+=2)
			{
				scanf("%d",&arr[i][j]);
			}
			cnt+=2;
		}
		cnt=7;
		for(int i=3;i<=9;i+=2)
		{
			for(int j=1;j<=cnt;j+=2)
			{
				tmp = arr[i][j];
				arr[i-2][j+1] = (tmp - (arr[i-2][j]+ arr[i-2][j+2]))/2;
			}
			for(int j=1;j<=cnt+1;j++)
			{
				arr[i-1][j]=arr[i-2][j]+arr[i-2][j+1];
			}
			cnt-=2;
		}
		cnt=1;
		for(int i=9;i>=1;i--)
		{
			for(int j=1;j<=cnt;j++)
			{
				printf("%d",arr[i][j]);
				cout<<(j!=cnt?" ":"\n");
			}
			cnt+=1;
		}
	}
	return 0;
}

#include <iostream>

#include <cstdio>

using namespace std;

int arr[10][10];

void init()

{

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

{

for(int j=1;j<10;j++)

arr[i][j]=0;

}

int main()

{

int t,cnt,tmp;

scanf("%d",&t);

while(t--)

{

cnt=1;

init();

for(int i=9;i>=1;i-=2)

{

for(int j=1;j<=cnt;j+=2)

{

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

}

cnt+=2;

}

cnt=7;

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

{

for(int j=1;j<=cnt;j+=2)

{

tmp = arr[i][j];

arr[i-2][j+1] = (tmp - (arr[i-2][j]+ arr[i-2][j+2]))/2;

}

for(int j=1;j<=cnt+1;j++)

{

arr[i-1][j]=arr[i-2][j]+arr[i-2][j+1];

}

cnt-=2;

}

cnt=1;

for(int i=9;i>=1;i--)

{

for(int j=1;j<=cnt;j++)

{

printf("%d",arr[i][j]);

cout<<(j!=cnt?" ":"\n");

}

cnt+=1;

}

return 0;

}

10911

Asif NaeemDecember 21, 2015

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

using namespace std;
struct HOUSE{
	double x,y;
};
string str[20];
HOUSE house[20];
double dp[(1<<16)-1];
double d[20][20];
int finalstate;
int n;

double _min(double a,double b)
{
	return a<b?a:b;
}
double DP(int state)
{
	if(state==finalstate)
	return 0;
	if(dp[state]!=-1)
		return dp[state];
	int rest_state = finalstate-state;
	double val=(1<<20);
	for(int i=0;i<2*n;i++)
	{
		if(rest_state&(1<<i))
		{
			for(int j=i+1;j<2*n;j++)
			{
				if(rest_state&(1<<j))
				{
					val = _min(val,d[i][j]+DP(state|(1<<i)|(1<<j) ));
				}
			}
		}
	}
	return dp[state]=val;
}
int main()
{
	int kase=1;
	while(scanf("%d",&n),n)
	{
		for(int i=0;i<(1<<2*n);i++)
			dp[i]=-1;
		finalstate=(1<<2*n)-1;
		for(int i=0;i<20;i++)
			for(int j=0;j<20;j++)
				d[i][j]=0;
		for(int i=0;i<2*n;i++)
		{
			cin>>str[i];
			scanf("%lf%lf",&house[i].x,&house[i].y);
		}
		for(int i=0;i<2*n-1;i++)
		{
			for(int j=i+1;j<2*n;j++)
			{
				d[i][j] = sqrt( (house[i].x-house[j].x)*(house[i].x-house[j].x) + (house[i].y-house[j].y)*(house[i].y-house[j].y) );
				d[j][i] = d[i][j];
			}
		}
		printf("Case %d: %.2lf\n",kase++,DP(0));
	}
	return 0;
}

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <string>

using namespace std;

struct HOUSE{

double x,y;

};

string str[20];

HOUSE house[20];

double dp[(1<<16)-1];

double d[20][20];

int finalstate;

int n;

double _min(double a,double b)

{

return a<b?a:b;

}

double DP(int state)

{

if(state==finalstate)

return 0;

if(dp[state]!=-1)

return dp[state];

int rest_state = finalstate-state;

double val=(1<<20);

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

{

if(rest_state&(1<<i))

{

for(int j=i+1;j<2*n;j++)

{

if(rest_state&(1<<j))

{

val = _min(val,d[i][j]+DP(state|(1<<i)|(1<<j) ));

}

return dp[state]=val;

}

int main()

{

int kase=1;

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

{

for(int i=0;i<(1<<2*n);i++)

dp[i]=-1;

finalstate=(1<<2*n)-1;

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

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

d[i][j]=0;

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

{

cin>>str[i];

scanf("%lf%lf",&house[i].x,&house[i].y);

}

for(int i=0;i<2*n-1;i++)

{

for(int j=i+1;j<2*n;j++)

{

d[i][j] = sqrt( (house[i].x-house[j].x)*(house[i].x-house[j].x) + (house[i].y-house[j].y)*(house[i].y-house[j].y) );

d[j][i] = d[i][j];

}

printf("Case %d: %.2lf\n",kase++,DP(0));

}

return 0;

}

10065

Asif NaeemDecember 20, 2015

Can read about orientation here Idea comes from the slope comparison.

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

using namespace std;

struct point{
	double x,y;
};
vector<point>pp;
double area(int n,vector<point> arr)
{
	double ans = 0.0;
	for(int i=0;i<n;i++)
	{
		ans += (arr[i].x*arr[(i+1)%n].y - arr[i].y*arr[(i+1)%n].x);
	}
	return fabs(ans/2.0);
}
int checkCross(point p, point q, point r)
{
    int val = (q.y - p.y) * (r.x - q.x) -
              (q.x - p.x) * (r.y - q.y);

    if (val == 0) return 0;  // colinear
    return (val > 0)? 1: 2; // clock or counterclock wise
}

int convexCalc(int n,vector<point> arr)
{
	point tmp;
	pp.clear();
	int leftMost=0;
	for(int i=1;i<n;i++)
	{
		if(arr[i].x<arr[leftMost].x)
		leftMost=i;
	}
	int left=leftMost,j;
	do
	{
		pp.push_back(arr[left]);
		j = (left+1)%n;
		for(int i=0;i<n;i++)
		{
			if( checkCross(arr[left],arr[i],arr[j])==2 )
			j=i;
		}
		left=j;
	}while(leftMost!=left);
	return pp.size();
}

bool cmp(point a,point b)
{
	if(a.x!=b.x)
	return a.x<b.x;
	return a.y<b.y;
}
int main()
{
	int n,kase=1;
	vector<point>arr;
	point tmp;
	double ans,ans2;
	while(scanf("%d",&n),n)
	{
		arr.clear();
		for(int i=0;i<n;i++)
		{
			scanf("%lf%lf",&tmp.x,&tmp.y);
			arr.push_back(tmp);
		}
		ans = area(n,arr);
		int cnt = convexCalc(n,arr);
		ans2 = area(cnt,pp);
		printf("Tile #%d\n",kase++);
		ans = ((ans2-ans)/ans2)*100;
		printf("Wasted Space = %.2lf %%\n\n",ans);
	}
	return 0;
}

#include <iostream>

#include <algorithm>

#include <cstdio>

#include <vector>

#include <cmath>

using namespace std;

struct point{

double x,y;

};

vector<point>pp;

double area(int n,vector<point> arr)

{

double ans = 0.0;

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

{

ans += (arr[i].x*arr[(i+1)%n].y - arr[i].y*arr[(i+1)%n].x);

}

return fabs(ans/2.0);

}

int checkCross(point p, point q, point r)

{

int val = (q.y - p.y) * (r.x - q.x) -

(q.x - p.x) * (r.y - q.y);

if (val == 0) return 0; // colinear

return (val > 0)? 1: 2; // clock or counterclock wise

}

int convexCalc(int n,vector<point> arr)

{

point tmp;

pp.clear();

int leftMost=0;

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

{

if(arr[i].x<arr[leftMost].x)

leftMost=i;

}

int left=leftMost,j;

{

pp.push_back(arr[left]);

j = (left+1)%n;

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

{

if( checkCross(arr[left],arr[i],arr[j])==2 )

j=i;

}

left=j;

}while(leftMost!=left);

return pp.size();

}

bool cmp(point a,point b)

{

if(a.x!=b.x)

return a.x<b.x;

return a.y<b.y;

}

int main()

{

int n,kase=1;

vector<point>arr;

point tmp;

double ans,ans2;

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

{

arr.clear();

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

{

scanf("%lf%lf",&tmp.x,&tmp.y);

arr.push_back(tmp);

}

ans = area(n,arr);

int cnt = convexCalc(n,arr);

ans2 = area(cnt,pp);

printf("Tile #%d\n",kase++);

ans = ((ans2-ans)/ans2)*100;

printf("Wasted Space = %.2lf %%\n\n",ans);

}

return 0;

}

10359

Asif NaeemDecember 20, 2015

#include <iostream>
#include <cstdio>

using namespace std;

int f[260][1000];
int length[260];
void init()
{
	for(int i=0;i<260;i++)
	{
		length[i]=0;
		for(int j=0;j<1000;j++)
			f[i][j]=0;
	}
}
int main()
{
	int n,j,cary,begn;
	init();
	f[0][0]=1;
	f[1][0]=1;
	for(int i=2;i<260;i++)
	{
		cary=0;
		for(j=0;j<1000;j++)
		{
			f[i][j]=(f[i-1][j]+2*f[i-2][j]+cary)%10;
			cary=(f[i-1][j]+2*f[i-2][j]+cary)/10;
		}
		if(cary!=0)
		f[i][j]=cary;
	}
	while(scanf("%d",&n)!=EOF)
	{
		for(int i=999;i>=0;i--)
		{
			if(f[n][i])
			{
				begn=i;
				break;
			}
		}
		for(int i=begn;i>=0;i--)
			printf("%d",f[n][i]);
		printf("\n");
	}
	return 0;
}

#include <iostream>

#include <cstdio>

using namespace std;

int f[260][1000];

int length[260];

void init()

{

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

{

length[i]=0;

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

f[i][j]=0;

}

int main()

{

int n,j,cary,begn;

init();

f[0][0]=1;

f[1][0]=1;

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

{

cary=0;

for(j=0;j<1000;j++)

{

f[i][j]=(f[i-1][j]+2*f[i-2][j]+cary)%10;

cary=(f[i-1][j]+2*f[i-2][j]+cary)/10;

}

if(cary!=0)

f[i][j]=cary;

}

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

{

for(int i=999;i>=0;i--)

{

if(f[n][i])

{

begn=i;

break;

}

for(int i=begn;i>=0;i--)

printf("%d",f[n][i]);

printf("\n");

}

return 0;

}

10918

Asif NaeemDecember 20, 2015

Using DP

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

using namespace std;

int f[35];
int g[35];

int main()
{
	for(int i=0;i<35;i++)
		f[i]=g[i]=0;
	f[0]=1;
	f[1]=0;
	g[0]=0;
	g[1]=1;//one missing cornered rect of size 3x1
	for(int i=2;i<35;i++)
	{
		f[i]=f[i-2]+2*g[i-1];//if last column are 3 of (2x1) OR one vertical 2x1(and removing that will leave one missing cornered ractngle of 2 ways)
		g[i]=f[i-1]+g[i-2];//one missing cornered rectangle can be 1.last one vertical 2x1 and 2. 2 horizontal 2x1 if we remove them wil form another missing cornered rectangle
	}
	int n;
	while(scanf("%d",&n) && n!=-1)
	{
		printf("%d\n",f[n]);
	}
	return 0;
}

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

int f[35];

int g[35];

int main()

{

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

f[i]=g[i]=0;

f[0]=1;

f[1]=0;

g[0]=0;

g[1]=1;//one missing cornered rect of size 3x1

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

{

f[i]=f[i-2]+2*g[i-1];//if last column are 3 of (2x1) OR one vertical 2x1(and removing that will leave one missing cornered ractngle of 2 ways)

g[i]=f[i-1]+g[i-2];//one missing cornered rectangle can be 1.last one vertical 2x1 and 2. 2 horizontal 2x1 if we remove them wil form another missing cornered rectangle

}

int n;

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

{

printf("%d\n",f[n]);

}

return 0;

}

Another way of adhoc suggested in a blog.

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

using namespace std;

int arr[35];

//lets assume if last column are all horizontal tiles of 3 *(2x1), so remove that and this 3*(2x1) can be
// tiled 3 ways ,so total ways for n length is ways[n-2]*3
//if n>=4 then for every term it can be shifted upside down adds two more ways
// so for n>=4
int main()
{
	for(int i=0;i<35;i++)
		arr[i]=0;
	arr[0]=1;

	for(int i=2;i<35;i+=2)
	{
		arr[i]+=3*arr[i-2];
		for(int j=4;j<=i;j+=2)
		{
			arr[i] += 2*arr[i-j];
		}
	}
	int n;
	while(scanf("%d",&n) && n!=-1)
	{
		printf("%d\n",arr[n]);
	}
	return 0;
}

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

int arr[35];

//lets assume if last column are all horizontal tiles of 3 *(2x1), so remove that and this 3*(2x1) can be

// tiled 3 ways ,so total ways for n length is ways[n-2]*3

//if n>=4 then for every term it can be shifted upside down adds two more ways

// so for n>=4

int main()

{

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

arr[i]=0;

arr[0]=1;

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

{

arr[i]+=3*arr[i-2];

for(int j=4;j<=i;j+=2)

{

arr[i] += 2*arr[i-j];

}

int n;

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

{

printf("%d\n",arr[n]);

}

return 0;

}

Month: December 2015

10298

13032

11008

11003

11002

11040

10911

10065

10359

10918

Archives

Categories