UVA 10751 - Chessboard

#include <cstdio>

#include <cmath>

using namespace std;

int main()

{

    int tc, n;

    scanf("%d", &tc);

    while (tc--)

    {

        scanf("%d", &n);

        if (n > 1)

            printf("%.3lf\n", (4 * n - 4) + sqrt(2) * (n - 2) * (n - 2));

        else

            printf("0.000\n");

    }

    return 0;

}

UVA 10137 - The Trip

#include<bits/stdc++.h>
using namespace std;
main()
{
    long n;
    while(cin>>n)
    {
        if(n==0)
            break;
        long i;
        double ar[10010]= {0.0},sum=0.0,avg=0;
        for(i=0; i<n; i++)
        {
            cin>>ar[i];
            sum+=ar[i];
        }
        avg=sum/n;
        sum=0.0;
        double sum1=0.0,baki;
        long ans=0;
        for(i=0; i<n; i++)
        {
            baki=avg-ar[i];
            if(baki>0)
            {
                ans=(baki*100);
                sum=sum+ans;
            }
            else
            {
                baki=baki*-1;
                ans=(baki*100);
                sum1=sum1+ans;
            }
        }
        if(sum>sum1)
            printf("$%.2lf\n",sum/100.0);
        else
            printf("$%.2lf\n",sum1/100.0);
    }
}

UVA 12160 - Unlock the Lock

#include<bits/stdc++.h>
using namespace std;
long vis[10005],dist[10005],i,l,u,r,ar[15];
void bfs(long src)
{
    queue<long>q;
    q.push(src);
    vis[src]=0;
    dist[src]=0;
    while(!q.empty())
    {
        long u1=q.front();
        q.pop();
        for(i=0;i<r;i++)
        {
            long v=(u1+ar[i])%10000;
            if(vis[v]==0)
            {
                vis[v]=1;
                dist[v]=dist[u1]+1;
                q.push(v);
            }
        }
    }
}
main()
{
    long cs=1;
    while(cin>>l>>u>>r)
    {
        if(l==0&&u==0&&r==0)
            break;
        for(i=0;i<r;i++)
        {
            cin>>ar[i];
        }
        bfs(l);
        printf("Case %ld: ",cs++);
        if(dist[u]==0)
            printf("Permanently Locked\n");
        else
        cout<<dist[u]<<endl;
        for(i=0;i<10005;i++)
        {
            vis[i]=0;
            dist[i]=0;
        }
    }
}

UVA 12917 - Prop hunt!

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int a,b,c;
    while(cin>>a>>b>>c)
    {
        if((a+b)>c)
            cout<<"Hunters win!"<<endl;
        else
            cout<<"Props win!"<<endl;
    }
}

UVA 1112 - Mice and Maze

#include<bits/stdc++.h>
using namespace std;
vector<long>vec[105],cost[105];
long sorc,desti;
long dist[105];
struct node
{
    long u,w;
    node(long a,long b)
    {
        u=a;
        w=b;
    }
    bool operator < ( const node& p ) const
    {
        return w > p.w;
    }
};
void dijkstra(long s)
{

    priority_queue<node>pq;
    dist[s]=0;
    pq.push(node(s,0));
    while(!pq.empty())
    {
        node top=pq.top();
        pq.pop();
        long u=top.u;
        for(long i=0;i<(long)vec[u].size();i++)
        {
            long v=vec[u][i];
            if(dist[u]+cost[u][i]<dist[v])
            {
                dist[v]=dist[u]+cost[u][i];
                pq.push(node(v,dist[v]));
            }
        }
    }
}
main()
{
    long ts,cs=1;
    cin>>ts;
    while(ts--)
    {
        if(cs>1)
            cout<<endl;
        long i,n,e;
        cin>>n>>desti>>sorc>>e;
        for(long i=1; i<=n; i++)
        dist[i]=100000000;
        for(i=0;i<e;i++)
        {
            long u,v,w;
            cin>>u>>v>>w;
            vec[u].push_back(v);
            vec[v].push_back(u);
            cost[u].push_back(w);
            cost[v].push_back(w);
        }
        long cnt=0;
        dijkstra(desti);
        for(i=1;i<=n;i++)
        {
            if(dist[i]<=sorc)
                cnt++;
        }
        cs++;
        cout<<cnt<<endl;
        for(i=1;i<=n;i++)
        {
            cost[i].clear();
            vec[i].clear();
        }
    }
}

UVA 10986 - Sending email

#include<bits/stdc++.h>
using namespace std;
vector<long>vec[200002],cost[200002];
long sorc,desti;
long dist[200002];
struct node
{
    long u,w;
    node(long a,long b)
    {
        u=a;
        w=b;
    }
    bool operator < ( const node& p ) const
    {
        return w > p.w;
    }
};
long dijkstra(long n)
{
    for(long i=0; i<=n; i++)
        dist[i]=10000000;
    priority_queue<node>pq;
    dist[sorc]=0;
    pq.push(node(sorc,0));
    while(!pq.empty())
    {
        node top=pq.top();
        pq.pop();
        long u=top.u;
        if(u==desti)
        {
            return dist[desti];
        }
        for(long i=0;i<(long)vec[u].size();i++)
        {
            long v=vec[u][i];
            if(dist[u]+cost[u][i]<dist[v])
            {
                dist[v]=dist[u]+cost[u][i];
                pq.push(node(v,dist[v]));
            }
        }
    }
    return -1;
}
main()
{
    long ts,cs=1;
    cin>>ts;
    while(ts--)
    {
        long i,n,e;
        cin>>n>>e>>sorc>>desti;
        for(i=0;i<e;i++)
        {
            long u,v,w;
            cin>>u>>v>>w;
            vec[u].push_back(v);
            vec[v].push_back(u);
            cost[u].push_back(w);
            cost[v].push_back(w);
        }
        long ans=dijkstra(n);
        if(ans==-1)
            printf("Case #%ld: unreachable\n",cs++);
        else
            printf("Case #%ld: %ld\n",cs++,ans);
        for(i=0;i<n;i++)
        {
            cost[i].clear();
            vec[i].clear();
        }
    }
}

UVA 429 - Word Transformation

#include<bits/stdc++.h>
#define fr(i1,m) for(int i1=0;i1<m;i1++)
using namespace std;
vector<int>vc[10000];
int  bfs(int n,int m)
{
    queue<int>q;
    q.push(n);
    int t[100000]= {0},d[100000]= {0};
    t[n]=1;
    d[n]=0;
    while(!q.empty())
    {
        int u=q.front();
        if(u==m)
            return d[u];
        for(int i=0; i<vc[u].size(); i++)
        {
            int v=vc[u][i];
            if(!t[v])
            {
                d[v]=d[u]+1;
                t[v]=1;
                q.push(v);
            }
        }
        q.pop();
    }
}

int main()
{
    long n;
    scanf("%ld",&n);
    fr(ii,n)
    {
        if(ii>0)
            cout<<"\n";
        long p=0,l=1,hh,j,c;
        char ch[100000];
        string s[10000],s1,ff,f,kk,rr;
        map<string,int>mp;
        while(cin>>s1)
        {
            if(s1=="*")
                break;
            s[p]=s1;
            mp[s1]=l++;
            p++;

        }
        fr(i,p)
        {
            for(j=i+1; j<p; j++)
            {
                if(s[i].size()==s[j].size())
                {
                    hh=0;
                    kk=s[j];
                    rr=s[i];

                    fr(k,s[i].size())
                    {
                        if(rr[k]!=kk[k])
                        {
                            hh++;
                            if(hh>1)
                                break;
                        }
                        if(hh>1)
                            break;
                    }
                    if(hh==1)
                    {
                        vc[mp[rr]].push_back(mp[kk]);
                        vc[mp[kk]].push_back(mp[rr]);
                    }
                }
            }
        }
        getchar();
        //  scanf("\n");
        while(gets(ch))
        {
            if(ch[0]=='\0')
                break;
            f="";
            ff="";
            c=0;
            fr(i,strlen(ch))
            {
                if(ch[i]==' ')
                    c=1;
                else if(c==0)
                    f+=ch[i];
                else
                    ff+=ch[i];

            }
            cout<<f<<" "<<ff<<" "<<bfs(mp[f],mp[ff])<<"\n";
        }
        fr(i,l+4)
        vc[i].clear();

    }
    return 0;
}