UVA 147 - Dollars

#include<bits/stdc++.h>
using namespace std;
long long coin[]= {10000,5000,2000,1000,500,200,100,50,20,10,5};
long long  dp[12][30005];
long long  c;
long long  func(long long  i,long long  w)
{
    if(i>=11)
    {
        if(w==0)
            return 1;
        else
            return 0;
    }
    if(dp[i][w]!=-1)
        return dp[i][w];
    long long  p1=0,p2=0;
    if(w-coin[i]>=0)
        p1=func(i,w-coin[i]);
    p2=func(i+1,w);
    return dp[i][w]=p1+p2;

}
int main()
{
    long long  x,y;
    char ch;
    memset(dp,-1,sizeof(dp));
    while(cin>>x>>ch>>y)
    {
        long long n,n1;
        if(x==0&&y==0)
            break;
        else
        {
            n=x*100+y;
            {
                n1=func(0,n);
                printf("%3lld.%.2lld%17lld\n",x,y,n1);
            }
        }

    }
    return 0;

}

Upper bound by using binary search

#include<bits/stdc++.h>
using namespace std;
#define fr(i,x) for(i=0;i<x;i++)
int binaryupper(int a[],int m,int l,int u)
{
    int mid,c=0;
    if(l<=u)
    {
        mid=(l+u)/2;
        if(m==a[mid])
        {
            c=m;
            return binaryupper(a,m,mid+1,u);
        }
        else if(m<a[mid])
        {
            return binaryupper(a,m,l,mid-1);
        }
        else
        {
            return binaryupper(a,m,mid+1,u);
        }
    }
    else
        return u;
}
int main()
{
    int n;
    while(cin>>n)
    {
        int ar[100010]= {0},i,a;
        fr(i,n)
        {
            cin>>ar[i];
        }
        cin>>a;
        cout<<binaryupper(ar,a,0,n-1)<<endl;
    }
}

Lower bound by using binary search

#include<bits/stdc++.h>
using namespace std;
#define fr(i,x) for(i=0;i<x;i++)
int binarylower(int a[],int m,int l,int u)
{
int mid,c=0;
    if(l<=u)
{
      mid=(l+u)/2;
      if(m==a[mid])
      {
c=m;
        return binarylower(a,m,l,mid-1);
      }
      else if(m<a[mid])
{
          return binarylower(a,m,l,mid-1);
      }
      else
{
return binarylower(a,m,mid+1,u);
        }
    }
    else
        return l;
  }

int main()
{
    int n;
    while(cin>>n)
    {
        int ar[100010]={0},i,a;
        fr(i,n)
        {
            cin>>ar[i];
        }
        cin>>a;
        cout<<binarylower(ar,a,0,n-1)<<endl;
    }
}

UVA 1121 - Subsequence

#include <bits/stdc++.h>
using namespace std;
main()
{
    long long n,s;
    while(cin>>n>>s)
    {
        long long ar[100010]= {0},high=0,low=0,ans=n+1,i,sum=0,temp=0;
        for(i=0; i<n; i++)
        {
            cin>>ar[i];
        }
        sum=ar[0];
        while(high<n)
        {
            if(sum<s)
            {
                high++;
                if(high<n)
                {
                    sum+=ar[high];
                }
            }
            if(sum>=s)
            {
                temp=high-low+1;
                if(ans>temp)
                {
                    ans=temp;
                }
            }
            if(sum>=s&&high>low)
            {
                sum-=ar[low];
                low++;
            }
        }
        if(ans==n+1)
        {
            cout<<0<<endl;
        }
        else
            cout<<ans<<endl;
    }
}

Path from 1 to any other node

Problem link: http://codeforces.com/contest/839/problem/C
Problem code :
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define ull unsigned long long int
#define inf (INT_MAX/10)
#define linf (LLONG_MAX/10LL)
#define sc(a) scanf("%d",&a)
#define sc2(a,b) scanf("%d%d",&a,&b)
#define sc3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define sc4(a,b,c,d) scanf("%d%d%d%d",&a,&b,&c,&d)
#define fl(c,i,n) for(i=c;i<n;i++)
#define f(i,n) for(i=0;i<n;i++)
#define mem(a) memset(a,0,sizeof(a))
#define memn(a) memset(a,-1,sizeof(a))
#define pb push_back
#define aov(a) a.begin(),a.end()
#define mpr make_pair
#define PI (2.0*acos(0.0)) //#define PI acos(-1.0)
#define xx first
#define yy second
#define mxv(a) *max_element(aov(a))
#define mnv(a) *min_element(aov(a))
#define LB(a,x) (lower_bound(aov(a),x)-a.begin())
#define UB(a,x) (upper_bound(aov(a),x)-a.begin())
#define to_c_string(a) a.c_str()
#define strtoint(c) atoi(&c[0])
#define pll pair< ll , ll >
#define pii pair< int , int >
#define pcs(a) printf("Case %d: ", a)
#define nl puts("")
#define endl '\n'
#define dbg(x) cout<<#x<<" : "<<x<<endl
#define M  100005
#define MD 1000000LL
#define MX 1000005
int n;
vector< int >al[M];
double p[M];

void dfs(int u,int par)
{
p[u]=0;
int i;
int cnt=0;
f(i,al[u].size())
{
int v=al[u][i];
if(v==par)continue;
dfs(v,u);
p[u]+=p[v]+1;
cnt++;
}
if(cnt)p[u]/=cnt;
}

int main()
{
    int t,i,j,k;

    sc(n);
    fl(1,i,n)
    {
sc2(j,k);
al[j].pb(k);
al[k].pb(j);
}
dfs(1,-1);
printf("%.12lf\n",p[1]);


return 0;
}

UVA 11933 - Splitting Numbers

#include<bits/stdc++.h>
using namespace std;
main()
{
    long n;
    while(cin>>n)
    {
        long a=0,b=0,i=0,k=0,x=0;
        if(n==0)
            break;
        else
        {
            while(n!=0)
            {
                k=n%2;
                if(k%2==1)
                {
                    if(x%2==0)
                    {
                        a+=(1<<i);
                    }
                    else
                    {
                        b+=(1<<i);
                    }
                    x++;
                }
                i++;
                n/=2;
            }
            cout<<a<<" "<<b<<endl;
        }
    }
}

UVA 12650 - Dangerous Dive

#include<bits/stdc++.h>
using namespace std;
main()
{
    int n,r;
    while(scanf("%d%d",&n,&r)!=EOF)
    {
        int ar[15000]={0},i,j;
        for(i=0;i<r;i++)
        {
            scanf("%d",&ar[i]);
        }
        sort(ar,ar+r);
        if(n==r)
            printf("*\n");
        else
        {
            j=0;
            for(i=1;i<=n;i++)
            {
                if(i!=ar[j])
                    printf("%d ",i);
                    else
                    j++;
            }
            printf("\n");
        }
    }
    return 0;
}