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;
}