UVA 11770 - Lighting Away

#include<bits/stdc++.h>
using namespace std;
#define mx 50000*3
long vis[mx];
vector<long>vec[mx];
void dfs(long u)
{
    vis[u]=1;
    for(long i1=0;i1<vec[u].size();i1++)
    {
        if(vis[vec[u][i1]]==0)
        dfs(vec[u][i1]);
    }
}
int main()
{
    long ts,cs=1;
    cin>>ts;
    while(ts--)
    {
        memset(vis,0,sizeof(vis));
        long node,edge,i,a,b,cnt=0;
        cin>>node>>edge;
        for(i=1;i<=edge;i++)
        {
            cin>>a>>b;
            vec[a].push_back(b);
        }
        vector<long>tostore;
        for(i=1;i<=node;i++)
        {
            if(vis[i]==0)
            {
                dfs(i);
                tostore.push_back(i);
            }
        }
        memset(vis,0,sizeof(vis));
        for(i=tostore.size()-1;i>=0;i--)
        {
            if(vis[tostore[i]]==0)
            {
                dfs(tostore[i]);
                cnt++;
            }
        }
        printf("Case %ld: %ld\n",cs++,cnt);
        for(i=0;i<=node;i++)
        {
            vec[i].clear();
        }
        tostore.clear();
    }
}

UVA 11876 - N + NOD (N)

#include<bits/stdc++.h>
using namespace std;
long divisor[1000010],ar[1000010]={0},tot;
void divisors()
{
    long i,j;
    for(i=1;i<=1000000;i++)
    {
        for(j=i;j<=1000000;j+=i)
            divisor[j]++;
    }
}
long binarysearch(long start,long ennd,long ele)
{
    while(start<ennd)
    {
        long mid=(start+ennd)/2;
        if(ele==ar[mid])
            return mid;
        else if(ele==ar[start])
            return start;
        else if(ele==ar[ennd])
            return ennd;
        else if(ele>ar[mid])
        {
            start=mid+1;
        }
        else if(ele<ar[mid])
        {
            ennd=mid-1;
        }
    }
    return start;
}
void nod()
{
    memset(ar,0,sizeof(ar));
    ar[0]=1;
    ar[1]=2;
    ar[2]=4;
    long i;
    for(i=3;ar[i-1]<1000010;i++)
    {
        ar[i]=ar[i-1]+divisor[ar[i-1]];
        tot=i;
    }
}
int main()
{
    divisors();
    nod();
    long ts,cs=1;
    cin>>ts;
    while(ts--)
    {
        long fst,scnd,a,b;
        cin>>a>>b;
        fst=binarysearch(0,tot,a);
        scnd=binarysearch(0,tot,b);
        if(ar[fst]<a)
            fst++;
        if(ar[scnd]>b)
            scnd--;
        printf("Case %ld: %ld\n",cs++,scnd-fst+1);
    }
}

UVA 10290 - {Sum+=i++} to Reach N

#include <bits/stdc++.h>
using namespace std;
#define sze 10000100
bool vis[sze];
vector<long long>ar;
void sieve()
{
    long long i,j;
    for(i=3; i<sze; i+=2)
    {
        if(vis[i]==0)
        {
            ar.push_back(i);
            for(j=2*i; j<sze; j+=(i))
            {
                vis[j]=1;
            }
        }
    }
}
long long check(long long a)
{
    long long ans=1,i1,xx=sqrt(a);
    while(a%2==0)
    {
        a/=2;
    }
    for(i1=0; ar[i1]<=xx&&i1<ar.size(); i1++)
    {
        if(a%ar[i1]==0)
        {
            long long cnt=0;
            while(a%ar[i1]==0)
            {
                a/=ar[i1];
                cnt++;
            }
            ans*=(cnt+1);
        }
        xx=sqrt(a);
    }
    if(a>1)
    {
        ans*=2;
    }
    return ans-1;
}
int main()
{
    sieve();
    long long n;
    while(cin>>n)
    {
        if(n>=3)
        printf("%lld\n",check(n)+1);
        else
            printf("1\n");
    }
    return 0;
}

UVA 10664 - Luggage

#include<bits/stdc++.h>
using namespace std;
long ar[110]= {0},tot=0,sum=0,dp[50][3000];
#define sf(a) scanf("%ld",&a)
long call(long i,long wt)
{
    if(i>tot)
        return 0;
    if(wt==sum/2)
        return 1;
    if(dp[i][wt]!=-1)
        return dp[i][wt];
    long ans=0;
    ans=ans|call(i+1,wt+ar[i]);
    ans=ans|call(i+1,wt);
    return dp[i][wt]=ans;
}
int main()
{
    long ts,num;
    string line;
    sf(ts);
    getchar();
    while(ts--)
    {
        getline(cin,line);
        stringstream ss;
        ss<<line;
        int cnt=0;
        sum=0;
        memset(dp,-1,sizeof(dp));
        while(ss>>num)
        {
            ar[cnt++]=num;
            sum+=num;
        }
        tot=cnt-1;

        if(sum%2==0)
        {
            // cout<<call(0,0);
            if(call(0,0))
                printf("YES\n");
            else
                printf("NO\n");
        }
        else
            printf("NO\n");
    }
    return 0;
}

UVa 10692 - Huge Mods

// Theory: a ^ ( b % phi[m]) + phi[m]
// suppose, m=53, n=3, and a1=2, a2=3 and a3=2; then: m=53, m1=phi[m]=52, m2=phi[m1]=24;
// we know: 2 ^ 3 ^ 2 % m ; that means it will be 2 ^ 3 ^ 2 ^ 1
// We have to start from the last, so: ans1 = (2 ^ 1 % m2) + m2=26; which is mod(2 , ans, m2), ans=1 here;
// ans2 = (( 3 ^ ans1) % m1) + m1 = 61; which is mod(3 , ans, m1), ans=ans1;
// main_ans = (2 ^ ans2) % m=35; which is mod(2 , ans, m), ans = ans2;

#include<bits/stdc++.h>
using namespace std;
#define sze 10010
char s[sze];
long phi[sze],vis[sze],i1,j;
void euler_phi()
{
    for(i1=1; i1<=sze; i1++)
        phi[i1]=i1;
    for(i1=2; i1<=sze; i1++)
    {
        if(vis[i1]==0)
        {
            for(j=i1; j<=sze; j+=i1)
            {
                phi[j]=(phi[j]/i1)*(i1-1);
                vis[j]=1;
            }
        }
    }
}
long bigmod(long base,long power,long mod)
{
    if(power==0)
        return 1;
    else if(power%2==0)
    {
        long xx=bigmod(base,power/2,mod);
        return ((xx%mod)*(xx%mod))%mod;
    }
    else
    {
        return ((base%mod)*(bigmod(base,power-1,mod)%mod))%mod;
    }
}
main()
{
    euler_phi();
    long cs=1;
    while(cin>>s)
    {
        if(s[0]=='#')
            break;
        else
        {
            long x=atoi(s),ar[10010]={0},ar1[10010]={0},n,x2,i;
            x2=x;
            cin>>n;
            for(i=1;i<=n;i++)
            {
                cin>>ar[i];
            }
            ar1[1]=x2;
            for(i=2;i<=n;i++)
            {
                x2=phi[x2];
                ar1[i]=x2;
            }
            long ans=1;
            for(i=n;i>=2;i--)
            {
                ans=bigmod(ar[i],ans,ar1[i]);
                ans+=ar1[i];
            }
            ans=bigmod(ar[1],ans,ar1[1]);
            printf("Case #%ld: %ld\n",cs++,ans);
        }
    }
}

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