Solution of UVa 10048 Audiophobia

/* Bismillahir Rahmanir Rahim Solution-Using BFS */ #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[105], cost[105]; int dis[105], zz; 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, q, ans; while(1){ cin>>n>>m>>q; if(n==0&&m==0&&q==0)break; if(cs!=1)cout<<endl; 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); } cout<<"Case #"<<cs++<<endl; while(q--){ fi(1, n) dis[i]=inf; cin>>tt>>zz; bfs(tt); if(dis[zz]==inf)cout<<"no path"<<endl; else cout<<dis[zz]<<endl; } fi(0, n){ vt[i].clear(); cost[i].clear(); } } return 0; }

Solution of UVa 821 Page Hopping

/* Bismillahir Rahmanir Rahim Solution-Using "Floyd Warshall" */ #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 ll long long using namespace std; set<ll>st; ll dis[101][101]; int main(){ ll n, e, u, v, w, cs=1, mx, sum, sz; float ans; while(1){ mx=0, sum=0; for(ll i=1; i<=100; i++){ for(ll j=1; j<=100; j++){ if(i==j)dis[i][j]=0; else dis[i][j]=1000000009; } } cin>>u>>v; if(u==0&&v==0) break; else{ st.insert(u); st.insert(v); mx=max(mx, max(u, v)); dis[u][v]=1; while(1){ cin>>u>>v; if(u==0&&v==0) break; else{ st.insert(u); st.insert(v); mx=max(mx, max(u, v)); dis[u][v]=1; } } } for(ll k=1; k<=mx; k++){ for(ll i=1; i<=mx; i++){ for(ll j=1; j<=mx; j++){ dis[i][j]=min(dis[i][j], (dis[i][k]+dis[k][j])); } } } for(ll i=1; i<=mx; i++){ for(ll j=1; j<=mx; j++){ if(dis[i][j]!=1000000009) sum=sum+dis[i][j]; } } sz=st.size(); sz=sz*(sz-1); ans=(double)sum/sz; cout<<"Case "<<cs++<<": average length between pages = "; printf("%.3f clicks\n", ans); st.clear(); } return 0; }

Solution of UVa 11015 - 05-2 Rendezvous

/* Bismillahir Rahmanir Rahim Solution-Using "Floyd Warshall" */ #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 main(){ int cs=1, n, u, v, w, m; string s; while(1){ int i, j, k, dis[25][25], ans, sum, mn=1000000009; map<int, string>mp; cin>>n>>m; if(n==0) break; fi(1, n){ cin>>s; mp[i]=s; } for(i=1; i<=n; i++){ for(j=1; j<=n; j++){ if(i==j)dis[i][j]=0; else dis[i][j]=1000000009; } } fi(0, m-1){ cin>>u>>v>>w; dis[u][v]=dis[v][u]=w; } for(k=1; k<=n; k++){ for(i=1; i<=n; i++){ for(j=1; j<=n; j++){ dis[i][j]=min(dis[i][j], (dis[i][k]+dis[k][j])); } } } for(i=1; i<=n; i++){ sum=0; for(j=1; j<=n; j++){ sum=sum+dis[i][j]; } if(mn>sum){ mn=sum; ans=i; } } cout<<"Case #"<<cs++<<" : "<<mp[ans]<<endl; } return 0; }

Solution of 10246 Asterix and Obelix

"All pair shortest path" বের করার সময় শুধুমাত্র path এর cost দেওয়া থাকে আর তার উপর ভিত্তি করে ans বের করতে হয়। কিন্তু এখানে শুধু path এর cost না, সাথে সেই path এর maximum node cost নিবে । অর্থাৎ two dimensional purpose। এই ক্ষেত্রে দুইবার Floyd Warshall প্রয়োগ করতে হবে। 

/* Bismillahir Rahmanir Rahim Just apply "Floyd Warshall" algorithm two times */ #include<bits/stdc++.h> #define fi(n, m) for(int i=n; i<=m; i++) #define fd(n, m) for(int i=n; i>=ml i--) #define inf 100000000 using namespace std; int main(){ int cs=1, n, m, r, u, v, w, q, tcost; while(1){ int total, x, dis[90][90], c[90][90]; cin>>n>>m>>q; if(n==0&&m==0&&q==0) break; for(int i=1; i<=n; i++){ for(int j=1; j<=n; j++){ if(i==j) dis[i][j]=0; else dis[i][j]=inf; c[i][j]=inf; } } fi(1, n){ cin>>x; c[i][i]=x; } fi(1, m){ cin>>u>>v>>w; dis[u][v]=w; dis[v][u]=w; c[u][v]=c[v][u]=max(c[u][u], c[v][v]); } for(int k=1; k<=n; k++){ for(int i=1; i<=n; i++){ for(int j=1; j<=n; j++){ total=dis[i][k]+dis[k][j]; tcost=max(c[i][k], c[k][j]); if(dis[i][j]+c[i][j]>total+tcost){ dis[i][j]=total; c[i][j]=tcost; } } } } for(int k=1; k<=n; k++){ for(int i=1; i<=n; i++){ for(int j=1; j<=n; j++){ total=dis[i][k]+dis[k][j]; tcost=max(c[i][k], c[k][j]); if(dis[i][j]+c[i][j]>total+tcost){ dis[i][j]=total; c[i][j]=tcost; } } } } if(cs!=1)cout<<endl; cout<<"Case #"<<cs++<<endl; fi(1, q){ cin>>u>>v; if(dis[u][v]>=inf) cout<<-1<<endl; else cout<<dis[u][v]+c[u][v]<<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;
}

Solution of UVa 11488-Hyper Prefix Sets

See the problem UVa-11488

 

>>>This problem has been solved using "Trie". So if you don't known with "Trie", you should not try to understand this solution.<<<

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll cur, last, ss, sss, ans, mx;
string s;

struct node{
    int next[2];
    long long cnt;
}ar[10000009];

void new_trie(int cur){
    ar[cur].next[0]=-1;
    ar[cur].next[1]=-1;
    ar[cur].cnt=1;
}

int insrt(){
    ss=s.size(), cur=0;
    for(int k=0; k<ss; k++){
        int x=(int)s[k]-48;
        if(ar[cur].next[x]==-1){
            ar[cur].next[x]=last;
            new_trie(last++);
            cur=ar[cur].next[x];
        }
        else{
            cur=ar[cur].next[x];
            ar[cur].cnt++;
            mx=(k+1)*ar[cur].cnt;
            ans=max(mx, ans);
        }
    }
    sss=max(ss, sss);
}

int main(){
    long long t, n;
    cin>>t;
    while(t--){
        ans=0, mx=0, last=1, sss=0;
        new_trie(0);
        cin>>n;
        while(n--){
            cin>>s;
            insrt();
        }
        cout<<max(ans, sss)<<endl;
    }
    return 0;
}

Solution of UVa 11362-Phone List

See the problem  UVa-11362

#include<bits/stdc++.h> using namespace std; long long n, t, i, last=1, cur, k, x, fl; string s; struct node{ bool endmark; int next[11]; }r[100009]; void new_trie(int cur){ for(int zz=0; zz<10; zz++){ r[cur].next[zz]=-1; } r[cur].endmark=false; } void insrt(){ cur=0, k=s.size(); for(int z=0; z<k; z++){ x=(int)s[z]-48; if(r[cur].next[x]==-1){ r[cur].next[x]=last; new_trie(last++); cur=r[cur].next[x]; } else{ cur=r[cur].next[x]; if(r[cur].endmark==true)fl=1; if(z==k-1) fl=1; } if(fl==1) break; } r[cur].endmark=true; } int main(){ cin>>t; while(t--){ cin>>n; fl=0, last=1; new_trie(0); for(i=0; i<n; i++){ cin>>s; insrt(); } if(fl==1) cout<<"NO"<<endl; else cout<<"YES"<<endl; } return 0; }