#include <iostream> #include <cstdio> #include <sstream> #include <string> #include <algorithm> #include <cstring> using namespace std; string str; struct node{ int fst; int ed; int idx; }arr[1010]; int L[17][1010]; int RANK[1010]; int lcp[1010]; int FoundAtIndex; int cnt; string resStr; bool cmp(node a,node b) { return (a.fst==b.fst?(a.ed<b.ed?1:0):(a.fst<b.fst?1:0)); } void suffixArray() { for(int i=0;i<str.size();i++) L[0][i]=str[i]-'A'; int stp=1; for(int
Author: Asif Naeem
11022
This is a dp problem where kmp algorithm(specially prefix function) is used to solve the problem. If a string is multiple of a repeated string then the difference between the string length and last index of the prefix table indicates the minimal length of the repeated string. A brief and nice discussion is available here . #include
10298
#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; } } } }
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