Light OJ 1027 - A Dangerous Maze

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll i,j,k,l,m,n,test,ng,sum;
    cin>>test;
    for(k=1;k<=test;k++)
    {
        cin>>n;
        ng=0;
        sum=0;
        for(i=0;i<n;i++)
        {
            cin>>m;
            sum+=abs(m);
            if(m>0)
            {
                ng++;
            }
        }
        cout<<"Case "<<k<<": ";
        if(ng==0)
        {
            cout<<"inf"<<endl;
        }
        else
        {
            cout<<sum/__gcd(sum,ng)<<"/"<<ng/__gcd(sum,ng)<<endl;
        }
    }
    return 0;
}

Light OJ 1016 - Brush (II)

#include<iostream>
#include<algorithm>
#include<string>
#include<cmath>

using namespace std;
typedef long long ll;
int main()

{
    ll i,j,k,l,m,n,test,y[100009],x,w;
    cin>>test;
    for(k=1;k<=test;k++)
    {
        cin>>n>>w;
        for(i=0;i<n;i++)
        {
            cin>>x>>y[i];
        }
        sort(y,y+n);
        ll ans=1;
        ll spc=y[0]+w;
        for(i=1;i<n;i++)
        {
            if(y[i]>spc)
            {
                ans++;
                spc=y[i]+w;
            }
        }
        cout<<"Case "<<k<<": "<<ans<<endl;
    }
    return 0;
}

Light OJ 1005 - Rooks

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[70][70];
ll nCr(ll n,ll r)
{
    if(r==1) return n;
    if(n==r) return 1;
    if(dp[n][r]!=-1) return dp[n][r];
        else{
        dp[n][r]=nCr(n-1,r)+nCr(n-1,r-1);
        return dp[n][r];
    }
}
int main()
{
    //ofstream o("output.txt");
    ll i,j,k,l,m,n,test;
    cin>>test;
    for(j=1;j<=test;j++)
    {
        cin>>n>>k;
        memset(dp,-1,sizeof(dp));
        cout<<"Case "<<j<<": ";
        if(n<k)
            cout<<0<<endl;
        else if(k==0)
            cout<<1<<endl;
        else
        {
            ll mul=1;
            for(i=n-k+1;i<=n;i++)
            {
                mul=mul*i;
            }
            cout<<mul*nCr(n,k)<<endl;
        }

    }
    return 0;
}

UVa 11710 - Expensive subway

#include<bits/stdc++.h>
#define mx 100009
using namespace std;
map<string,int>mp;
bool visited[79809];
vector<string>v;
vector<int>g[79809];
int ct;
void dfs(int n)
{
    visited[n]=1;
    for(int i=0;i<g[n].size();i++)
    {
        int m=g[n][i];
        if(!visited[m])
        {
            ct++;
            dfs(m);
        }
    }
}
struct edge
{
    int u,v,w;
    bool operator < (const edge& p) const
    {
        return w<p.w;
    }
};
int pr[mx];
vector<edge>e;
int fnd(int r)
{
    return (pr[r]==r)?r:fnd(pr[r]);
}
int mst(int n)
{
    sort(e.begin(),e.end());
    for(int i=1;i<=n;i++)
    {
        pr[i]=i;
    }
    int cnt=0,s=0;
    for(int i=0;i<(int)e.size();i++)
    {
        int u=fnd(e[i].u);
        int v=fnd(e[i].v);
        if(u!=v)
        {
            pr[u]=v;
            cnt++;
            s+=e[i].w;
            if(cnt==n-1)
                break;
        }
    }
    return s;
}
int main()
{
    int i,j,k,l,m,n;
    while(cin>>n>>m)
    {
        if(n==0&&m==0)
            break;
        else
        {
            mp.clear();
            e.clear();
            v.clear();
            string s;
            for(i=0;i<79809;i++)
            {
                g[i].clear();
            }
            memset(visited,0,sizeof(visited));
            for(i=0;i<n;i++)
            {
                cin>>s;
                v.push_back(s);
            }
            int num=1;
            for(i=0;i<m;i++)
            {
                string from,to;
                int u,v,w;
                cin>>from>>to>>w;
                if(mp[from]!=0)
                {
                    u=mp[from];
                }
                if(mp[to]!=0)
                {
                    v=mp[to];
                }
                if(!mp[from])
                {
                    u=num;
                    mp[from]=num;
                    num++;
                }
                if(!mp[to])
                {
                    v=num;
                    mp[to]=num;
                    num++;
                }
                edge get;
                get.u=u;
                get.v=v;
                get.w=w;
                e.push_back(get);
                swap(u,v);
                get.u=u;
                get.v=v;
                get.w=w;
                e.push_back(get);
                g[u].push_back(v);
                g[v].push_back(u);
            }
            string st;
            cin>>st;
            int start=mp[st];
            ct=1;
            dfs(start);
            if(ct!=n)
            {
                cout<<"Impossible"<<endl;
                continue;
            }
            cout<<mst(n)<<endl;
        }
    }
    return 0;
}

UVa 11631 - Dark roads

#include<bits/stdc++.h>
#define mx 200009
using namespace std;
typedef long long ll;
struct edge
{
    ll u,v,w;
    bool operator < (const edge& p) const
    {
        return w<p.w;
    }
};
ll pr[mx];
vector<edge>e;
ll fnd(ll r)
{
    return (pr[r]==r)?r:fnd(pr[r]);
}
ll mst(ll n)
{
    sort(e.begin(),e.end());
    //reverse(e.begin(),e.end());
    for(ll i=1;i<=n;i++)
    {
        pr[i]=i;
    }
    ll cnt=0,s=0;
    for(int i=0;i<(ll)e.size();i++)
    {
        ll u=fnd(e[i].u);
        ll v=fnd(e[i].v);
        if(u!=v)
        {
            pr[u]=v;
            cnt++;
            s+=e[i].w;
            if(cnt==n-1)
                break;
        }
    }
    return s;
}
int main()
{
    //ofstream o("op.txt");
    while(1)
    {
        ll n,m,sum=0;
        scanf("%lld %lld",&n,&m);
        if(n==0&&m==0)
            break;
        for(int i=1;i<=m;i++)
        {
            ll u,v,w;
            scanf("%lld%lld%lld",&u,&v,&w);
            sum+=w;
            edge get;
            get.u=u+1;
            get.v=v+1;
            get.w=w;
            e.push_back(get);
        }
        printf("%lld\n",sum-mst(n));
        e.clear();
    }
    return 0;
}

UVa 10034 - Freckles

#include<bits/stdc++.h>
#define mx 100009
using namespace std;
typedef long long ll;
struct edge
{
    int u,v;
    double w;
    bool operator < (const edge& p) const
    {
        return w<p.w;
    }
};
int pr[mx];
vector<edge>e;
int fnd(int r)
{
    return (pr[r]==r)?r:fnd(pr[r]);
}
double mst(int n)
{
    sort(e.begin(),e.end());
    for(int i=1;i<=n;i++)
    {
        pr[i]=i;
    }
    int cnt=0;
    double s=0.0;
    for(int i=0;i<(int)e.size();i++)
    {
        int u=fnd(e[i].u);
        int v=fnd(e[i].v);
        if(u!=v)
        {
            pr[u]=v;
            cnt++;
            s+=e[i].w;
            if(cnt==n-1)
                break;
        }
    }
    return s;
}
int main()
{
    ll i,j,k,l,m,n,test;
    cin>>test;
    for(k=1;k<=test;k++)
    {

        cin>>n;
        vector< pair<double,double> >v;
        v.clear();
        e.clear();
        for(i=1;i<=n;i++)
        {
            double x,y;
            cin>>x>>y;
            v.push_back(make_pair(x,y));
        }
        for(i=0;i<n;i++)
        {
            for(j=i+1;j<n;j++)
            {
                double x1,x2,y1,y2;
                double d=sqrt((v[i].first-v[j].first)*(v[i].first-v[j].first)+(v[i].second-v[j].second)*(v[i].second-v[j].second));
                double u,v;
                edge get;
                get.u=i+1;
                get.v=j+1;
                get.w=d;
                e.push_back(get);
            }
        }
        printf("%.2f\n",mst(n));
        if(k<test)
            printf("\n");
    }
    return 0;
}

UVa 357 - Let Me Count The Ways

#include<bits/stdc++.h>
#define mod 100000007
using namespace std;
typedef long long ll;
ll arr[300009],coin[6]={0,1,5,10,25,50};
int main()
{
    ll i,j,k,l,m,n,test,make;
    while(cin>>make)
    {
        n=5;
        memset(arr,0,sizeof(arr));
        arr[0]=1;
        ll sum=0;
        for(i=1;i<=n;i++)
        {
            for(j=coin[i];j<=make;j++)
            {
                arr[j]=(arr[j])+(arr[j-coin[i]]);
            }
        }
        cout<<"There ";
        if(arr[make]<=1)
            cout<<"is only ";
        else
            cout<<"are ";
        cout<<arr[make]<<" ";
        if(arr[make]<=1)
            cout<<"way";
        else
            cout<<"ways";
        cout<<" to produce "<<make<<" cents change."<<endl;
    }
    return 0;
}

UVa 231 - Testing the CATCHER

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll arr[10000];
ll dp[40000];
ll n;
ll solve(ll i)
{
    if(i==n)
        return 0;
    if(dp[i]!=-1)
        return dp[i];
    ll cnt=0,mx=0;
    for(ll j=i+1;j<n;j++)
    {
        if(arr[i]>=arr[j])
        {
            ll tmp=solve(j);
            if(tmp>mx)
            {
                mx=tmp;
            }
        }
    }
    dp[i]=1+mx;
    return dp[i];
}
int main()
{
    //ofstream o("op.txt");
    ll i,j,k=1,l,m;
    memset(dp,-1,sizeof(dp));
    while(1)
    {
        memset(arr,0,sizeof(arr));
        cin>>m;
        if(m==-1)
            break;
        else
        {
            arr[0]=999999999;
            arr[1]=m;
            i=2;
            while(1)
            {
                cin>>m;
                if(m==-1)
                    break;
                arr[i]=m;
                i++;
            }
            n=i;
        }
        memset(dp,-1,sizeof(dp));
        if(k!=1)
            cout<<endl;
        cout<<"Test #"<<k<<":"<<endl;
        cout<<"  maximum possible interceptions: "<<solve(0)-1<<endl;
        k++;
    }
    return 0;
}

UVa 10819 - Trouble of 13-Dots

#include<bits/stdc++.h>
#define pi acos (-1.0)
using namespace std;
int n,amount;
int dp[500][12000];
typedef int (*compfn)(const void*, const void*);
struct s
{
    int tk,val;
}a[20000];
int compare(struct s *elem1, struct s *elem2)
{
   if(elem1->tk>elem2->tk)
      return 1;

   else if(elem1->tk<elem2->tk)
      return -1;
}
int func(int i,int w)
{
if(i==n) return 0;
if(dp[i][w]!=-1) return dp[i][w];
int profit1=0,profit2=0;
if((w+a[i].tk<=amount)||(w+a[i].tk>2000)&&(w+a[i].tk<=amount+200))
    {
        profit1=a[i].val+func(i+1,w+a[i].tk);
    }

profit2=func(i+1,w);
dp[i][w]=max(profit1,profit2);
return dp[i][w];
}
int main()
{
    int test,k,i;
    memset(dp,-1,sizeof(dp));
    while(cin>>amount>>n)
    {
        for(i=0;i<n;i++)
        {
            cin>>a[i].tk>>a[i].val;
        }
        qsort(a,n,sizeof(struct s),(compfn)compare);
        cout<<func(0,0)<<endl;
        memset(dp,-1,sizeof(dp));
    }
    return 0;
}

Light OJ 1004 Monkey Banana Problem

#include<bits/stdc++.h>
#define inf 1<<28
using namespace std;
typedef long long ll;
ll arr[500][500];
ll dp[500][500];
ll n;
ll call(ll i,ll j)
{
    ll k,l,m;
    if(i>=0&&i<500&&j>=0&&j<500&&arr[i][j]!=-1)
    {
        if(dp[i][j]!=-1)
            return dp[i][j];
        ll ret=-inf;
        ret=max(ret,call(i+1,j-1)+arr[i][j]);
        ret=max(ret,call(i+1,j)+arr[i][j]);
        return dp[i][j]=ret;
    }
    else return 0;
}
int main()
{
    ll i,j,k,l,m,test;
    cin>>test;
    for(k=1;k<=test;k++)
    {
        memset(arr,-1,sizeof(arr));
        memset(dp,-1,sizeof(dp));
        cin>>n;
        for(i=0,l=0;i<n;i++,l++)
        {
            for(j=n-l-1;j<n;j++)
            {
                cin>>arr[i][j];
            }
        }
        for(i=n,l=1;i<2*n-1;i++,l++)
        {
            for(j=0;j<n-l;j++)
            {
                cin>>arr[i][j];
            }
        }
       cout<<"Case "<<k<<": "<<call(0,n-1)<<endl;
    }
    return 0;
}

UVa 10926 - How Many Dependencies?

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
bool c[109];
vector<ll>graph[109];
ll ans[109];
ll cnt;
void dfs(ll n)
{
    c[n]=1;
    for(ll i=0;i<graph[n].size();i++)
    {
        ll tmp=graph[n][i];
        if(c[tmp]==0)
        {
            cnt++;
            dfs(tmp);
        }
    }
}
int main()
{
    ll i,j,k,l,m,n,test;
    while(1)
    {
        cin>>n;
        if(n==0)
            break;
        for(i=0;i<109;i++)
        {
            graph[i].clear();
        }
        for(i=1;i<=n;i++)
        {
            cin>>m;
            for(j=1;j<=m;j++)
            {
                cin>>k;
                graph[i].push_back(k);
            }
        }
        //cout<<1111<<endl;
        for(i=1,k=1;i<=n;i++)
        {
            memset(c,0,sizeof(c));
            cnt=0;
            dfs(i);
            ans[k]=cnt;
            //cout<<ans[k]<<endl;
            k++;
        }
        ll mx=-111;
        ll res;
        for(i=1;i<k;i++)
        {
            if(ans[i]>mx)
            {
                mx=ans[i];
                res=i;
            }
        }
        cout<<res<<endl;
    }
    return 0;
}

Light OJ 1041 Road Construction

#include<bits/stdc++.h>
#define mx 100009
using namespace std;
map<string,int>mp;
vector<int>graph[1000];
bool check[10009];
int cnt;
void dfs(int n)
{
    check[n]=1;
    for(int i=0;i<graph[n].size();i++)
    {
        int m=graph[n][i];
        if(check[m]==0)
        {
            dfs(m);
            cnt++;
        }
    }
}
struct edge
{
    int u,v,w;
    bool operator < (const edge& p) const
    {
        return w<p.w;
    }
};
int pr[mx];
vector<edge>e;
int fnd(int r)
{
    return (pr[r]==r)?r:fnd(pr[r]);
}
int mst(int n)
{
    sort(e.begin(),e.end());
    for(int i=1;i<=n;i++)
    {
        pr[i]=i;
    }
    int cnt=0,s=0;
    for(int i=0;i<(int)e.size();i++)
    {
        int u=fnd(e[i].u);
        int v=fnd(e[i].v);
        if(u!=v)
        {
            pr[u]=v;
            cnt++;
            s+=e[i].w;
            if(cnt==n-1)
                break;
        }
    }
    return s;
}
int main()
{
    int i,j,k,l,n,m,test;
    cin>>test;
    for(k=1;k<=test;k++)
    {
        cnt=0;
        cin>>m;
        memset(check,0,sizeof(check));
        int val=1;
        for(i=1;i<=m;i++)
        {
            string s1,s2;
            cin>>s1>>s2;
            if(!mp[s1])
            {
                mp[s1]=val;
                val++;
            }
            if(!mp[s2])
            {
                mp[s2]=val;
                val++;
            }
            int u,v,w;
            cin>>w;
            edge get;
            get.u=mp[s1];
            get.v=mp[s2];
            graph[get.u].push_back(get.v);
            graph[get.v].push_back(get.u);
            //cout<<get.u<<" "<<get.v<<endl;
            get.w=w;
            e.push_back(get);
        }
        dfs(1);
        //cout<<cnt<<" "<<val<<endl;
        cout<<"Case "<<k<<": ";
        if(abs(cnt-val)==2)
            cout<<mst(val-1)<<endl;
        else
            cout<<"Impossible"<<endl;
        mp.clear();
        e.clear();
        for(i=0;i<1000;i++)
        {
            graph[i].clear();
        }
    }
    return 0;
}

Light OJ 1029 Civil and Evil Engineer

#include<bits/stdc++.h>
#define mx 100009
using namespace std;
struct edge
{
    int u,v,w;
    bool operator < (const edge& p) const
    {
        return w<p.w;
    }
};
int pr[mx];
vector<edge>e;
int fnd(int r)
{
    return (pr[r]==r)?r:fnd(pr[r]);
}
int mst(int n)
{
    for(int i=0;i<n;i++)
    {
        pr[i]=i;
    }
    int cnt=0,s=0;
    for(int i=0;i<(int)e.size();i++)
    {
        int u=fnd(e[i].u);
        int v=fnd(e[i].v);
        if(u!=v)
        {
            pr[u]=v;
            cnt++;
            s+=e[i].w;
            if(cnt==n-1)
                break;
        }
    }
    return s;
}
int main()
{
    //ofstream o("op.txt");
    int i,j,k,l,n,m,test;
    cin>>test;
    for(k=1;k<=test;k++)
    {
        cin>>n;
        for(i=1;;i++)
        {
            int u,v,w;
            cin>>u>>v>>w;
            if(u==0&&v==0&&w==0)
                break;
            edge get;
            get.u=u;
            get.v=v;
            get.w=w;
            e.push_back(get);
        }
        int ans=0;
        sort(e.begin(),e.end());
        ans+=mst(n+1);
        reverse(e.begin(),e.end());
        ans+=mst(n+1);
        cout<<"Case "<<k<<": ";
        if(ans%2==0)
            cout<<ans/2<<endl;
        else
            cout<<ans<<"/"<<2<<endl;
        e.clear();
    }
    return 0;
}

Light OJ 1374 Confusion in the Problemset

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[1000009];
bool c[100009];
int main()
{
    ll i,j,k,l,m,n,test,arr[100009];
    cin>>test;
    for(k=1;k<=test;k++)
    {
        cin>>n;
        memset(a,0,sizeof(a));
        memset(c,0,sizeof(c));
        bool flag=1;
        for(i=0;i<n;i++)
        {
            cin>>arr[i];
            a[arr[i]]++;
            if(a[arr[i]]>2)
            {
                flag=0;
            }
            if(arr[i]>=n)
            {
                flag=0;
            }
        }
        sort(arr,arr+n);
        if(!flag)
        {
            cout<<"Case "<<k<<": "<<"no"<<endl;
            continue;
        }
        ll gar=-9999999;
        for(i=0;i<n;)
        {
            if(!flag)
                break;
            ll tmp=arr[i];
            if(a[tmp]==1)
            {
                //cout<<11111<<" "<<tmp<<endl;
                if(c[tmp]==0)
                {
                    c[tmp]=1;
                }
                else
                {
                    flag=0;
                }
                i=i+1;
            }
            else
            {
                //cout<<22222<<" "<<tmp<<endl;
                if(c[tmp]==0&&c[n-tmp-1]==0)
                {
                    c[tmp]=1;
                    c[n-tmp-1]=1;
                }
                else
                {
                    flag=0;
                }
                i=i+2;
            }
        }
        cout<<"Case "<<k<<": ";
        if(flag)
            cout<<"yes"<<endl;
        else
            cout<<"no"<<endl;
    }
    return 0;
}

Light OJ 1198 Karate Competition

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll i,j,k,l,m,n,test;
    cin>>test;
    for(k=1;k<=test;k++)
    {
        cin>>n;
        ll a[1009],b[1009];
        for(i=0;i<n;i++)
        {
            cin>>a[i];
        }
        for(j=0;j<n;j++)
        {
            cin>>b[j];
        }
        sort(a,a+n);
        sort(b,b+n);
        ll cnt=0;
        for(i=0;i<n;i++)
        {
            if(a[i]==-1)
                continue;
            ll in;
            bool flag=0;
            for(j=0;j<n;j++)
            {
                if(b[j]==-1)
                    continue;
                else
                {
                    if(a[i]>b[j])
                    {
                        flag=1;
                        in=j;
                    }
                }
            }
            if(flag)
            {
                a[i]=b[in]=-1;
                cnt+=2;
            }
        }
        for(i=0;i<n;i++)
        {
            if(a[i]==-1)
                continue;
            for(j=0;j<n;j++)
            {
                if(b[j]==-1)
                    continue;
                else
                {
                    if(a[i]==b[j])
                    {
                        a[i]=b[j]=-1;
                        cnt+=1;
                        break;
                    }
                }
            }
        }
        cout<<"Case "<<k<<": "<<cnt<<endl;
    }
    return 0;
}

Light OJ 1328 A Gift from the Setter

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll arr[100009];
int main()
{
    ll i,j,k,l,m,n,test,K,C;
    cin>>test;
    for(k=1;k<=test;k++)
    {
        cin>>K>>C;
        cin>>n>>arr[0];
        ll sum=arr[0];
        for(i=1;i<n;i++)
        {
            arr[i]=(K*arr[i-1]+C)%1000007;
            sum+=arr[i];
        }
        sort(arr,arr+n);
        ll S=0,prev_sum=0;
        for(i=0;i<n;i++)
        {
            prev_sum+=arr[i];
            ll tmp=((n-i-1)*arr[i])-(sum-prev_sum);
            if(tmp<0)
                tmp*=(-1);
            S+=tmp;
        }
        cout<<"Case "<<k<<": "<<S<<endl;
    }
    return 0;
}

Light OJ 1166 Old Sorting

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll i,j,k,l,m,n,test;
    cin>>test;
    for(k=1;k<=test;k++)
    {
        cin>>n;
        ll arr[1009];
        for(i=1;i<=n;i++)
        {
            cin>>arr[i];
        }
        ll cnt=0;
        cout<<"Case "<<k<<": ";
        for(i=1;i<=n;i++)
        {
            if(arr[i]!=i)
            {
                for(j=i+1;j<=n;j++)
                {
                    if(arr[j]==i)
                    {
                        swap(arr[i],arr[j]);
                        cnt++;
                    }
                }
            }
        }
        cout<<cnt<<endl;
    }
    return 0;
}

Light OJ 1389 Scarecrow

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll i,j,k,l,m,n,test;
    cin>>test;
    for(k=1;k<=test;k++)
    {
        string s;
        cin>>n>>s;
        ll cnt=0;
        for(i=0;i<s.size();i++)
        {
            if(s[i]=='#')
                cnt++;
        }
        cout<<"Case "<<k<<": ";
        if(cnt==n)
        {
            cout<<0<<endl;
            continue;
        }
        else
        {
            ll ans=0;
            for(i=0;i<n;i++)
            {
                //cout<<i<<endl;
                if(s[i]=='.')
                {
                    //cout<<"AAA:"<<i<<endl;
                    ans++;
                    i+=2;
                }
            }
            cout<<ans<<endl;
        }
    }
    return 0;
}

Light OJ 1221 Travel Company

#include<bits/stdc++.h>
#define inf 999999999
#define mx 10000
using namespace std;
typedef long long ll;
struct s
{
    ll from,to,cost;
}edge[mx];
ll edges,nodes,rat;
ll dist[mx];
int main()
{
    ll i,j,k,l,m,n,test;
    cin>>test;
    for(k=1;k<=test;k++)
    {
        fill(dist,dist+mx,inf);
        cin>>nodes>>edges>>rat;
        for(i=0;i<edges;i++)
        {
            cin>>edge[i].from>>edge[i].to;
            ll earn,exp;
            cin>>earn>>exp;
            edge[i].cost=rat*exp-earn;
        }
        ll now;
        ll u,v;
        for(i= 1;i<nodes;i++ )
        {
            for(j= 0;j<edges;j++ )
            {
                u=edge[j].from;
                v=edge[j].to;
                now=dist[u]+edge[j].cost;
                if(now<dist[v])
                    dist[v]=now;
            }
        }
        bool flag=false;
        for(i= 0;i<edges;i++)
        {
            u=edge[i].from;
            v=edge[i].to;
            now=dist[u]+edge[i].cost;
            if(now<dist[v])
            {
                flag=true;
                break;
            }
        }
        cout<<"Case "<<k<<": ";
        if(flag)
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
    }
    return 0;
}

SPOJ ABCDEF - ABCDEF

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll>v1;
vector<ll>v2;
vector<ll>v;
int main()
{
    ll i,j,k,l,m,n;
    while(cin>>n)
    {
        for(i=0;i<n;i++)
        {
            cin>>m;
            v.push_back(m);
        }
        for(i=0;i<n;i++)
        {
            for(j=0;j<n;j++)
            {
                for(k=0;k<n;k++)
                {
                    ll sum=(v[i]*v[j])+v[k];
                    v1.push_back(sum);
                }
            }
        }
        for(i=0;i<n;i++)
        {
            for(j=0;j<n;j++)
            {
                for(k=0;k<n;k++)
                {
                    if(v[k]!=0)
                    {
                        ll sum=(v[i]+v[j])*v[k];
                        v2.push_back(sum);
                    }
                }
            }
        }
        sort(v2.begin(),v2.end());
        sort(v1.begin(),v1.end());
        ll cnt=0;
        for(i=0;i<v1.size();i++)
        {
            cnt+=(upper_bound(v2.begin(),v2.end(),v1[i])-lower_bound(v2.begin(),v2.end(),v1[i]));
        }
        cout<<cnt<<endl;
        v.clear();
        v1.clear();
        v2.clear();
    }
    return 0;
}

Light OJ 1088 Points in Segments

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll i,j,k,l,m,n,test,q;
    scanf("%lld",&test);
    for(k=1;k<=test;k++)
    {
        vector<ll>v;
        scanf("%lld %lld",&n,&q);
        for(i=0;i<n;i++)
        {
            scanf("%lld",&m);
            v.push_back(m);
        }
        printf("Case %lld:\n",k);
        for(i=0;i<q;i++)
        {
            ll x,y,ans=0;
            scanf("%lld %lld",&x,&y);
            ans=(upper_bound(v.begin(),v.end(),y)-lower_bound(v.begin(),v.end(),x));
            printf("%lld\n",ans);
        }
    }
    return 0;
}

Light OJ 1076 Get the Containers

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll m,arr[10009],n;
bool bin_s(ll val)
{
    ll i,j,k,l,cnt=1,sum=0;
    for(i=1;i<=n;i++)
    {
        //cout<<sum<<" "<<cnt<<endl;
        if(sum+arr[i]<=val)
        {
            sum+=arr[i];
        }
        else
        {
            sum=arr[i];
            cnt++;
        }
    }
    if(cnt>m)
        return 0;
    else
        return 1;
}
int main()
{
    ll i,j,k,l,test;
    cin>>test;
    for(k=1;k<=test;k++)
    {
        cin>>n>>m;
        ll sum=0,tmp=0;
        for(i=1;i<=n;i++)
        {
            cin>>arr[i];
            sum+=arr[i];
            if(arr[i]>tmp)
                tmp=arr[i];
        }
        ll low,high,mid;
        low=tmp;
        high=sum;
        ll ans;
        while(low<=high)
        {
            mid=(low+high)/2;
            if(bin_s(mid))
            {
                ans=mid;
                high=mid-1;
            }
            else
            {
                low=mid+1;
            }
        }
        cout<<"Case "<<k<<": "<<ans<<endl;
    }
    return 0;
}

UVa 674 - Coin Change

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll table[10000],coin[6];
int main()
{
    ll i,j,k,l,m,n;
    while(cin>>n)
    {
        memset(table,0,sizeof(table));
        coin[1]=1;
        coin[2]=5;
        coin[3]=10;
        coin[4]=25;
        coin[5]=50;
        table[0]=1;
        for(i=1;i<=5;i++)
        {
            for(j=coin[i];j<n+1;j++)
            {
                table[j]=table[j]+table[j-coin[i]];
            }
        }
        cout<<table[n]<<endl;
    }
    return 0;
}

UVa 616 - Coconuts, Revisited

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll>divisors;
void div(ll n)
{
    divisors.clear();
    ll i,j,k,l,m;
    for(i=2;i<=sqrt(n)+1;i++)
    {
        if(n%i==0)
        {
            divisors.push_back(i);
            j=n/i;
            if(i!=j)
            {
                divisors.push_back(j);
            }
        }
    }
    sort(divisors.begin(),divisors.end());
}
int main()
{
    ll i,j,k,l,m,n;
    while(cin>>n)
    {
        if(n<0)
        {
            break;
        }
        else
        {
            cout<<n<<" coconuts, ";
            div(n-1);
            ll num;
            //cout<<num<<endl;
            bool flag=0;
            if(divisors.size()==0)
            {
                cout<<"no solution"<<endl;
                continue;
            }
            for(i=divisors.size()-1;i>=0;i--)
            {
                ll rem=0;
                ll num=n;
                //cout<<divisors[i]<<endl;
                if(flag)
                    break;
                for(j=0;j<divisors[i];j++)
                {
                    num-=rem;
                    //cout<<num<<" "<<rem<<" ";
                    ll r=num%divisors[i];
                    if(num<0)
                    {
                        flag=0;
                        break;
                    }
                    //cout<<r<<" ";
                    if(r!=1)
                    {
                        flag=0;
                        break;
                    }
                    num--;
                    //cout<<num<<" ";
                    if(num%divisors[i]!=0)
                    {
                        flag=0;
                        break;
                    }
                    else
                    {
                        rem=num/divisors[i];
                    }
                }
                //cout<<num<<" "<<rem<<" "<<j<<endl;
                rem=num/divisors[i];
                if(rem%divisors[i]==0&&j==divisors[i])
                {
                    flag=1;
                    cout<<divisors[i]<<" people and 1 monkey"<<endl;
                }
                else
                {
                    flag=0;
                }
            }
            if(!flag)
                cout<<"no solution"<<endl;
        }
    }
    return 0;
}

Detecting cycle in an undirected graph

#include<bits/stdc++.h>
using namespace std;
int i,j,k,l,m,n;
struct edge
{
int u,v;
};
int pr[1009];
vector<edge>e;
int find(int r)
{
   return (pr[r]==r)?r:find(pr[r]);
}
bool cycle(int n)
{
for(i=1;i<=n;i++)
        pr[i]=i;
for(int i=0;i<(int)e.size();i++)
{
int u=find(e[i].u);
int v=find(e[i].v);
if(u!=v)
{
pr[u]=v;
}
else
            return false;
}
return true;
}

int main()
{
cin>>n>>m;
for(i=1;i<=m;i++)
{
int u,v;
cin>>u>>v;
edge get;
get.u=u;
get.v=v;
e.push_back(get);
}
if(cycle(n)==1)
        cout<<"No cycle exists"<<endl;
    else
        cout<<"Cycle exists"<<endl;
return 0;

}

Light Oj 1023 Discovering Permutations

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll i,j,k,l,m,n,test;
    cin>>test;
    for(k=1;k<=test;k++)
    {
        string s="";
        cin>>n>>m;
        char c='A';
        for(i=1;i<=n;i++)
        {
            s=s+c;
            c++;
        }
        cout<<"Case "<<k<<":"<<endl;
        cout<<s<<endl;
        m--;
        while(m--)
        {
            if(next_permutation(s.begin(),s.end()))
            {
                cout<<s<<endl;
            }
            else
                break;
        }
    }
    return 0;
}

Light Oj 1062 Crossed Ladders

#include<bits/stdc++.h>
#define er 1000000
using namespace std;
typedef long long ll;
double x,y,c;
double eqn(double z)
{
    double a=1/(sqrt(x*x-z*z));
    double b=1/(sqrt(y*y-z*z));
    return (a+b);
}
int main()
{
    ll i,j,k,l,m,n,test;
    cin>>test;
    for(k=1;k<=test;k++)
    {
        double mid,l,r;
        cin>>x>>y;
        cin>>c;
        l=0.0;
        r=min(x,y);
        while(r-l>0.0000001)
        {
            mid=(r+l)/2.0;
            //cout<<mid<<endl;
            double tmp=1/c;
            if(eqn(mid)>tmp)
            {
                r=mid;
            }
            else
            {
                l=mid;
            }
        }
        printf("Case %lld: %.10f\n",k,mid);
    }
    return 0;
}

Light Oj 1202 Bishops

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll i,j,k,l,m,n,test;
    cin>>test;
    for(k=1;k<=test;k++)
    {
        ll a,b,c,d;
        cin>>a>>b;
        cin>>c>>d;
        cout<<"Case "<<k<<": ";
        if(abs(a-c)%2!=abs(b-d)%2)
        {
            cout<<"impossible"<<endl;
            continue;
        }
        if(abs(a-c)==abs(b-d))
            cout<<1;
        else
            cout<<2;
        cout<<endl;
    }
    return 0;
}

Light Oj 1042 Secret Origins

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll i,j,k,l,m,n,test;
    cin>>test;
    for(k=1;k<=test;k++)
    {
        cin>>n;
        vector<ll>num;
        while(n)
        {
            ll rem=n%2;
            num.push_back(rem);
            n=n/2;
        }
        num.push_back(0);
        reverse(num.begin(),num.end());
        l=num.size()-1;
        next_permutation(num.begin(),num.end());
        ll sum=0;
        for(i=0,j=l;i<=l,j>=0;i++,j--)
        {
            sum+=num[i]*pow(2,j);
        }
        cout<<"Case "<<k<<": "<<sum<<endl;
    }
    return 0;
}

Light Oj 1138 Trailing Zeroes (III)

#include <bits/stdc++.h>
using namespace std ;
typedef long long ll;
ll count_5(ll num)
{
    ll pow_5=5,counter=0;
    while(pow_5<=num)
    {
        counter+=num/pow_5;
        pow_5*=5;
    }
    //cout<<counter<<endl;
    return counter;
}
ll binary_s(ll n)
{
    int low=0,high=1000000000,mid,ans=0;
    while (low<=high)
    {
        mid=(low+high)/2 ;
        ll tmp=count_5(mid);
        if (tmp<n)
            low=mid+1;
        else if(tmp>n)
            high=mid-1;
        else
        {
            ans=mid;
            high=mid-1;
        }
    }
    return ans ;
}
int main ()
{
    ll i,j,k,l,m,n,test;
    cin>>test;
    for (k=1;k<=test;k++)
    {
        cin>>n;
        ll ans=binary_s(n);
        if(ans==0)
            cout<<"Case "<<k<<": "<<"impossible"<<endl;
        else
            cout<<"Case "<<k<<": "<<ans<<endl;
    }
    return 0 ;
}

UVa 11137 - Ingenuous Cubrency

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll arr[10009];
int main()
{
    ll i,j,k,l,m,n;
    memset(arr,0,sizeof(arr));
    arr[0]=1;
    for(i=1;i<=21;i++)
    {
        for(j=i*i*i;j<=10009;j++)
        {
            arr[j]=arr[j]+arr[j-(i*i*i)];
        }
    }
    while(cin>>n)
    {
        cout<<arr[n]<<endl;
    }
    return 0;
}

Light OJ 1090 Trailing Zeroes (II)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll cnt_p2(ll n)
{
    ll p_2=2,cnt=0;
    while(p_2<=n)
    {
        cnt+=n/p_2;
        p_2*=2;
    }
    return cnt;
}
ll cnt_p5(ll n)
{
    ll p_5=5,cnt=0;
    while(p_5<=n)
    {
        cnt+=n/p_5;
        p_5*=5;
    }
    return cnt;
}
ll cnt_div(ll n,ll ret_val)
{
    ll i=2,j,k,l,m,cnt2=0,cnt5=0;
    while(1)
    {
        if(n%2!=0)
            break;
        else
        {
            cnt2++;
            n=n/2;
        }
    }
    while(1)
    {
        if(n%3!=0)
            break;
        else
        {
            n=n/3;
        }
    }
    while(1)
    {
        if(n%5!=0)
            break;
        else
        {
            cnt5++;
            n=n/5;
        }
    }
    //cout<<cnt2<<" "<<cnt5<<endl;
    if(ret_val==2)
        return cnt2;
    else
        return cnt5;
}
int main()
{
    //cout<<cnt_div(10,5)<<endl;
    ll i,j,k,l,m,n,r,p,q,test,cn,cr,cnr,cp;
    cin>>test;
    for(ll in=1;in<=test;in++)
    {
        cin>>n>>r;
        cin>>p>>q;
        i=cnt_p2(n);
        j=cnt_p5(n);
        k=cnt_p2(r);
        l=cnt_p5(r);
        ll tmp=n-r;
        m=cnt_p2(tmp);
        n=cnt_p5(tmp);
        ll x,y;
        x=cnt_div(p,2)*q;
        y=cnt_div(p,5)*q;
        //cout<<i<<" "<<j<<" "<<k<<" "<<l<<" "<<m<<" "<<n<<" "<<x<<" "<<y<<endl;
        ll ans=min(i-k-m+x,j-l-n+y);
        cout<<"Case "<<in<<": "<<ans<<endl;
    }
    return 0;
}

UVa 11723 - Numbering Roads

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    //ofstream o("op.txt");
    ll i,j,k,l,m,n,num;
    for(k=1;;k++)
    {
        cin>>n>>num;
        if(n==0&&num==0)
            break;
        cout<<"Case "<<k<<": ";
        ll ans;
        bool flag=0;
        for(i=1;i<=27;i++)
        {
            if(num*i>=n)
            {
                ans=i-1;
                flag=1;
                break;
            }
        }
        if(flag)
            cout<<ans<<endl;
        else
            cout<<"impossible"<<endl;
    }
    return 0;
}

UVa 12696 - Cabbin Baggage

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int i,j,k,count=0;
    double test,l,w,d,W;
    cin>>test;
    for(i=1;i<=test;i++)
    {
        cin>>l>>w;
        cin>>d>>W;
        if(((l<=56.0&&w<=45.0&&d<=25.0)||(l+d+w<=125.0))&&(W<=7.0))
        {
            count++;
            cout<<1<<endl;
        }
        else
            cout<<0<<endl;
    }
    cout<<count<<endl;
    return 0;
}

UVa 344 - Roman Digititis

#include<bits/stdc++.h>
using namespace std;
int main()
{
    string a[110];
    string b;
    int i,j,k,l,m,n,x,v,c;
    while(cin>>n)
    {
        if(n==0)
            break;
        else
        {
            i=v=x=c=l=0;
            a[1]="i";
            a[2]="ii";
            a[3]="iii";
            a[4]="iv";
            a[5]="v";
            a[6]="vi";
            a[7]="vii";
            a[8]="viii";
            a[9]="ix";
            a[10]="x";
            a[11]="xi";
            a[12]="xii";
            a[13]="xiii";
            a[14]="xiv";
            a[15]="xv";
            a[16]="xvi";
            a[17]="xvii";
            a[18]="xviii";
            a[19]="xix";
            a[20]="xx";
            a[21]="xxi";
            a[22]="xxii";
            a[23]="xxiii";
            a[24]="xxiv";
            a[25]="xxv";
            a[26]="xxvi";
            a[27]="xxvii";
            a[28]="xxviii";
            a[29]="xxix";
            a[30]="xxx";
            a[31]="xxxi";
            a[32]="xxxii";
            a[33]="xxxiii";
            a[34]="xxxiv";
            a[35]="xxxv";
            a[36]="xxxvi";
            a[37]="xxxvii";
            a[38]="xxxviii";
            a[39]="xxxix";
            a[40]="xl";
            a[41]="xli";
            a[42]="xlii";
            a[43]="xliii";
            a[44]="xliv";
            a[45]="xlv";
            a[46]="xlvi";
            a[47]="xlvii";
            a[48]="xlviii";
            a[49]="xlix";
            a[50]="l";
            a[51]="li";
            a[52]="lii";
            a[53]="liii";
            a[54]="liv";
            a[55]="lv";
            a[56]="lvi";
            a[57]="lvii";
            a[58]="lviii";
            a[59]="lix";
            a[60]="lx";
            a[61]="lxi";
            a[62]="lxii";
            a[63]="lxiii";
            a[64]="lxiv";
            a[65]="lxv";
            a[66]="lxvi";
            a[67]="lxvii";
            a[68]="lxviii";
            a[69]="lxix";
            a[70]="lxx";
            a[71]="lxxi";
            a[72]="lxxii";
            a[73]="lxxiii";
            a[74]="lxxiv";
            a[75]="lxxv";
            a[76]="lxxvi";
            a[77]="lxxvii";
            a[78]="lxxviii";
            a[79]="lxxix";
            a[80]="lxxx";
            a[81]="lxxxi";
            a[82]="lxxxii";
            a[83]="lxxxiii";
            a[84]="lxxxiv";
            a[85]="lxxxv";
            a[86]="lxxxvi";
            a[87]="lxxxvii";
            a[88]="lxxxviii";
            a[89]="lxxxix";
            a[90]="xc";
            a[91]="xci";
            a[92]="xcii";
            a[93]="xciii";
            a[94]="xciv";
            a[95]="xcv";
            a[96]="xcvi";
            a[97]="xcvii";
            a[98]="xcviii";
            a[99]="xcix";
            a[100]="c";
            for(j=1;j<=n;j++)
            {
                b=a[j];
                for(k=0;k<b.size();k++)
                {
                    if(b[k]=='i')
                        i++;
                    if(b[k]=='v')
                        v++;
                    if(b[k]=='x')
                        x++;
                    if(b[k]=='l')
                        l++;
                    if(b[k]=='c')
                        c++;
                }
            }
            cout<<n<<": "<<i<<" i, "<<v<<" v, "<<x<<" x, "<<l<<" l, "<<c<<" c"<<endl;
        }
    }
    return 0;
}

UVa 821 - Page Hooping

#include<bits/stdc++.h>
#define mx 1000
#define inf 1e18
#define nil -999999999
using namespace std;
typedef long long ll;
ll graph[mx][mx];
ll path[mx][mx],N;
void fl_wr()
{
    ll i,j,k,l,m,n;
    for(k=1;k<=N;k++)
    {
        for(i=1;i<=N;i++)
        {
            for(j=1;j<=N;j++)
            {
                graph[i][j]=min(graph[i][j],graph[i][k]+graph[k][j]);
            }
        }
    }
}
int main()
{
    ll i,j,k=0,l,m,n;
    while(1)
    {
        k++;
        for(i=0;i<mx;i++)
        {
            for(j=0;j<mx;j++)
            {
                graph[i][j]=inf;
            }
        }
        for(i=1;i<mx;i++)
        {
            graph[i][i]=0;
        }
        ll a,b;
        N=0;
        cin>>a>>b;
        N=max(max(a,b),N);
        if(a==0&&b==0)
            break;
        else
        {
            graph[a][b]=1;
            while(1)
            {
                ll a,b;
                cin>>a>>b;
                N=max(max(a,b),N);
                if(a==0&&b==0)
                    break;
                else
                {
                    graph[a][b]=1;
                }
            }
            fl_wr();
            ll sum=0,d=0;
            for(i=1;i<=N;i++)
            {
                for(j=1;j<=N;j++)
                {
                    if(graph[i][j]!=inf&&graph[i][j]!=0)
                    {
                        d++;
                        sum+=graph[i][j];
                    }
                }
            }
            double x,y;
            x=sum;
            y=d;
            printf("Case %lld: average length between pages = ",k);
            printf("%.3lf clicks\n",x/y);
        }
    }
    return 0;
}