Posts

Spoj FINDSR - Find String Roots Solution

 #include<bits/stdc++.h>  using namespace std;  void arraycal(string pat, int M, int  lps[])   {     int len = 0;      lps[0] = 0;        int i = 1;     while (i < M)      {          if (pat[i] == pat[len])           {             len++;             lps[i] = len;             i++;          }         else          {            if (len != 0)             {                 len = lps[len-1];                }             else             {                 lps[i] = 0;                 i++;             }         }     } } int main() {  string s;  cin>>s;  while(s!="*") {  int m=s.size(),i;   int lps[m];   arraycal(s,m,lps);   int x= m-lps[m-1];   if(m%x==0)      cout<<m/x<<"\n";   else cout<<"1"<<"\n";    cin>>s;   }  return 0; }     
Post a Comment
Read more

Spoj EDIST - Edit distance Solution

#include<bits/stdc++.h> using namespace std; int main() {  int t,i,j;  cin>>t;  while(t--) {  string a,b;    cin>>a>>b;  int m= a.size();  int n=b.size();  int ans[m+1][n+1];  for(i=0;i<=m;i++)    ans[0][i]=i;  for(j=0;j<=n;j++)    ans[j][0]=j;  for(i=1;i<=m;i++)  {    for(j=1;j<=n;j++)   {     if(a[i-1]==b[j-1])           ans[i][j]=ans[i-1][j-1];              else        ans[i][j]=1+min(ans[i-1][j-1],min(ans[i-1][j],ans[i][j-1]));    }  } cout<<ans[m][n]<<"\n"; } return 0; }    
Post a Comment
Read more

Spoj CLOPPAIR Solution

This is the solution for spoj Closest Point Pair  #include<bits/stdc++.h>  using namespace std;  #define mn 9999999999.9  struct point  {       long double x,y;       int index;  };  point makepoint(double a,double b,int i) {       point temp;     temp.x=a;temp.y=b;temp.index=i;       return temp; }        double dist(point p1,point p2)  {      return sqrt((p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y));  }  bool compareX(point a,point b) {     return a.x < b.x; } bool compareY(point a,point b) {     return a.y < b.y; }  int indexa,indexb; double ans=999999999; double bruteforce(point p[],int n) {   double d=mn;  for( int i=0;i<n;i++)  {    for(int j=i+1;j<n;j++)   {      double dtemp=dist(p[i],p[j]);         if(dtemp<d)       {          d=dtemp;          if(d < ans)          {            ans=d;            indexa= p[i].index;      
1 comment
Read more

Spoj NDIV Solution

                            This is the solution for spoj n-divisors        #include<bits/stdc++.h>     using namespace std;   int mx=32000;        vector<int> prime;     void sieve()  {    int isprime[mx],i,j;        for(i=0;i<=mx;i++)        isprime[i]=1;         isprime[0]=0;        isprime[1]=0;       for(i=4;i<=mx;i+=2)       isprime[i]=0;   for(i=3;i*i<=mx;i+=2)   {      if(isprime[i])      {        for(j=i*i;j<=mx;j+=i*2)             isprime[j]=0;      }   }     for(i=2;i<=mx;i++)    {       if(isprime[i]==1)                prime.push_back(i);    } }   int main() {    sieve();     int a,b,c,i,j,fans=0;     cin>>a>>b>>c;      for(i=a;i<=b;i++)  {    int n=i;       int ans=1;      int k=0;      for(j=prime[k]; j*j<=n ; j=prime[++k])   {      int cnt=0;        while(n%j==0)       {          n/=j;      
Post a Comment
Read more

FRIENDS OF FRIENDS SPOJ SOLUTION

 "FACEFRND" SPOJ SOLUTION #include<bits/stdc++.h> #include<set> #include<vector> using namespace std; int main() {  set<int> s;  vector<int> v;  int n,i;  cin>>n;  while(n--) {  int x;  cin>>x;  v.push_back(x);  int m;  cin>>m;  while(m--)   {   cin>>x;   s.insert(x);   }  } for(i=0;i<v.size();i++) s.erase(v[i]); cout<<s.size(); return 0; }
Post a Comment
Read more

ADDING REVERSED NUMBERS SPOJ SOLUTION

*/ "ADDREV" SPOJ SOLUTION */ #include<bits/stdc++.h> using namespace std; int rev(int x) {  int y=0,z;  while(x>=1)  {  z=x%10;  y=y*10+z;  x/=10; } return (y); } int main() {int t; cin>>t; while(t--) { int x,y,z; cin>>x>>y; z=rev(x)+rev(y); cout<<rev(z)<<"\n"; } return 0; }
Post a Comment
Read more

RECTANGLES SPOJ SOLUTION

*/ "AE00" SPOJ SOLUTION */ #include<bits/stdc++.h> using namespace std; int main() { int i,j,c=0; int n; cin>>n; for(i=2;i<=sqrt(n);i++)  {for(j=i;(j*i)<=n;j++)       c++;} cout<<n+c; return 0; }
Post a Comment
Read more