#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; } } } }
Month: December 2015
13032
#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;
11008
#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;
11003
#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++) {
11002
#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;
11040
#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]+
10911
#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
10065
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
10359
#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
10918
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 3×1 for(int i=2;i<35;i++) { f[i]=f[i-2]+2*g[i-1];//if last column are 3 of (2×1) OR one vertical 2×1(and removing that will leave one missing cornered ractngle of 2