UVa-231 Testing the catcher

#include<cstdio>
#include<iostream>
#include<algorithm>
#define INF 20000000000
#define MAX 10000

using namespace std;

int seq[MAX+1],len[MAX+5],n;

int lis(int n)
{ int i,j;
    for(i=0;i<n;i++)len[i]=1;
   for(i=0;i<n;i++){
       for(j=i+1;j<n;j++)
          {
              if(seq[j]>=seq[i]){if(len[i]+1>len[j])len[j]=len[i]+1;}
          }

                                 }
                                // for(i=0;i<n;i++)cout<<len[i]<<" ";
                                 //cout<<endl;
                                 int maX=*max_element(len,len+n);
                                 return maX;
}


int main()
{ int tc=1,signal=false;
   while(1){
               mylabel:

                int I=0;
                while(1){
                        scanf("%d",&seq[I]);
                        if(seq[I]==-1)break;
                        seq[I]=-1*seq[I];
                        I++;


                                }

                if(seq[0]==-1)break;
                 if(signal)cout<<endl;
                n=I;
                int result=lis(n);
                //printf("%d %d\n",tc,result);
                printf("Test #%d:\n",tc);
                cout<<"  maximum possible interceptions: "<<result<<endl;
                signal=true;
                tc++;
                goto mylabel;
                }
}

UVa-11151 Longest Pallindrome

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

#define MAX 1005

char inp[MAX],revinp[MAX];
int c[MAX][MAX];

using namespace std;

int pal(char *inp)
{
    int M=strlen(inp);

    strcpy(revinp,inp);
    reverse(revinp,revinp+M);


    int i,j;
    for(int i=1;i<=M;i++)c[i][0]=0;
    for(int j=0;j<=M;j++)c[0][j]=0;

    for(i=1;i<=M;i++)
        for(j=1;j<=M;j++)
           {
               if(inp[i-1]==revinp[j-1])c[i][j]=c[i-1][j-1]+1;
               else if(c[i-1][j]>=c[i][j-1])c[i][j]=c[i-1][j];
               else c[i][j]=c[i][j-1];
           }
           return c[M][M];
}
int main()
{
    int tc;
    bool signal=false;
    cin>>tc;
    tc+=1;

        while(tc--){ int len;

                                                //scanf("%s",&inp);
                       gets(inp);
                        if(signal==false){signal=true;continue;}

                       if(strcmp("\n",inp)==0)len=0;
                       else  len=pal(inp);
                      cout<<len<<endl;
                     }
                    return 0;

}

UVa-10036 Divisiblity

#include<iostream>
#include<cstdio>
#define MAX 10001
#define MAX2 100

using namespace std;
int N,K;
int A[MAX];
bool result[MAX][MAX2],count[MAX][MAX2];

void init()
{
    int i,j;
    for(i=0;i<MAX;i++)
        for(j=0;j<MAX2;j++)
            count[i][j]=false;
            return ;
}

bool div(int n,int k)
{  //printf("Calling(%d %d)\n",n,k);
   if(count[n][k]==true)return result[n][k];
    int k1=A[n]%K;
    if(k1<0)k1=K+k1;


    if(n==1 ){ if( (k1==k) || ( (K-k1)%K ==k) )return true;
                       else return false;
                      }
     bool c,d;
     c=div(n-1,(k+k1)%K );
     count[n-1][(k+k1)%K]=true;
     result[n-1][(k+k1)%K]=c;

          //printf("calling 1 ( %d %d),result %d\n",n-1,(A[n] %K),c);

     d=div(n-1,(k-k1)%K);
     count[n-1][(k-k1)%K]=true;
     result[n-1][(k-k1)%K]=d;
     //printf("calling 2( %d %d),result %d \n",n-1,(A[n] %K),d);
          if( c==true || d==true) return true;
     else return false;

}
int main()
{
    int tc;
    cin>>tc;
    while(tc--){  init();
                         cin>>N>>K;
                        for(int i=1;i<=N;i++)cin>>A[i];
                        //for(int i=1;i<=N;i++)cout<<A[i];

                        if(div(N,0))cout<<"Divisible"<<endl;
                        else cout<<"Not divisible"<<endl;




    }
}

UVa-191 :Intersection

#include<iostream>
#include<algorithm>
using namespace std;


class Point{

public:
int x,y;
void input(int a,int b);

};


void Point:: input(int a,int b)
{  x=a;
   y=b;

return ;
}

int cross(Point pi,Point pj,Point pk)
{  int a,b;
//cout<<"calling cross"<<endl;
    a=(pk.x-pi.x)*(pj.y-pi.y);
    b=(pj.x-pi.x)*(pk.y-pi.y);
    return a-b;

}

bool onsegment(Point pi,Point pj,Point pk)
{
    int minx=min(pi.x,pj.x),maxx=max(pi.x,pj.x),miny=min(pi.y,pj.y),maxy=max(pi.y,pj.y);

    if((minx<=pk.x) && (pk.x<=maxx) && (miny<=pk.y) && (pk.y<=maxy)) return true;
    //cout<<minx<<maxx<<maxy<<miny;
    //if(minx<=pk.x &(pk.x<=maxx) )return true;
    else return false;


}
bool intersect(Point P1,Point P2,Point P3,Point P4)
 {   long int d1,d2,d3,d4;
    d1=cross(P3,P4,P1);
    //cout<<"d1"<<d1<<endl;

    d2=cross(P3,P4,P2);
    //cout<<"d2"<<d2<<endl;

    d3=cross(P1,P2,P3);
    //cout<<"d3"<<d3<<endl;
    d4=cross(P1,P2,P4);
    //cout<<"d4"<<d4<<endl;
    if(((d1>0&&d2<0) || (d1<0&&d2>0) )&& ((d3>0&&d4<0)||(d3<0&&d4>0))) return true;
    else if (d1==0 && onsegment(P3,P4,P1)) return true;
    else if(d2==0 && onsegment(P3,P4,P2))return true;
     else if(d3==0 && onsegment(P1,P2,P3))return true;
    else if(d4==0 &&onsegment(P1,P2,P4))return true;

    else return false;}

bool onrect(int ax,int ay,int bx,int by,int Px,int Qy,int Rx,int Sy)
{  bool AX,AY,BX,BY;
  AX=AY=BX=BY=false;
     if(min(Px,Rx)<ax && ax<max(Px,Rx))AX=true;
     if(min(Qy,Sy)<ay &&ay<max(Qy,Sy))AY=true;
      if(min(Px,Rx)<bx && bx<max(Px,Rx))BX=true;
     if(min(Qy,Sy)<by &&by<max(Qy,Sy))BY=true;
     if(AX && AY && BX && BY==true)return true;
     else return false;

}

int main()
{  int tc,t=0;
cin>>tc;
    while(tc--){
    Point Ple,Pbe,P1,P2,P3,P4;
    int xle,yle,xbe,ybe,xleft,ytop,xright,ybottom;
    cin>>xle>>yle>>xbe>>ybe>>xleft>>ytop>>xright>>ybottom;
    bool b=onrect(xle,yle,xbe,ybe,xleft,ytop,xright,ybottom);

    Ple.input(xle,yle);
    Pbe.input(xbe,ybe);

     P1.input(xleft,ytop);
    P2.input(xleft,ybottom);
    P3.input(xright,ybottom);
    P4.input(xright,ytop);
   if(intersect(Ple,Pbe,P1,P2)==true)cout<<"T"<<endl;
   else if(intersect(Ple,Pbe,P2,P3)==true)cout<<"T"<<endl;
      else if (intersect(Ple,Pbe,P3,P4)==true)cout<<"T"<<endl;
   else if(intersect(Ple,Pbe,P4,P1)==true)cout<<"T"<<endl;
   else if(b==true)cout<<"T"<<endl;
   else cout<<"F"<<endl;
   //cout<<"Case :"<<++t<<endl;
   }

    return 0;
}

UVA-116 Undirectional TSP

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

#define MAXR 10
#define MAXC 100

using namespace std;



int main()
{
    int m,n;//row column
    int array[MAXR][MAXC],mini[MAXR][MAXC],child[MAXR][MAXC];//entry,minimum sum, path



    while(cin>>m>>n){if(feof(stdin))break;

                                 int i,j;//iterator

                                 for(i=0;i<m;i++)
                                        for(j=0;j<n;j++)cin>>array[i][j];  //array entry


                                 for(i=0;i<m;i++){mini[i][n-1]=array[i][n-1];}
                                   
                                for(j=n-2;j>=0;j--)            //dp apply +child set
                                     for(i=0;i<m;i++)
                                                          {
                                                            mini[i][j]=mini[(m+i-1)%m][j+1];
                                                            child[i][j]=(m+i-1)%m;

                                                          if(mini[i][j]>mini[i][j+1]){mini[i][j]=mini[i][j+1];
                                                                                                child[i][j]=i;
                                                                                              }
                                                         else if(mini[i][j]==mini[i][j+1] && child[i][j]>i)child[i][j]=i;

                                                    if(mini[i][j]>mini[(m+i+1)%m][j+1])
                                                                    {mini[i][j]=mini[(m+i+1)%m][j+1];
                                                                     child[i][j]=(m+i+1)%m;
                                                                     }
                                                   else if(mini[i][j]==mini[(m+i+1)%m][j+1] && child[i][j]>(m+i+1)%m)
                                                                      child[i][j]=(m+i+1)%m;

                                                     mini[i][j]+=array[i][j];
                                                         }


                    int minimum=30000000,minirow;
                    for(i=0;i<m;i++)if(minimum>mini[i][0]){minimum=mini[i][0];
                                                                               minirow=i;
                                                                               }   //minimum sum and source find

                    vector<int>path;
                    bool blank =false;

                    for(j=0;j<n;j++){path.push_back(minirow+1);                 //path ready+print
                                              if(blank)cout<<" ";
                                               cout<<path[j];
                                              minirow=child[minirow][j];
                                              blank=true;
                                              }


                    cout<<endl;


                    cout<<minimum<<endl;
                    }
   return 0;
}

UVA-108 Maximum sum

#include<cstdio>
#include<iostream>
#include<queue>

#define INF 30000
#define MAX 100

using namespace std;

int main()
{  int array[MAX][MAX];
   int sum[MAX][MAX][MAX];
 while(1){ int N;
           cin>>N;
           if(feof(stdin))break;
         
           priority_queue<int>pq;
           int i,j,k;

           for(i=0;i<N;i++)
               for(j=0;j<N;j++){cin>>array[i][j];          //array input
                                         pq.push(array[i][j]);} //to handle the case of all negative entries

         
            for(i=0;i<N;i++)                         // taking input for column combination sums
               for(j=0;j<N;j++){sum[i][j][j]=array[i][j];
                                           for(k=j+1;k<N;k++)sum[i][j][k]=sum[i][j][k-1]+array[i][k];
                                         }
       
          int Sum,maxsum=-INF;
          for(j=0;j<N;j++)
              for(k=j;k<N;k++){Sum=0;
                                         for(i=0;i<N;i++){Sum+=sum[i][j][k];
                                                                    if(Sum<0){Sum=0;}
                                                                    else if(Sum>=maxsum){maxsum=Sum;}
                                                                  }
                                           }
       
          if(maxsum==-INF)maxsum=pq.top();
          cout<<maxsum<<endl;

  }
  return 0;
}

UVA-103 Stacking Boxes

#include<iostream>
#include<algorithm>
#include<cstdio>

using namespace std;

int totalbox,DIM;
int len[32],order[32],pred[32];
class box{
int dim[12];
public:
void input();             //taking input
void dimsort();        //dimension sorting
int operator<<(box BOX1);  //lexico sorting;
int operator>(box BOX1);    //lis compare
box operator^(box &BOX1);  //swap box's
};

void box::input()
{
    int i;
    for(i=1;i<=DIM;i++)cin>>dim[i];

    return;
}

void box::dimsort()
{ sort(dim+1,dim+1+DIM);
  return;
}

int box::operator<<(box BOX1)
{ int i;
  for(i=1;i<=DIM;i++){if(dim[i]<BOX1.dim[i])return 1;
                                    if(dim[i]>BOX1.dim[i])return 0;
                                  }
  return 0;
}

int box::operator>(box BOX1)
{ int i;
  for(i=1;i<=DIM;i++)if(dim[i]<=BOX1.dim[i])return 0;
  return 1;
 }

box box::operator^(box &BOX1)
{
    int i;
    for(i=1;i<=DIM;i++)swap(dim[i],BOX1.dim[i]);
    return *this;
}
void setvalue()
{
   int i;
   for(i=1;i<=totalbox;i++){order[i]=i;len[i]=1;
                         
                           }

   return;
}

 int main()
 {   int signal=0;
     while(cin>>totalbox>>DIM)
    {   if(signal)cout<<endl;
        box BOX[32];
        int i,j;
        setvalue();
        for(i=1;i<=totalbox;i++){BOX[i].input();
                                              BOX[i].dimsort();
                                             }

        for(i=1;i<totalbox;i++)
                    for(j=i+1;j<=totalbox;j++)
                                             if(BOX[j]<<BOX[i]){ BOX[j]^BOX[i];
                                                                                swap(order[j],order[i]);
                                                                               }
                             
                               
       
         for(i=1;i<totalbox;i++)
           for(j=i+1;j<=totalbox;j++){ if(BOX[j]>BOX[i] && len[i]+1>len[j]){len[j]=len[i]+1;
                                                                                                                    pred[j]=i;
                                                                                                                   }
                                                     }

            int max=0,maxel;;
            for(i=1;i<=totalbox;i++)if(max<len[i]){max=len[i];maxel=i;}
          int rev[32];
            rev[max]=order[maxel];
            for(i=max-1;i>0;i--){ rev[i]=order[pred[maxel]];
                                            maxel=pred[maxel];
                                            }
         
            cout<<max<<endl;
            cout<<rev[1];
            for(i=2;i<=max;i++)cout<<" "<<rev[i];
            cout<<endl;
            signal=1;

    }
    return 0;
    }