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

Floyd Warshall Algorithm

#include<bits/stdc++.h>
#define mx 1000
#define inf 1e8
using namespace std;
typedef long long ll;
ll graph[mx][mx];
int main()
{
    ll i,j,k,l,m,n,edge,node;
    cin>>edge>>node;
    for(i=0;i<mx;i++)
    {
        for(j=0;j<mx;j++)
        {
            graph[i][j]=inf;
        }
    }
    for(i=1;i<=edge;i++)
    {
        graph[i][i]=0;
    }
    for(i=1;i<=edge;i++)
    {
        ll a,b,cost;
        cin>>a>>b;
        cin>>cost;
        graph[a][b]=cost;
    }
    for(k=1;k<=node;k++)
    {
        for(i=1;i<=node;i++)
        {
            for(j=1;j<=node;j++)
            {
                graph[i][j]=min(graph[i][j],graph[i][k]+graph[k][j]);
            }
        }
    }
    for(i=1;i<=node;i++)
    {
        for(j=1;j<=node;j++)
        {
            if(graph[i][j]!=inf)
            {
                cout<<i<<" "<<j<<" "<<graph[i][j]<<endl;
            }
        }
    }
   
    return 0;
}

Light OJ 1019 (Brush (V))

#include<bits/stdc++.h>
#define mx 1000000
#define inf 1e8
using namespace std;
typedef long long ll;
ll dist[mx];
list<pair<ll,ll> > *graph;
void dijksra(ll root)
{
    set<pair<ll,ll> >pq;
    set<pair<ll,ll> > :: iterator it;
    ll u,v,w,wt;
    list<pair<ll,ll> > :: iterator i;
    dist[root]=0;
    pq.insert(pair<ll,ll>(0,root));
    while(pq.size()!=0)
    {
        it=pq.begin();
        u=it->second;
        pq.erase(it);
        for(i=graph[u].begin();i!=graph[u].end();i++)
        {
            v=i->first;
            wt=i->second;
            if(dist[v]>dist[u]+wt)
            {
                if(dist[v]!=inf)
                {
                    pq.erase(pq.find(pair<ll,ll>(dist[v],v)));
                }
                dist[v]=dist[u]+wt;
                pq.insert(pair<int,int>(dist[v],v));

            }
        }
    }
}
void add(ll src,ll des,ll wt)
{
    pair<ll,ll>x;
    x.first=des;
    x.second=wt;
    graph[src].push_front(x);
    x.first=src;
    x.second=wt;
    graph[des].push_front(x);
    //cout<<111<<endl;
}
int main()
{
    ll i,j,k,l,m,n,test,edge,node,cs=1;
    cin>>test;
    while(test--)
    {
        cin>>node>>edge;
        for(i=0;i<mx;i++)
        {
            dist[i]=inf;
        }
        graph=new list<pair<ll,ll> > [node+1];
        for(i=0;i<edge;i++)
        {
            ll src,dest,wt;
            cin>>src>>dest>>wt;
            add(src,dest,wt);
        }
        ll start,stop;
        start=1;
        stop=node;
        dijksra(start);
        cout<<"Case "<<cs<<": ";
        if(dist[stop]!=inf)
        {
            cout<<dist[stop]<<endl;
        }
        else
        {
            cout<<"Impossible"<<endl;
        }
        cs++;
    }
    return 0;
}