UVA 785 - Grid Colouring

#include<bits/stdc++.h>
using namespace std;
char s[35][85];
char ch;
long dr[]={1,0,-1,0};
long dc[]={0,1,0,-1};
long cnt=0;
void dfs(long x,long y)
{
    long i1,dx,dy;
    for(i1=0;i1<4;i1++)
    {
        dx=x+dr[i1];
        dy=y+dc[i1];
        if(s[dx][dy]==ch||s[dx][dy]=='X')
            continue;
        else
        {
            s[dx][dy]=ch;
            dfs(dx,dy);
        }
    }
}
main()
{
    while(gets(s[0]))
    {
        cnt=1;
        while(gets(s[cnt]))
        {
            if(s[cnt][0]=='_')
                break;
            cnt++;
        }
        long i,j;
        for(i=0;i<cnt;i++)
        {
            for(j=0;j<strlen(s[i]);j++)
            {
                if(s[i][j]!=' '&&s[i][j]!='X')
                {
                    ch=s[i][j];
                    s[i][j]=' ';
                    dfs(i,j);
                    s[i][j]=ch;
                }
            }
        }
         for(i=0;i<=cnt;i++)
            printf("%s\n",s[i]);
    }
}

UVA 784 - Maze Exploration

#include<bits/stdc++.h>
using namespace std;
char s[100][100],s1[100][100];
long  X[8]= {-1,-1,-1,0,0,1,1,1};
long  Y[8]= {-1,0,1,-1,1,-1,0,1};
long  m;
void dfs(long  i1,long  j1)
{
    long  vx,vy,k1;
    s[i1][j1]='#';
    for(k1=0; k1<8; k1++)
    {
        vx=i1+X[k1];
        vy=j1+Y[k1];
        if(s[vx][vy]==' ')
        {
            dfs(vx,vy);
        }
    }
}
main()
{
    long ts;
    cin>>ts;
    getchar();
    while(ts--)
    {

        long k,i,j,flag=0;
        k=0;
        while(1)
        {
            gets(s[k]);
           if(s[k][0]=='_')
           {
               k++;
                break;
           }
                k++;
        }
        for(i=0;i<k;i++)
        {
            long l=strlen(s[i]);
            for(j=0;j<l;j++)
            {
                if(s[i][j]=='*')
                {
                    dfs(i,j);
                    flag=1;
                    break;
                }
            }
            if(flag==1)
                break;
        }
        for(i=0;i<k;i++)
        {
            cout<<s[i]<<endl;
        }
    }
}

String upper to string lower (Convert)

#include<bits/stdc++.h>
#define fr(i1,m) for(int i1=0;i1<m;i1++)
using namespace std;
int main()
{
    string s,ans;
    ans="SOJOL";
    transform(ans.begin(),ans.end(),ans.begin(),::tolower);
    cout<<ans<<endl;
    return 0;
}

UVA 12543 - Longest Word

#include<stdio.h>
#include<string.h>
#include<ctype.h>
int main()
{
    char a[100000]={0},c[1000000]={0};
char b[100000]={0};
    long l2=0;
    while(~scanf("%s",a))
    {

        long l,p=0,i,l1;
        if(strcmp(a,"E-N-D")==0)
        break;
        l=strlen(a);
        for(i=0;i<l;i++)
        {
            if(isalpha(a[i]))
            {
                if(a[i]<97)
                b[p++]=a[i]+32;
                else
                b[p++]=a[i];
            }
            else if(a[i]=='-')
            b[p++]=a[i];
        }
        b[p]='\0';
        l1=strlen(b);
        if(l2<l1)
        {
            l2=l1;
            strcpy(c,b);
        }
    }//printf("%s\n",b);
    printf("%s\n",c);
    return 0;
}

UVA 10420 - List of Conquests

#include<bits/stdc++.h>
using namespace std;
main()
{
    long ts,k=0;
    map<string,long>mp;
    map<string,long>::iterator it;
    cin>>ts;
    getchar();
    while(ts--)
    {
        string s,s1;
        getline(cin,s);
        stringstream ss(s);
        ss>>s1;
        mp[s1]++;
    }
    long i;
    for(it=mp.begin();it!=mp.end();it++)
    {
        cout<<it->first<<" "<<it->second<<endl;
    }
}

UVA 424 - Integer Inquiry

#include<stdio.h>
#include<string.h>
int main()
{
    char st1[100000]={0},st2[100000]={0},f[100000]={0},str1[100000]={0},f1[100000]={0};
    long i=0,k=0,x=0,w=0,l2,cc,l3,q,qq;
    f[0]='0';f[1]='\0';
    while(scanf("%s",str1)!=EOF)
    {
        long l=0,l1=0,c=0,d=0,e=0,p=0;
        l=strlen(str1);
        l2=l;
        if(l==1&&str1[0]=='0')
        break;
        l1=strlen(f);
        l3=l1;
        for(i=l-1;i>=0;i--)
        {
            st1[e++]=str1[i];
        }
        st1[e]='\0';
        e=0;
        for(i=l1-1;i>=0;i--)
        {
            st2[e++]=f[i];
        }
        st2[e]=0;
        if(l<l1)
        l=l1;
        k=0;
        for(i=0,c=0;i<l;i++)
        {
            if(i<l2)
            q=st1[i]-48;
            else
            q=0;
            if(i<l3)
            qq=st2[i]-48;
            else
            qq=0;
            cc=q+qq+c;
            d=cc%10;
            f1[k++]=d+48;
            c=cc/10;
        }
        if(c>0)
        {
            f1[k++]=c+48;
        }
        f1[k]=0;
        for(i=k-1,p=0;i>=0;i--)
        {
            f[p++]=f1[i];
        }
        f[p]=0;
    }
    for(i=0;i<strlen(f);i++)
    printf("%c",f[i]);
    printf("\n");
    return 0;
}

Maximum Range query in segment tree

#include<bits/stdc++.h>
using namespace std;
#define mx 100000
long tree[mx*3],ar[mx];
void build(long node,long start,long end)
{
    if(start==end)
    {
        tree[node]=ar[start];
    }
    else
    {
        long mid=(start+end)/2;
        build(2*node,start,mid);
        build(2*node+1,mid+1,end);
        tree[node]=max(tree[2*node],tree[2*node+1]);
    }
}
long query(long node,long b,long  e,long i,long j)
{
    if (i > e || j < b)
        return -10000000;
    if (b >= i && e <= j)
        return tree[node];
    int Left = node * 2;
    int Right = node * 2 + 1;
    int mid = (b + e) / 2;
    int p1 = query(Left, b, mid, i, j);
    int p2 = query(Right, mid + 1, e, i, j);
    return max(p1,p2);
}
int main()
{
    long n,i,qry;
    while(cin>>n)
    {
        for(i=1; i<=n; i++)
        {
            cin>>ar[i];
        }
        build(1,1,n);
        long a,b;
        cin>>qry;
        for(i=1; i<=qry; i++)
        {
            cin>>a>>b;
            cout<<query(1,1,n,a,b)<<endl;
        }
    }
}

UVA 10008 - What's Cryptanalysis?

#include<bits/stdc++.h>
using namespace std;
main()
{
    long ts;
    cin>>ts;
    getchar();
    map<char,long>mp;
    long i,mx=0;
    while(ts--)
    {

        string s;
        getline(cin,s);
        long k;
        for(i=0; i<s.size(); i++)
        {
            if(isalpha(s[i]))
            {
                if(s[i]>='a'&&s[i]<='z')
                {
                    s[i]-=32;
                }
                k=s[i];
                mp[k]++;
                mx=max(mx,mp[k]);
            }

        }
    }
    long j;
        for(i=mx;i>=1;i--)
        {
            for(j=65;j<=90;j++)
            {
                if(mp[j]==i)
                {
                    cout<<char(j)<<" "<<mp[j]<<endl;
                }
            }
        }
}

UVA 10976 - Fractions Again?

#include<bits/stdc++.h>
using namespace std;
main()
{
    long z;
    while(cin>>z)
    {
        long long n,k,k1,i,ar[100010]={0},ar1[100010]={0},cnt=0;
        n=2*z;
        for(i=z+1;i<=n;i++)
        {
            k=(i-z);
            k1=(i*z);
            if(k1%k==0)
            {
                ar[cnt]=k1/k;
                ar1[cnt]=i;
                cnt++;
            }
        }
        cout<<cnt<<endl;
        for(i=0;i<cnt;i++)
        {
            printf("1/%ld = 1/%lld + 1/%lld\n",z,ar[i],ar1[i]);
        }

    }
}

UVA 108 - Maximum Sum

#include<bits/stdc++.h>
using namespace std;
main()
{
    long n;
    while(cin>>n)
    {
        long long i,j,i1,j1,ar[105][105]= {0},sum=0,mx=-2000,i2;
        for(i=0; i<n; i++)
        {
            for(j=0; j<n; j++)
            {
                cin>>ar[i][j];
            }
        }
        for(i=0; i<n; i++)
        {
            for(j=0; j<n; j++)
            {
                for(i1=i; i1<n; i1++)
                {
                    sum=0;
                    for(j1=j; j1<n; j1++)
                    {
                        for(i2=i; i2<=i1; i2++)
                            sum=sum+ar[i2][j1];
                        if(sum>mx)
                            mx=sum;
                    }
                }
            }
        }
        cout<<mx<<endl;
    }
}

UVA 10305 - Ordering Tasks

#include<bits/stdc++.h>
using namespace std;
main()
{
    long n,m;
    while(cin>>n>>m)
    {
        long i,vis[105][105]={0},indegree[105]={0},a,b,u;
        queue<long>q;
        vector<long>vec;
        if(n==0&&m==0)
            break;
        for(i=0;i<m;i++)
        {
            cin>>a>>b;
            vis[a][b]=1;
            indegree[b]++;
        }
        for(i=1;i<=n;i++)
        {
            if(indegree[i]==0)
            {
                q.push(i);
                vec.push_back(i);
            }
        }
        while(!q.empty())
        {
            u=q.front();
            q.pop();
            for(i=1;i<=n;i++)
            {
                if(vis[u][i]==0)
                    continue;
                indegree[i]--;
                if(indegree[i]==0)
                {
                    q.push(i);
                    vec.push_back(i);
                }
            }
        }
        for(i=0;i<vec.size();i++)
        {
            if(i==0)
            {
                cout<<vec[i];
            }
            else
                cout<<" "<<vec[i];
        }
        cout<<endl;
    }
}

Topological sort (2 different code)

1


#include<bits/stdc++.h>
#define fr(i1,m) for(int i1=0;i1<m;i1++)
using namespace std;
int main()
{
    long n,m;
    while(cin>>n>>m)
    {
        if(n==0&&m==0)
        break;
        queue<long>q;
        vector<long>vc;
        long x,y;
        long d[2002]={0},in[10010]={0},u,i;
        long g[200][200]={0};
        fr(i,m)
        {
            cin>>x>>y;
            g[x][y]=1;
            in[y]++;
        }
        for(i=1;i<=n;i++)
        {
            if(in[i]==0)
            {
                q.push(i);
                vc.push_back(i);
            }
        }
        while(!q.empty())
        {
            u=q.front();
            q.pop();
            for(i=1;i<=n;i++)
            {
                if(g[u][i]==0)
                continue;
                in[i]--;
                if(in[i]==0)
                {
                    q.push(i);
                    vc.push_back(i);
                }
            }
        }
        for(i=0;i<vc.size();i++)
        {
            cout<<vc[i];
            cout<<" ";
        }
        cout<<"\n";
    }
    return 0;
}


2.

int taken[55] = {};
int n, take[55][55], list[55] indegree[55];
int i, j, k;

// when take[a][b] = 1, that means a must come before b
// indegree[i] = number of items that that must come before i
// when taken[i] = 1, means we already have taken ith item
int invalid = 0;
for(i=0; i<n; i++) {
    for(j=0; j<n; j++) if( !indegree[j] && !taken[j]    ) {
        taken[j] = 1;
        list[i] = j;
        // in this step we are taking item j
        // we'd update the indegree[k] of items that depended on j
        for(k=0; k<n; k++)
            if( !taken[k] && take[j][k] ) --indegree[k];
        break;
    }
    if( j == n ) {
        invalid = 1;
        break;
    }
}

if( invalid ) printf("There is no solution\n");
else for(i=0; i<n; i++) printf("%d\n", list[i] );

UVA 11060 - Beverages

#include <bits/stdc++.h>
using namespace std;
main()
{
    long n,cs=1;
    while(cin>>n)
    {
        long i,m,indegree[200]={0},cnt=1,vis[200]={0},j,k;
        string s,s1;
        queue<long>q;
        map<long,string>mp1;
        map<string,long>mp;
        vector<long>vec[200];
        vector<long>vec1;
        for(i=1;i<=n;i++)
        {
            cin>>s;
            mp[s]=cnt;
            mp1[cnt]=s;
            cnt++;
        }
        cin>>m;
        for(i=1;i<=m;i++)
        {
            cin>>s>>s1;
            vec[mp[s]].push_back(mp[s1]);
            indegree[mp[s1]]++;
        }
        for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            {
                if(indegree[j]==0&&vis[j]==0)
                {
                    vis[j]=1;
                    vec1.push_back(j);
                    for(k=0;k<vec[j].size();k++)
                    {
                        long u=vec[j][k];
                        indegree[u]--;
                    }
                    break;
                }
            }
            printf("Case #%ld: Dilbert should drink beverages in this order:",cs++);
            for(i=0;i<vec1.size();i++)
            {
                cout<<" "<<mp1[vec1[i]];
            }
            cout<<"."<<endl<<endl;
            for(i=1;i<=n;i++)
            {
                vec[i].clear();
                vis[i]=0;
            }
            mp.clear();
            mp1.clear();
    }
}