uva 541 - Error Correction -solution

#include<cstdio>
#include<string.h>
using namespace std;

int main()
{
    int n,bit[100][100];
   
    while (scanf("%d",&n)==1)
    {
        if (n==0) return 0;
        int a,r,c,cntr,cntc;
        int row[n],col[n];
        memset(row,0,sizeof(row));
        memset(col,0,sizeof(col));
        for (int i=0;i<n;i++)
        {
            for (int j=0;j<n;j++)
            {
                scanf("%d",&a);
                bit[i][j]=a;
                row[i]+=a;
                col[j]+=a;
            }
        }
        cntr=0;
        cntc=0;
        for (int i=0;i<n;i++)
        {
            if (row[i]%2)
            {
                cntr++;
                r=i;
            }
            if (col[i]%2)
            {
                cntc++;
                c=i;
            }
        }
       
        if (cntr==0 && cntc==0) printf("OK\n");
        else if (cntr==1 && cntc==1) printf("Change bit (%d,%d)\n",r+1,c+1);
        else printf("Corrupt\n");
       
    }
    return 0;
   
}

Read More

uva 101 - The Blocks Problem -solution

#include <cstdio>
#include <cstring>
#include <string>
#include <stack>
using namespace std;

int block[25];

stack<int> s[25], tmp;

void move_onto(int a, int b);
void move_over(int a, int b);
void pile_onto(int a, int b);
void pile_over(int a, int b);

int main()
{
        int n, a, b;
        char c1[10], c2[10];

        while(scanf("%d",&n)==1)
        {
                for(int i = 0; i < n; i++)
                {
                        s[i].push(i);
                        block[i] = i;
                }

                while(scanf("%s",c1)!=EOF)
                {
                         if(c1[0] == 'q')
                                 break;

                         scanf("%d %s %d",&a,c2,&b);

                         if(a != b && block[a] != block[b])
                         {
                                 if(c1[0] == 'm')
                                 {
                                         if(c2[1] == 'n')
                                                 move_onto(a,b);
                                         else
                                                 move_over(a,b);
                                 }
                                 else
                                 {
                                          if(c2[1] == 'n')
                                                  pile_onto(a,b);
                                          else
                                                  pile_over(a,b);
                                  }
                         }
               }

                for(int i = 0; i < n; i++)
               {
                       printf("%d:",i);
                       while(!s[i].empty())
                       {
                                tmp.push(s[i].top());
                                s[i].pop();
                        }

                        while(!tmp.empty())
                        {
                                printf(" %d",tmp.top());
                                tmp.pop();
                        }
                        printf("\n");
                 }
        }
        return 0;
}

void move_onto(int a, int b)
{
        while(s[block[a]].top() != a)
        {
                int t = s[block[a]].top();
                s[t].push(t);
                block[t] = t;
                s[block[a]].pop();
        }

        while(s[block[b]].top() != b)
        {
                int t = s[block[b]].top();
                s[t].push(t);
                block[t] = t;
                s[block[b]].pop();
        }

        s[block[b]].pop();
        block[b] = b;
        s[b].push(b);

        s[b].push(s[block[a]].top());
        s[block[a]].pop();
        block[a] = b;
}

void move_over(int a, int b)
{
        while(s[block[a]].top() != a)
        {
                int t = s[block[a]].top();
                s[t].push(t);
                block[t] = t;
                s[block[a]].pop();
        }

        s[block[b]].push(s[block[a]].top());
        s[block[a]].pop();
        block[a] = block[b];
}

void pile_onto(int a, int b)
{
        while(s[block[b]].top() != b)
        {
                 int t = s[block[b]].top();
                 s[t].push(t);
                 block[t] = t;
                 s[block[b]].pop();
         }

          s[block[b]].pop();
          block[b] = b;
          s[b].push(b);

          while(s[block[a]].top() != a)
          {
                  tmp.push(s[block[a]].top());
                  s[block[a]].pop();
          }

          tmp.push(s[block[a]].top());
          s[block[a]].pop();

          while(!tmp.empty())
          {
                  s[block[b]].push(tmp.top());
                  block[tmp.top()] = block[b];
                  tmp.pop();
          }
}

void pile_over(int a, int b)
{
        while(s[block[a]].top() != a)
        {
                tmp.push(s[block[a]].top());
                s[block[a]].pop();
        }

        tmp.push(s[block[a]].top());
        s[block[a]].pop();

        while(!tmp.empty())
        {
                s[block[b]].push(tmp.top());
                block[tmp.top()] = block[b];
                tmp.pop();
        }
}

Read More

UVA 10050 : Hartals - solution

#include<cstdio>
using namespace std;

int main()
{
    int t;
    scanf("%d",&t);
    while (t--)
    {
        int n,q,p,r,count;
        scanf("%d",&n);
        int a[n+1]={0};
        scanf("%d",&p);
        count=0;
        while (p--)
        {
            scanf("%d",&q);
            for (int i=q;i<=n;i+=q)
            {
                r=i%7;
                if (a[i]==0 && r!=0 && r!=6)
                {
                    count++;
                    a[i]=1;
                }
            }
        }
        printf("%d\n",count); 
    }
    return 0;
}

Read More

uva 12578 solution

#include<cstdio>
#include<cmath>
#define pi acos(-1)
using namespace std;
int main()
{
    int t,l;
    scanf("%d",&t);
    while (t--)
    {
        scanf("%d",&l);
        double green,red,len,wid,r;
        len=(double)l;
        wid=len*0.60;
        r=len/5.0;
        red=pi*r*r;
        green=len*wid-red;
        printf("%.2lf %.2lf\n",red,green);
    }
    return 0;
}

Read More

uva 490 - Rotating Sentences - solution

#include<cstdio>
#include<string.h>
using namespace std;

int main()
{
    char s[105][105];
    int k=0;
    int max_len=-1;
    while (gets(s[k]))
    {
        int len=strlen(s[k]);
        if (len>max_len) max_len=len;
        for (int i=len;i<102;i++)
        s[k][i]=' ';
        k++;
    }
    for (int i=0;i<max_len;i++)
    {
        for ( int j=k-1;j>=0;j--)
        {
            printf("%c",s[j][i]);
        }
        printf("\n");
    }
    return 0;
}

Read More

uva 10405 - Longest Common Subsequence - solution

#include<cstdio>
#include<string.h>
#include<algorithm>
using namespace std;

#define mx 1001
char a[mx],b[mx];
int dp[mx][mx];
bool visited[mx][mx];

int lcs(int i,int j)
{
    if (a[i]=='\0' || b[j]=='\0') return 0;
    if (visited[i][j]) return dp[i][j];
    int ans=0;
    if (a[i]==b[j]) ans=1+lcs(i+1,j+1);
    else ans=max(lcs(i,j+1),lcs(i+1,j));
    visited[i][j]=true;
    dp[i][j]=ans;
    return dp[i][j];
}

int main()
{
    while (gets(a) && gets(b))
    {
        memset(visited,false,sizeof (visited));
        printf("%d\n",lcs(0,0));
    }
    return 0;
}

Read More

UVA problem 10935- Throwing cards away I : soution

# include <cstdio>
# include <queue>
using namespace std;
int main ()
{
    int n, x;
    queue< int > q;
    while (scanf("%d",&n), n)
    {
        for ( int i = 1 ; i <= n; i++)
        q. push (i);
        printf ("Discarded cards:" );
        while (q.size () > 1 )
        {
        printf (" %d" , q.front());
        q.pop();
        x = q.front();
        q.pop ();
        if (!q. empty())
        printf ("," );
        q. push (x);
        }
        printf ("\nRemaining card: %d\n" , q. front());
        q. pop ();
    }
    return 0 ;
}

Read More