Mohammad Erfan Hossain's Blog

UVA 10235 - Simply Emirp Solution /* It is a simple and easy problem. But has critical test case. Critical case:  If a number is prime and reverse number is equal to the given number then the output is "prime" not "emirp". For example: Given number 11. 11 number is prime. But reverse number is also 11.So, it is not "emirp". It is prime. */ Code: #include<iostream> #include<string> #include<string.h> #include<algorithm> #define MAX 1000001 using namespace std; bool prime[MAX]; int reverseInt(int num) {     string str=to_string(num);     reverse(str.begin(),str.end());     num=stoi(str);     return num; } int main() {     int i,j,x;     memset(prime,1,sizeof(prime));     for(i=4;i<MAX;i+=2)         prime[i]=0;     for(i=3;i<1001;i+=2)     {       ...

  UVA 389 - Basically Speaking Solution #include<iostream> #include<string> using namespace std; string input; int m,n; int convertToDes() {     int i,j,k,len,sum,temp,val,mul;     len=input.length();     char ch;     bool flag=false;     j=0;     sum=0;     mul=1;     for(i=len-1;i>=0;i--)     {         ch=input[i];         if(ch>='0' && ch<='9')             val=ch-48;         else             val=ch-55;         if(flag)             mul=mul*m;         flag=true;         sum=sum+val*mul;     ...

UVA 11479 Is this the easiest problem? #include<iostream> using namespace std; int main() {     long int test,a,b,c,count;     cin>>test;     count=1;     while(count<=test)     {         cin>>a>>b>>c;         cout<<"Case "<<count++<<": ";         if(a+b>c && a+c>b && b+c>a)         {             if(a==b && b==c)                 cout<<"Equilateral"<<endl;             else if(a==b || b==c || c==a)                 cout<<"Isosceles"<<endl;         ...

UVA 11340 Newspaper Solution #include<iostream> #include<string.h> #include<map> #include<stdio.h> using namespace std; map<char,int> mymap; map<char,int>::iterator mit; int main() {     freopen("input.txt","r",stdin);     int i,k,m,test,value;     char ch;     double sum;     char str[10010];     cin>>test;     while(test--)     {         cin>>k;         mymap.clear();         while(k--)         {             cin>>ch>>value;             mymap[ch]=value;         }         cin>>m;         getchar();  ...

#include<iostream> #include<string.h> #include<algorithm> #include<queue> using namespace std; typedef pair<int,int> pii; typedef pair<pii,int> piii; bool visit[8][8]; int m,n; int dx[]={-2,-2,-1,-1,1,1,2,2,},dy[]={-1,1,-2,2,-2,2,-1,1}; int bfs(char *str1,char *str2) {     queue<piii> q;     pii p1;     piii p2;     int x=str1[0]-97,y=str1[1]-49,xf=str2[0]-97,yf=str2[1]-49;     p1=pair<int,int>(x,y);     p2=pair<pii,int>(p1,0);     q.push(p2);     int i,xx,yy,zz;     while(!q.empty())     {         p2=q.front();         q.pop();         p1=p2.first;         zz=p2.second+1;         x=p1.first;         y=p1.sec...

UVA 572 Oil Deposits Solution #include<iostream> #include<map> #include<algorithm> #include<queue> using namespace std; typedef pair<int,int> pii; char arr[100][100]; bool visit[100][100]; int m,n; int dx[]={-1,-1,-1,0,0,1,1,1},dy[]={-1,0,1,-1,1,-1,0,1}; void bfs(int x,int y) {     queue<pii> q;     int i,xx,yy;     pii p=pair<int,int>(x,y);     q.push(p);     while(!q.empty())     {         p=q.front();         q.pop();         x=p.first;         y=p.second;         for(i=0;i<8;i++)         {             xx=x+dx[i];             yy=y+dy[i];          ...

UVA 11470 Square Sums Solution       #include<iostream> using namespace std; int arr[10][10],n,res[5]; int calculateSquare(int x) {     int sum=0,i,j;     i=n-1-x;     for(j=x;j<n-x;j++)         sum=sum+arr[x][j]+arr[i][j];     j=n-1-x;     for(i=x+1;i<j;i++)         sum=sum+arr[i][x]+arr[i][j];     return sum; } int main() {     int i,j,k,sum,lim,count,test=1;     while(cin>>n)     {         if(n==0)             break;         for(i=0;i<n;i++)         {             for(j=0;j<n;j++)             {        ...

UVA 713 - Adding Reversed Numbers Solution   '0'+'0'=96    (48+48) 48 is the ASCII value of zero. Sum of two char  is 96 is means 0. Sum value 97 means 1..... Sum value 105 means 9. Sum value 106 means 10. So, result is 0 and carry is 1. which add to next chars sum. CODE: #include<iostream> #include<map> #include<algorithm> #include<string> using namespace std; int trailZero(string str) {      int index=0;      while(str[index]=='0')      {         index++;      }      return index; } int main() {     map<char,char> charToInt;     string s1,s2,s3;     char ch;     int i,len1,len2,max_len,carry,test;     for(i=0;i<10;i++)         charToInt[i+96]=i+48;     cin>>te...

UVA 713 Adding Reversed Numbers Solution /*uva id: shoaib05    Accepted Time: 0.000 */ Procedure: Take input as string. Reverse the string. build the string equal length by putting zeros at start. Split the string and store in queue. Input: 8000000001   length is 10 1000101         length is 7 max_length is 10. Reverse the string 1000000008                                     1010001 put zero and build equal length. 0001010001 str1 is 1000000008 str2 is 0001010001 Here I spilt the string by size 4 and store in queue. Queue 1 0008 0000 rest of digits store in rem1=10 Queue 2 0001 0101 rest of digits store in rem2=00 Take string from queue1 and queue2, convert srings to number and add. If size exceed max size of 4 digit 9999 then subtract the sum value from 10000. put the subtract's value i...

Merge Sort in C++ #include<iostream> using namespace std; void merge(int *arr,int start,int mid, int end) { int x=start,y=mid+1,z=0,i,size=end-start+1; int *temp=new int[size]; while(true) { if(x>mid || y>end) break; if(arr[x]<arr[y]) { temp[z]=arr[x]; x++; z++; } else { temp[z]=arr[y]; y++; z++; } } if(x>mid) { while(y<=end) { temp[z]=arr[y]; y++; z++; } } else { while(x<=mid) { temp[z]=arr[x]; x++; z++; } } for(i=0;i<z;i++) { arr[start]=temp[i]; start++; } delete [] temp; } void divided_conqure(int *arr,int start_index,int last_index) { if(start_index==last_index)   return; int mid=(start_index+last_index)/2; divided_conqure(arr,start_index,mid); divided_conqure(arr,mid+1,last_index); merge(arr,start_index,mid,last_index); } int main()  { int arr[]= {7,8,1,2,9,5,3}; //start index of arr is 0 ...

UVA 10986 Solution - Sending email uva id: shoaib05 Accepted Time: 0.379 I used priority queue and Dijkstra Algorithm. Code: #include<iostream> #include<vector> #include<algorithm> #include<map> #include<queue> #include<cstring> using namespace std; typedef pair<int,int> pii; typedef vector<pii> vecpii; map<int,vecpii> mymap; map<int,int> result; bool visit[20010]; class Compare { public: bool operator()(pii p1,pii p2) { return p1.second>p2.second; } }; int DjKastra(int x,int y) { priority_queue<pii,vector<pii>,Compare> q; pii p,temp; int i; memset(visit,false,sizeof(visit)); q.push(pii(x,0)); while(!q.empty()) { p=q.top(); if(p.first==y) return p.second; q.pop(); if(visit[p.first]) continue; visit[p.first]=true; for(i=0;i<mymap[p.first].size();i++) { temp=mymap[p.first][i]; if(!visit[temp.first]) { q.push(pi...

UVA 429 Solution - Word Transformation uva id: shoaib05 Accepted Time: 0.036 I used Edit_Distance and Floyd warshall algorithm. Every word acts as a node. Two nodes are  adjacent if their edit distance is One . map, may ,mad are adjacent of each other. But pad and map are not adjacent because their edit distance is 2 . But mad and pad are adjacent because their edit distance is 1 . Here has no link between may and pad, no link between map and pad. Code: #include<iostream> #include<string> #include<algorithm> #include<map> #include<stdio.h> #define COLUMN 210 #define INFINITE 100000 using namespace std; int editDistance(string str1,string str2) { int table[11][11],length1,length2,i,j; length1=str1.size(); length2=str2.size(); for(i=0;i<=length1;i++) table[0][i]=i; for(i=1;i<=length2;i++) table[i][0]=i; for(i=1;i<=length2;i++) { for(j=1;j<=length1;j++) { ...

C++ Code for Kruskal's Algorithm with explanation  Example: Node numbers are 1 2 3 4 5 Weight is 3 between 1 and 3.  Weight is 4 between 1 and 2. Weight is 9 between 2 and 3. Weight is 1 between 2 and 4. Weight is 7 between 5 and 3. Weight is 2 between 4 and 5. At first sort the edge list according to weight. Weight is 1 between 2 and 4. Weight is 2 between 4 and 5. Weight is 3 between 1 and 3.  Weight is 4 between 1 and 2. Weight is 7 between 5 and 3. Weight is 9 between 2 and 3. Take array for node's parent. And initialize parent value equal to node value. parent[1]=1 parent[2]=2 parent[3]=3 parent[4]=4 parent[5]=5 Select the most small weighted edge. Here it is : Weight is 1 between 2 and 4. check the parents of two nodes are equal or not. If parents are not equal, Then store it in answer container. And set 2nd's node parent is 1st node's parent. parent of node 2 is 1. parent of node 4 is 2. p...