Solution of Light OJ 1029-Civil and Evil Engineer

/* Bismillahir Rahmanir Rahim Solution using MST(Kruskal's algorithm) */ #include<bits/stdc++.h> #define fi(n, m) for(int i=n; i<=m; i++) #define fd(n, m) for(int i=n; i>=m; i--) using namespace std; int x, pr[105], n; struct edge{ int u, v, w; }one[12005]; bool comp(edge f, edge s){ return f.w<s.w; } int find(int p){ if(pr[p]==p) return p; else return find(pr[p]); } int mst(int st){ int cnt=0, sm=0, xx, yy; fi(0, n)pr[i]=i; fi(0, x-1){ xx=find(one[i].u); yy=find(one[i].v); if(xx!=yy){ cnt++; sm+=one[i].w; pr[yy]=xx; } if(cnt==n) break; } return sm; } int mxst(int st){ int cnt=0, sm=0, xx, yy; fi(0, n)pr[i]=i; fd(x-1, 0){ xx=find(one[i].u); yy=find(one[i].v); if(xx!=yy){ cnt++; pr[yy]=xx; sm+=one[i].w; } if(cnt==n) break; } return sm; } int main(){ int t, cs=1, u, v, w, up, dwn; cin>>t; while(t--){ cin>>n; x=0; while(1){ cin>>u>>v>>w; if(u==0&&v==0&&w==0) break; one[x].u=u; one[x].v=v; one[x].w=w; x++; } sort(one, one+x, comp); up=mxst(0); dwn=mst(0); cout<<"Case "<<cs++<<": "; if((up+dwn)%2==0) cout<<(up+dwn)/2<<endl; else cout<<up+dwn<<"/"<<2<<endl; } return 0; }

Solution of Light OJ 1002-Country Roads

/* Bismillahir Rahmanir Rahim Solution using BFS algorithm */ #include<bits/stdc++.h> #define fi(n, m) for(int i=n; i<=m; i++) #define fd(n, m) for(int i=n; i>=m; i--) #define inf 100009 using namespace std; vector<int>vt[505], cost[505]; int dis[505]={0}; void bfs(int st){ queue<int>q; q.push(st); dis[st]=0; int p, sz, temp, xx; while(!q.empty()){ p=q.front(); q.pop(); sz=vt[p].size(); fi(0, sz-1){ xx=vt[p][i]; temp=max(dis[p], cost[p][i]); if(temp<dis[xx]){ dis[xx]=temp; q.push(xx); } } } } int main(){ int t, cs=1, n, m, u, v, w, tt; cin>>t; while(t--){ cin>>n>>m; fi(0, m-1){ cin>>u>>v>>w; vt[u].push_back(v); vt[v].push_back(u); cost[u].push_back(w); cost[v].push_back(w); } cin>>tt; fi(0, n-1) dis[i]=inf; bfs(tt); cout<<"Case "<<cs++<<":"<<endl; fi(0, n-1){ if(dis[i]==inf)cout<<"Impossible"<<endl; else cout<<dis[i]<<endl; } fi(0, n-1){ vt[i].clear(); cost[i].clear(); } } return 0; }

Kruskal's Algorithm - Implementation with C++

/* Bismillahir Rahmanir Rahim Implementation of (MST)Kruskal's algorithm with C++ */ #include<bits/stdc++.h> #define fi(i, n) for(int i=0; i<n; i++) using namespace std; struct node{ // structure int u, v, cost; }; int pr[101], edge, n; node one[100]; bool comp(node f, node s){ // sort of structure return f.cost<s.cost; } int find(int p){ // Disjoint Set if(pr[p]==p)return p; else return find(pr[p]); } int mst(int st){ // minimum-cost spanning tree fi(i, n) pr[i]=i; int cnt=0, xx, sm=0, yy; fi(i, edge){ xx=find(one[i].u); // parent of one[i].u yy=find(one[i].v); if(xx!=yy){ pr[yy]=xx; cnt++; sm+=one[i].cost; } if(cnt==n-1) break; } return sm; } int main(){ int u, v, cost; /* input start */ cin>>n>>edge; fi(i, edge){ cin>>u>>v>>cost; one[i].u=u; one[i].v=v; one[i].cost=cost; } sort(one, one+edge, comp); cout<<mst(1)<<endl; return 0; }

BFS Algorithm - Implementation with C++

/* Bismillahir Rahmamir Rahim Implementing BFS algorithm with c++ */ #include<bits/stdc++.h> using namespace std; vector<int>vt[100]; queue<int>q; int cost[100][100], dis[100], visit[100]; void bfs(int st){ for(int i=0; i<=100; i++){ dis[i]=100009, visit[i]=0; } int p, y, cst; dis[st]=0; q.push(st); while(!q.empty()){ p=q.front(); q.pop(); if(!visit[p]){ for(int i=0; i<vt[p].size(); i++){ y=vt[p][i]; cst=cost[p][y]+dis[p]; if(cst<dis[y]){ dis[y]=cst; q.push(y); } } visit[p]=1; } } } int main(){ int n1, n2, edge, c, x; cin>>edge; for(int i=0; i<edge; i++){ cin>>n1>>n2>>c; vt[n1].push_back(n2); vt[n2].push_back(n1); cost[n1][n2]=cost[n2][n1]=c; } bfs(1); while(cin>>x) cout<<dis[x]<<endl; return 0; }

Solution of Light OJ 1067-Combinations

See the problem Light OJ 1067

#include<bits/stdc++.h> #define ll long long using namespace std; ll n, r, t, i, ans, cs=1, up, dwn, fac[1000009]; const ll mod=1000003; ll bigmod(ll b, ll p){ if(p==0) return 1; ll x=bigmod(b, p/2); x=(x*x)%mod; if(p%2==1)x=(x*b)%mod; return x; } int main(){ fac[0]=1; for(i=1; i<=1000000; i++){ fac[i]=(fac[i-1]*i)%mod; } cin>>t; while(t--){ cin>>n>>r; up=fac[n]; dwn=(fac[n-r]*fac[r])%mod; ans=up*bigmod(dwn, mod-2); cout<<"Case "<<cs++<<": "<<ans%mod<<endl; } return 0; }

Solution of Light OJ 1028 -Trailing Zeroes (I)

#include<bits/stdc++.h>
#define ll long long
using namespace std;

ll t, n, m, i, j, ans, prime[1000009], num[1000009]={0}, cnt, cs=1;

void seive(){
    for(i=3; i*i<=1000000; i+=2){
        if(num[i]==0){
            for(j=i*i; j<=1000000; j=j+(i*2)) num[j]=1;
        }
    }
    prime[0]=2;
    j=1;
    for(i=3; i<=1000000; i+=2){
        if(num[i]==0) prime[j++]=i;
    }
}

int main(){
    seive();
    scanf("%lld", &t);

    while(t--){
        cin>>n;
        ans=1;
        for(i=0; i<j&&prime[i]*prime[i]<=n; i++){
            cnt=0;
            while(n%prime[i]==0){
                cnt++;
                n=n/prime[i];
            }
            ans=ans*(cnt+1);
        }

        if(n!=1)ans=ans*2;
        cout<<"Case "<<cs++<<": "<<ans-1<<endl;

    }
    return 0;
}

Solution of UVa-11029 Leading and Trailing

#include<bits/stdc++.h>

#define ll long long

using namespace std;

ll n, k, t_case;

ll bigmod(ll b, ll p, ll m){

    if(p==0)return 1;

    ll xx=bigmod(b, p/2, 1000);

    xx=(xx*xx)%1000;

    if(p%2==1)xx=(xx*b)%1000;

    return xx;
}

int main(){

    cin>>t_case;

    while(t_case){

        cin>>n>>k;

        /* executing first 3 digits */

        double x=k*(log10(n));

        x=x-(int)x; // taking fraction value only
        

        double ans=pow(10, x);

        ans=ans*100;

        cout<<(int)ans<<"...";

        /* executing last 3 digits */

        printf("%03d\n", bigmod(n, k, 1000));

        t_case--;

    }

    return 0;
}