UVA 392 - Polynomial Showdown

#include<stdio.h>
#include<string.h>
#include<math.h>
int main()
{
    long a[10]={0};
    while(~scanf("%ld",&a[8]))
    {
        long i,p,p1=0;
        for(i=7;i>=0;i--)
        scanf("%ld",&a[i]);
        for(i=8;i>=0;i--)
        {
            if(a[i]!=0)
            {
                if(p1==1)
                printf(" ");
                if(i>1)
                {
                    if(a[i]==1)
                    {
                        if(p1==1)
                        printf("+ ");
                        printf("x^%ld",i);
                    }
                    else if(a[i]==-1)
                    {
                        if(p1==1)
                        printf("- ");
                        else
                        printf("-");
                        printf("x^%ld",i);
                    }
                    else if(a[i]>1)
                    {
                        if(p1==1)
                        printf("+ ");
                        printf("%ldx^%ld",a[i],i);
                    }
                    else if(a[i]<0)
                    {
                        if(p1==1)
                        printf("- ");
                        else
                        printf("-");
                        printf("%ldx^%ld",-1*a[i],i);
                    }
               }
               if(i==1)
               {
                   if(a[i]==1)
                   {
                       if(p1==1)
                       printf("+ ");
                       printf("x");
                   }
                   else if(a[i]==-1)
                   {
                       if(p1==1)
                       printf("- ");
                       else
                       printf("-");
                       printf("x");
                   }
                   else if(a[i]>1)
                   {
                       if(p1==1)
                       printf("+ ");
                       printf("%ldx",a[i]);
                   }
                   else if(a[i]<0)
                   {
                       if(p1==1)
                       printf("- ");
                       else
                       printf("-");
                       printf("%ldx",-1*a[i]);
                   }
               }
               if(i==0)
               {
                   if(a[i]==1)
                   {
                       if(p1==1)
                       printf("+ ");
                       printf("%ld",a[i]);
                   }
                   else if(a[i]==-1)
                   {
                       if(p1==1)
                       printf("- ");
                       else
                       printf("-");
                       printf("%ld",-1*a[i]);
                   }
                   else if(a[i]>1)
                   {
                       if(p1==1)
                       printf("+ ");
                       printf("%ld",a[i]);
                   }
                   else if(a[i]<0)
                   {
                       if(p1==1)
                       printf("- ");
                       else
                       printf("-");
                       printf("%ld",-1*a[i]);
                   }
               }
               p1=1;
            }
        }
        if(p1==0)
        printf("0");
        printf("\n");
    }
    return 0;
}

UVA 353 - Pesky Palindromes

///...................SUBHASHIS MOLLICK...................///
///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
///....................SESSION-(14-15)....................///
#include<bits/stdc++.h>
using namespace std;
#define sf(a) scanf("%lld",&a)
#define sf2(a,b) scanf("%lld %lld",&a,&b)
#define sf3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pf(a) printf("%lld",a)
#define pf2(a,b) printf("%lld %lld",a,b)
#define pf3(a,b,c) printf("%lld %lld %lld",a,b,c)
#define nl printf("\n")
#define   timesave              ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define pb push_back
#define MPI map<int,int>mp;
#define fr(i,n) for(i=0;i<n;i++)
#define fr1(i,n) for(i=1;i<=n;i++)
#define frl(i,a,b) for(i=a;i<=b;i++)
/*primes in range 1 - n
1 - 100(1e2) -> 25 pimes
1 - 1000(1e3) -> 168 primes
1 - 10000(1e4) -> 1229 primes
1 - 100000(1e5) -> 9592 primes
1 - 1000000(1e6) -> 78498 primes
1 - 10000000(1e7) -> 664579 primes
large primes ->
104729 1299709 15485863 179424673 2147483647 32416190071 112272535095293 48112959837082048697
*/
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
main()
{
    timesave;
    string s;
    while(cin>>s)
    {
       long i,j,cnt=0,sz;
       sz=s.size();
       map<string,long>mp;
       for(i=0;i<sz;i++)
       {
          string s1,s2;
          for(j=i;j<sz;j++)
          {
             s1+=s[j];
             s2=s1;
             reverse(s2.begin(),s2.end());
             if(s2==s1&&mp[s1]==0)
               {
                  cnt++;
                  mp[s1]=1;
               }
          }
       }
       cout<<"The string '"<<s<<"' contains "<<cnt<<" palindromes.\n";
    }
}

UVA 496 - Simply Subsets

///...................SUBHASHIS MOLLICK...................///
///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
///....................SESSION-(14-15)....................///
#include<bits/stdc++.h>
using namespace std;
#define sf(a) scanf("%lld",&a)
#define sf2(a,b) scanf("%lld %lld",&a,&b)
#define sf3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pf(a) printf("%lld",a)
#define pf2(a,b) printf("%lld %lld",a,b)
#define pf3(a,b,c) printf("%lld %lld %lld",a,b,c)
#define nl printf("\n")
#define   timesave              ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define pb push_back
#define MPI map<int,int>mp;
#define fr(i,n) for(i=0;i<n;i++)
#define fr1(i,n) for(i=1;i<=n;i++)
#define frl(i,a,b) for(i=a;i<=b;i++)
/*primes in range 1 - n
1 - 100(1e2) -> 25 pimes
1 - 1000(1e3) -> 168 primes
1 - 10000(1e4) -> 1229 primes
1 - 100000(1e5) -> 9592 primes
1 - 1000000(1e6) -> 78498 primes
1 - 10000000(1e7) -> 664579 primes
large primes ->
104729 1299709 15485863 179424673 2147483647 32416190071 112272535095293 48112959837082048697
*/
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
main()
{
    timesave;
    string s;
    while(getline(cin,s))
    {
       vector<long>fstvec,scndvec;
       long number;
        stringstream ss;
        ss<<s;
        while(ss>>number)
        {
            fstvec.push_back(number);
        }
        getline(cin,s);
        stringstream ss1;
        ss1<<s;
        while(ss1>>number)
        {
            scndvec.push_back(number);
        }
        long fstsz=fstvec.size();
        long scndsz=scndvec.size();
        long i,j,cnt=0,cnt1=0;
        for(i=0;i<fstsz;i++)
        {
           for(j=0;j<scndsz;j++)
           {
              if(fstvec[i]==scndvec[j])
              {
                 cnt++;
                 break;
              }
           }
        }
        for(i=0;i<scndsz;i++)
        {
           for(j=0;j<fstsz;j++)
           {
              if(fstvec[j]==scndvec[i])
              {
                 cnt1++;
                 break;
              }
           }
        }
         if(fstsz==cnt&&fstsz<scndsz)
            puts("A is a proper subset of B");
        else if(scndsz==cnt1 &&scndsz<fstsz)
            puts("B is a proper subset of A");
        else if(fstsz==scndsz&&cnt==fstsz&&cnt1==scndsz)
            puts("A equals B");
        else if(cnt==0&&cnt1==0)
            puts("A and B are disjoint");
        else
            puts("I'm confused!");
        //cout<<fstvec.size()<<" "<<scndvec.size()<<endl;
    }
}

Minimum insertion to make a string palindrome

///...................SUBHASHIS MOLLICK...................///
///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
///....................SESSION-(14-15)....................///
#include<bits/stdc++.h>
using namespace std;
#define sf(a) scanf("%lld",&a)
#define sf2(a,b) scanf("%lld %lld",&a,&b)
#define sf3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pf(a) printf("%lld",a)
#define pf2(a,b) printf("%lld %lld",a,b)
#define pf3(a,b,c) printf("%lld %lld %lld",a,b,c)
#define nl printf("\n")
#define ll long long
#define pb push_back
#define MPI map<int,int>mp;
#define fr(i,n) for(i=0;i<n;i++)
#define fr1(i,n) for(i=1;i<=n;i++)
#define frl(i,a,b) for(i=a;i<=b;i++)
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
string s;
long dp[6100][6100];
long call(long i,long j)
{
    if(i>j)
        return 0;
    if(i==j)
        return 1;
    long ans=0;
    if(dp[i][j]!=-1)
        return dp[i][j];
    if(s[i]==s[j])
    {
        ans=call(i+1,j-1)+2;
    }
    else
    {
        ans=max(call(i+1,j),call(i,j-1));
    }
    return dp[i][j]=ans;
}
main()
{
    long ts,cs=1;
    cin>>ts;
    while(ts--)
    {
        cin>>s;
        long n=s.size();
        memset(dp,-1,sizeof(dp));
        long ans1=call(0,n-1);
        //printf("Case %ld: ",cs++);
        cout<<n-ans1<<endl;
    }
}

Square Root Decomposition Algorithm Code

#include<bits/stdc++.h>
using namespace std;
const int sz=100005;
const int inf=(1<<28);
template<typename t> t MIN3(t a,t b, t c)
{
    return min(a,min(b,c));
}
int block[400];
int arr[sz];
int getId(int indx,int blocksz)
{
    return indx/blocksz;
}
void init(int sz)
{
    for(int i=0; i<=sz; i++)
        block[i]=inf;
}
void update(int val,int indx,int blocksz)
{
    int id=getId(indx,blocksz);
    block[id]=min(block[id],val);
}
int query(int L,int R,int blocksz)
{
    int lid=getId(L,blocksz);
    int rid=getId(R,blocksz);
    if(lid==rid)
    {
        int ret=inf;
        for(int i=L; i<=R; i++)
            ret=min(ret,arr[i]);
        return ret;
    }
    int m1=inf,m2=inf,m3=inf;
    for(int i=L; i<(lid+1)*blocksz; i++)
        m1=min(m1,arr[i]);
    for(int i=lid+1; i<rid; i++)
        m2=min(m2,block[i]);
    for(int i=rid*blocksz; i<=R; i++)
        m3=min(m3,arr[i]);
    return MIN3(m1,m2,m3);
}
int main()
{
    int n,q;
    scanf("%d %d",&n,&q);
    int blocksz=sqrt(n);
    init(blocksz);
    for(int i=0; i<n; i++)
    {
        int x;
        scanf("%d",&x);
        arr[i]=x;
        update(x,i,blocksz);
    }
    while(q--)
    {
        int x,y;
        scanf("%d %d",&x,&y);
        printf("%d\n",query(x,y,blocksz));
    }
    return 0;
}

UVA 10165 - Stone Game

#include <stdio.h>
int main()
{
    long long int a[100001],b,c,i,n,j;
    while(scanf("%d",&n)==1)
    {
        if(n==0)
        break;
        for(j=0;j<n;j++)
        {
            scanf("%lld",&a[j]);
        }
        c=a[0];
        for(i=1;i<n;i++)
        {
            c=c^a[i];
        }
        if(c==0)
        printf("No\n");
        else printf("Yes\n");
    }
    return 0;

}

UVA 10042 - Smith Numbers

///...................SUBHASHIS MOLLICK...................///
///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
///....................SESSION-(14-15)....................///
#include<bits/stdc++.h>
using namespace std;
#define sf(a) scanf("%lld",&a)
#define sf2(a,b) scanf("%lld %lld",&a,&b)
#define sf3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pf(a) printf("%lld",a)
#define pf2(a,b) printf("%lld %lld",a,b)
#define pf3(a,b,c) printf("%lld %lld %lld",a,b,c)
#define nl printf("\n")
#define   timesave              ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define pb push_back
#define MPI map<int,int>mp;
#define fr(i,n) for(i=0;i<n;i++)
#define fr1(i,n) for(i=1;i<=n;i++)
#define frl(i,a,b) for(i=a;i<=b;i++)
/*primes in range 1 - n
1 - 100(1e2) -> 25 pimes
1 - 1000(1e3) -> 168 primes
1 - 10000(1e4) -> 1229 primes
1 - 100000(1e5) -> 9592 primes
1 - 1000000(1e6) -> 78498 primes
1 - 10000000(1e7) -> 664579 primes
large primes ->
104729 1299709 15485863 179424673 2147483647 32416190071 112272535095293 48112959837082048697
*/
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move

#define SIZE 31663
long visit[SIZE],k;
long prime[100000];
void sieve()
{
    long i,j;
    for(i=3; i<=sqrt(SIZE); i++)
    {
        if(visit[i]==0)
        {
            for(j=2*i; j<=SIZE; j+=i)
                visit[j]=1;
        }
    }
    visit[0]=visit[1]=1;
    k=0;
    for(i=0; i<=SIZE; i++)
    {
        if(visit[i]==0)
            prime[k++]=i;
    }
}
long chk_prime(long number)
{
    if(number==2)
        return 1;
    if(number%2==0)
        return 0;
    for(long ii=3; ii<=sqrt(number); ii+=2)
    {
        if(number%ii==0)
        {
            return 0;
        }
    }
    return 1;
}
long sum_of_digit(long number)
{
    long ans=0;
    while(number!=0)
    {
        ans+=number%10;
        number/=10;
    }
    return ans;
}
long factor(long number)
{
    long ans=0,i,sum1=0;
    for(i=0; prime[i]*prime[i]<=number; i++)
    {
        sum1=0;
        if(number%prime[i]==0)
        {

            while(number%prime[i]==0)
            {
                sum1+=sum_of_digit(prime[i]);
                number/=prime[i];
            }
        }
        //cout<<sum1<<endl;
        ans+=sum1;
    }
    if(number!=1)
    ans+=sum_of_digit(number);
    return ans;
}
main()
{
    timesave;
    sieve();
    long ts;
    cin>>ts;
    while(ts--)
    {
        long i,n,x,sod=0,pf=0;
        cin>>n;
        for(i=n+1;i<=2e9; i++)
        {
            x=chk_prime(i);
            if(x==0)  ///x jodi prime na  hoi tahole kaj korbe
            {
                sod=sum_of_digit(i);
                pf=factor(i);
                if(sod==pf)
                {
                    cout<<i<<endl;
                    break;
                }
            }
        }
    }
}