Uva 572 – Oil Deposits

Problem Link Solution :- Oil Deposits C++ /****************************************************************** *** Problem : *** *** Author : Shipu Ahamed (Psycho Timekiller) *** *** E-mail : shipuahamed01@gmail.com *** *** University : BUBT,Dept. of CSE *** *** Team : BUBT_Psycho *** *** My Blog : http://shipuahamed.blogspot.com *** *** Facebook : http://www.facebook.com/DeesheharaShipu *** ******************************************************************/ #include <bits/stdc++.h> using namespace std; #define ll long long #define pi 2*acos(0.0) #define all(v) v.begin(),v.end() //input #define si(t) scanf("%d",&t) #define sl(t) scanf("%lld",&t) #define sf(t) scanf("%f",&t) #define sdb(t) scanf("%lf",&t) #define schar(c) scanf("%c",&c) #define sstring(s) scanf("%s",s) #define ssi(a,b) scanf("%d%d",&a,&b) #define ssl(a,b) scanf("%lld%lld",&a,&b) //Output #define P(a) printf("%d\n",a) #define PL(a) printf("%lld\n",a) #define PF(a) printf("%f\n",a) #define PDB(a) printf("%lf\n",a) #define PN(a) printf("%d ",a) #define PLN(a) printf("%lld ",a) #define PFN(a) printf("%f ",a) #define PDBN(a) printf("%lf ",a) #define CP(a) cout<<a<<endl #define CPN(a) cout<<a<<" " //Test Case & New line #define Case(no) printf("Case %d: ",++no) #define nl puts("") #define ff first #define se second #define pb push_back #define ppb pop_back #define mkp(a,b) make_pair(a,b) #define ST(v) sort(all(v)) #define sz(x) (int)x.size() #define gcd(a,b) __gcd(a,b) #define lcm(a,b) (a*(b/gcd(a,b))) #define max3(a,b,c) max(a,max(b,c)) #define min3(a,b,c) min(a,min(b,c)) #define maxall(v) *max_element(all(v)) #define minall(v) *min_element(all(v)) #define cover(a,d) memset(a,d,sizeof(a)) #define popcount(i) __builtin_popcount(i) //count one #define parity(i) __builtin_parity(i) //evenparity 0 and odd parity 1 #define input freopen("in.txt","r",stdin) #define output freopen("out.txt","w",stdout) #define un(v) ST(v), (v).erase(unique(all(v)),v.end()) #define common(a,b) ST(a), ST(b), a.erase(set_intersection(all(a),all(b),a.begin()),a.end()) #define uncommon(a,b) ST(a), ST(b), a.erase(set_symmetric_difference(all(a),all(b),a.begin()),a.end()) typedef vector<int> vi; typedef vector<ll> vl; typedef vector<string> vs; typedef pair<int,int> pii; typedef vector<pii> vpii; typedef set<int> si; typedef set<string> ss; typedef map<int,int> mii; typedef map<string,int> msi; //For Define #define for0(i,n) for(__typeof(n) i=0;i<(n);i++) #define for1(i,n) for(__typeof(n) i=1;i<=(n);i++) #define rfor0(i,n) for(__typeof(n) i=(n);i>=0;i--) #define rfor1(i,n) for(__typeof(n) i=(n);i>=1;i--) #define For(i,a,b) for(__typeof(b) i=a;i<=b;i++) #define forstl(i,s) for(__typeof((s).end()) i=(s).begin(); i != (s).end();...

Uva 10004 – Bicoloring

Problem Link   BFS Solution :- Bicoloring C++ /****************************************************************** *** Problem Setter: Miguel Revilla *** *** Uva Problem No: 10004 *** *** Problem Name : Bicoloring *** *** Type : Graph theory,BFS,DFS,Bipartite graphs *** *** Author : Shipu Ahamed (Psycho Timekiller) *** *** E-mail : shipuahamed01@gmail.com *** *** University : BUBT,Dept. of CSE *** *** Facebook : http://www.facebook.com/DeesheharaShipu *** ******************************************************************/ #include <queue> #include <cstdio> #include <vector> #include <cstring> #include <iostream> using namespace std; #define pf printf #define pb push_back #define sii(t) scanf("%d",&t) #define ssii(a,b) scanf("%d%d",&a,&b) #define cover(a,d) memset(a,d,sizeof(a)) int main() { int n,e,p; while(sii(n)) { if(n==0) break; sii(e); vector<int>ed[100000]; int color[10000]; cover(color,-1); for(int i=0;i<e;i++) { int x,y; ssii(x,y); ed[x].pb(y); ed[y].pb(x); } queue<int>work; int f=0; color[0]=0; work.push(0); while(!work.empty()) { p=work.front(); work.pop(); int vsize=ed[p].size(); for(int i=0;i<vsize;i++) { if(color[ed[p][i]]==-1) { if(color[p]==0) color[ed[p][i]]=1; else color[ed[p][i]]=0; work.push(ed[p][i]); } else { if(color[ed[p][i]]==color[p]){ f=1; break; } } } if(f==1) break; } if(f==1) pf("NOT BICOLORABLE.n"); else pf("BICOLORABLE.n"); } return 0; } 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586 /*********************************************************************   Problem Setter: Miguel Revilla                            ******   Uva Problem No: 10004                                     ******   Problem Name  : Bicoloring                                ******   Type          : Graph theory,BFS,DFS,Bipartite graphs     ******   Author        : Shipu Ahamed (Psycho Timekiller)          ******   E-mail        : shipuahamed01@gmail.com                   ******   University    : BUBT,Dept. of CSE                         ******   Facebook      : http://www.facebook.com/DeesheharaShipu   *********************************************************************/ #include <queue>#include <cstdio>#include <vector>#include <cstring>#include <iostream> using namespace std; #define pf printf#define pb push_back#define sii(t) scanf("%d",&t)#define ssii(a,b) scanf("%d%d",&a,&b)#define cover(a,d) memset(a,d,sizeof(a)) int main(){     int n,e,p;    while(sii(n))    {         if(n==0)        break;        sii(e);        vector<int>ed[100000];        int color[10000];        cover(color,-1);         for(int i=0;i<e;i++)        {            int x,y;            ssii(x,y);            ed[x].pb(y);            ed[y].pb(x);        }         queue<int>work;        int f=0;        color[0]=0;        work.push(0);         while(!work.empty())        {            p=work.front();            work.pop();            int vsize=ed[p].size();            for(int i=0;i<vsize;i++)            {                if(color[ed[p][i]]==-1)                {                    if(color[p]==0)                     color[ed[p][i]]=1;                    else                    color[ed[p][i]]=0;                     work.push(ed[p][i]);                }                else                {                    if(color[ed[p][i]]==color[p]){                        f=1;                        break;                    }                }            }            if(f==1)                break;        }        if(f==1)        pf("NOT BICOLORABLE.n");        else        pf("BICOLORABLE.n");    }     return 0;}   DFS Solution :- Bicoloring C++ /****************************************************************** *** Problem Setter: Miguel Revilla *** *** Uva Problem No: 10004 *** *** Problem Name : Bicoloring *** *** Type : Graph theory,BFS,DFS,Bipartite graphs *** *** Author : Shipu Ahamed (Psycho Timekiller) *** *** E-mail : shipuahamed01@gmail.com *** *** University : BUBT,Dept. of CSE *** *** Facebook...

গ্রাফ থিওরি এবং একটি রুপকথার গল্প

পোস্টের শুরু এক গল্প দিয়ে যেখানে এক রাজ্যে এক রাজার কোন সন্তান ছিল না । রাজার মনে খুব দুঃখ। রাজা আর রাণী সারাদিন মন খারাপ করে থাকে। এক দিন ভাগ্য দেবতা তাদের প্রতি প্রসন্ন হলেন। রাণীর গর্ভে সন্তান আসলো। কিন্তু গোল বাধলো ৯ মাস পর যখন সন্তান প্রসবের সময় আসলো রাণী এক মহা বিপদে পড়লেন রাজা সবাইকে বললেন যে যে কোন মুল্যে রাণীকে সুস্থ করে তুলতে হবে সবাই রাজার কথা মত রাণীর জন্য দাওয়াই খুজতে বের হল। সেখানে রাজার সেনাপতিরা এক অদ্ভুত সূর্যমুখী ফুলের সন্ধান পেলেন যেখানে ফুলটি দিনের রাতের বেলায়ও জ্বলজ্বল করে। সেনাপতি সেই ফুল রাণীর জন্য নিয়ে এলেন। এবং সেই ফুল ধোয়া পানি খেয়ে রাণী এক সুন্দর ফুটফুটে কন্যা সন্তান জন্ম দিলেন। যার চুল ছিল সোনালী আর সেই চুল ও কেউ গান গাইলে জ্বলজ্বল করতো। এখানে সেই ফুল ছিল এক ডাইনি বুড়ির দখলে যে তার ফুল হারিয়ে পাগল হয়ে গিয়েছিল। কারণ সেই ফুলের ছিল এক আশ্চর্য গুন যেখানে সেই ফুল কোন অসুস্থ মানুষকে সুস্থ করতে পারতো আর সেই ফুলের গুণে সেই ডাইনি আর যৌবন ধরে রাখতে পেরেছিল। ডাইনির নজর ছিল সেই রাজকন্যার উপর আর তাই এক রাতে সে সেই রাজকন্যাকে চুরি করে এক উচু টাওয়ারের উপর লুকিয়ে রাখলো আর তাকে বলল যে বাইরের দুনিয়া খুব ভয়ংকর সেখানে মোটেও যাওয়া যাবের না। আর সে নিজে তার মা সেজে তারসব কাজ করে দিত। ধীরে ধীরে সেই রাজকন্যা সেই ডাইনিকেই তার মা জেনে বড় হল আর জানল যে বাইরের দুনিয়া তার জন্য এক বিভিষীকাময় জায়গা। আমাদের সবার অবস্থা সেই রাজকন্যার মত। আমাদের ভেতরে এক ডাইনি বুড়ি সব সময় যে গ্রাফ থিওরি হল এক বিভিষীকাময় জায়গা আর আমরা ভয়তে সেদিকে ফিরেও তাকাই না। Back to the story: ধীরে ধীরে রাজকন্যার বয়স...

Uva 417 – Word Index

Problem Link Solution :- Word Index C++ /*------------------------------------------------*/ //Problem Setter: Shahriar Manzoor //Uva Problem No: 417 //Problem Name : Word Index //Type : BFS //Author : Abdul Alim //University : BUBT //E-mail : alim@programmer.net /*-----------------------------------------------*/ #include<cstdio> #include<map> #include<string> #include<iostream> #include<algorithm> using namespace std; string a="abcdefghijklmnopqrstuvwxyz"; map<string,int>mp; void alim() { int i,j,k,m,n; int p=1; string s,s1,s2,s3,s4,s5; for(i=0;i<26;i++) { s=a[i]; mp[s]=p; p++; } for(i=0;i<26;i++) { for(j=i+1;j<26;j++) { s1=a[i]; s2=a[j]; s=s1+s2; mp[s]=p; p++; } } for(i=0;i<26;i++) { for(j=i+1;j<26;j++) { for(k=j+1;k<26;k++) { s1=a[i]; s2=a[j]; s3=a[k]; s=s1+s2+s3; mp[s]=p; p++; } } } for(i=0;i<26;i++) { for(j=i+1;j<26;j++) { for(k=j+1;k<26;k++) { for(m=k+1;m<26;m++) { s1=a[i]; s2=a[j]; s3=a[k]; s4=a[m]; s=s1+s2+s3+s4; mp[s]=p; p++; } } } } for(i=0;i<26;i++) { for(j=i+1;j<26;j++) { for(k=j+1;k<26;k++) { for(m=k+1;m<26;m++) { for(n=m+1;n<26;n++) { s1=a[i]; s2=a[j]; s3=a[k]; s4=a[m]; s5=a[n]; s=s1+s2+s3+s4+s5; mp[s]=p; p++; } } } } } } int main() { char s[20]; alim(); while(scanf("%s",s)==1) { printf("%dn",mp[s]); } return 0; } 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110 /*------------------------------------------------*///Problem Setter: Shahriar Manzoor//Uva Problem No: 417//Problem Name  : Word Index//Type          : BFS//Author        : Abdul Alim//University    : BUBT//E-mail        : alim@programmer.net/*-----------------------------------------------*/ #include<cstdio>#include<map>#include<string>#include<iostream>#include<algorithm>using namespace std; string a="abcdefghijklmnopqrstuvwxyz";map<string,int>mp;void alim(){    int i,j,k,m,n;    int p=1;    string s,s1,s2,s3,s4,s5;    for(i=0;i<26;i++)    {        s=a[i];        mp[s]=p;        p++;    }    for(i=0;i<26;i++)    {        for(j=i+1;j<26;j++)        {            s1=a[i];            s2=a[j];            s=s1+s2;            mp[s]=p;            p++;        }    }    for(i=0;i<26;i++)    {        for(j=i+1;j<26;j++)        {            for(k=j+1;k<26;k++)            {                s1=a[i];                s2=a[j];                s3=a[k];                s=s1+s2+s3;                mp[s]=p;                p++;            }        }    }    for(i=0;i<26;i++)    {        for(j=i+1;j<26;j++)        {            for(k=j+1;k<26;k++)            {                for(m=k+1;m<26;m++)                {                s1=a[i];                s2=a[j];                s3=a[k];                s4=a[m];                s=s1+s2+s3+s4;                mp[s]=p;                p++;                }            }        }    }     for(i=0;i<26;i++)    {        for(j=i+1;j<26;j++)        {            for(k=j+1;k<26;k++)            {                for(m=k+1;m<26;m++)                {                   for(n=m+1;n<26;n++)                   {                s1=a[i];                s2=a[j];                s3=a[k];                s4=a[m];                s5=a[n];                s=s1+s2+s3+s4+s5;                mp[s]=p;                p++;                   }                }            }        }    } }int main(){    char s[20];    alim();    while(scanf("%s",s)==1)    {        printf("%dn",mp[s]);    }    return 0;}...