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