Mohammad Erfan Hossain's Blog

#include<iostream> #include<set> #include<algorithm> using namespace std; int main(){ multiset<int> myset; multiset<int>::iterator msit; int n,q,x,i,kase=1; while(cin>>n>>q){ if(n==0 && q==0) break; myset.clear(); for(i=0;i<n;i++){ cin>>x; myset.insert(x); } cout<<"CASE# "<<kase++<<":"<<endl; for(i=0;i<q;i++){ cin>>x; msit=myset.find(x); if(msit==myset.end()) cout<<x<<" not found"<<endl; else cout<<x<<" found at "<<distance(myset.begin(),msit)+1<<endl; } } return 0; }

#include<iostream> using namespace std; int main(){ int input_num,input_den,left_num,left_den,right_num,right_den,cur_num,cur_den; while(cin>>input_num>>input_den){ if(input_num==1 && input_den==1) break; left_num=0; left_den=1; right_num=1; right_den=0; cur_num=cur_den=1; while(true){ if(cur_num== input_num && cur_den==input_den) break; if(cur_num*input_den < cur_den*input_num){ cout<<"R"; left_num=cur_num; left_den=cur_den; cur_num+=right_num; cur_den+=right_den; }else{ cout<<"L"; right_num=cur_num; right_den=cur_den; cur_num+=left_num; cur_den+=left_den; } } cout<<endl; } return 0; }

uva 679 - Dropping Balls Solution Algorithm: 1. convert (position-1)  to binary and store it to a string. 2. make the binary string length equal to the (depth-1) by adding zero(0) at start of the string. 3. reverse the binary string. 4. convert binary string to integer + power(2,depth-1). Example: depth=7; position=4; covert 4-1= 3 to binary. binary string is 11. make the string length 7-1=6 by adding 0. Updated string 000011. reverse the binary string and string is now 110000 convert binary string(110000) to integer. value is 48. calculate power_value=pow(2,7-1)=pow(2,6)=64. Answer is = 48 + 64=112. Code in C++: #include<iostream> #include<string> #include<algorithm> using namespace std; string convertDecimalToBinary(int num){ string result; while(num!=0){ if(num%2==1) result.insert(0,1,'1'); else result.insert(0,1,'0'); num=num/2; } return result; } int convertBinaryToDecimal(string &n...

uva 481 - What Goes Up Solution #include<iostream> #include<vector> using namespace std; void binary_search(int *arr, int search_value, int start, int end, int &index){ if (start == end){ index = start; return; } int mid = (start + end) / 2; if (arr[mid] == search_value){ index = mid; return; } else if (arr[mid + 1] == search_value){ index = mid + 1; return; } else if (arr[mid]<search_value && arr[mid + 1]>search_value){ index = mid + 1; return; } else if (arr[mid] > search_value){ binary_search(arr, search_value, start, mid, index); } else{ binary_search(arr, search_value, mid + 1, end, index); } } void calculate_lis(vector<int>&arr,vector<int>&result){ int *temp, i, max = 0, j, index, n = arr.size(), *res; temp = new int[n]; res = new int[n]; temp[0] = 0; for (i = 1; i < n; i++){ if (arr[temp[max]] < arr[i]){ res[i] = temp[max]; max++; ...

uva 11790 Murcia’s Skyline Solution #include<algorithm> #include<iostream> #include<vector> using namespace std; int main() { vector<int> height, width, inc, dec; int i, j, test_case, n, x,max_i,max_d,cas=1; cin >> test_case; while (test_case--){ cin >> n; height.clear(); width.clear(); inc.clear(); dec.clear(); for (i = 0; i < n; i++){ cin >> x; height.push_back(x); } for (i = 0; i < n; i++){ cin >> x; width.push_back(x); } inc.push_back(width[0]); dec.push_back(width[0]); max_i = max_d = width[0]; for (i = 1; i < n; i++){ inc.push_back(width[i]); dec.push_back(width[i]); if (max_i<width[i]) max_i = width[i]; if (max_d<width[i]) max_d = width[i]; for (j = 0; j < i; j++){ if (height[i] > height[j] && inc[j] + width[i]>inc[i]){ inc[i] = inc[j] + width[i]; if (max_i < inc[i]) max_i...

uva 10534 - Wavio Sequence Solution #include<algorithm> #include<iostream> #include<vector> using namespace std; void binary_search(int *arr, int search_value, int start, int end, int &index){ if (start == end){ index = start; return; } int mid = (start + end) / 2; if (arr[mid] == search_value){ index = mid; return; } else if (arr[mid + 1] == search_value){ index = mid + 1; return; } else if (arr[mid]<search_value && arr[mid + 1]>search_value){ index = mid + 1; return; } else if (arr[mid] > search_value){ binary_search(arr, search_value, start, mid, index); } else{ binary_search(arr, search_value, mid + 1, end, index); } } void calculate_lis(vector<int>&arr, int n, vector<int>&result){ int *temp, i, max = 0, j, index; temp = new int[n]; temp[0] = 0; result.push_back(1); for (i = 1; i < n; i++){ if (arr...

uva 11456 - Trainsorting Solution #include<algorithm> #include<cstdio> using namespace std; int main() { int A[2000], Ma[2000], Mb[2000], N, T, sum, ans, i, j; scanf("%d", &T); while(T--) { scanf("%d", &N); for (i = 0; i < N; i++) scanf("%d", &A[i]); ans = 0; for (i = N - 1; i >= 0; i--) { Ma[i] = 1; Mb[i] = 1; for (j = i + 1; j < N; j++) { if (A[i] < A[j]) { Ma[i] = max(Ma[j] + 1, Ma[i]); } if (A[i] > A[j]) { Mb[i] = max(Mb[j] + 1, Mb[i]); } } ans = max(ans, Ma[i] + Mb[i] - 1); } printf("%d\n", ans); } return 0; }

uva 10131 - Is Bigger Smarter? Solution #include<iostream> #include<algorithm> #include<vector> using namespace std; typedef pair<int, int> pii; typedef pair<pii, int> piii; vector<piii> vec; vector<int> res; bool piii_sort(piii p1, piii p2){  if (p1.first.first<p2.first.first)   return true;  else   return false; } void calculate_lis(int len){ int *order = new int[len], *count = new int[len], i, j, last_index = 0, max = 1; fill(order, order + len, -1); fill(count, count + len, 1); for (i = 1; i < len; i++){ for (j = 0; j < i; j++){ if (vec[i].first.second<vec[j].first.second && vec[i].first.first>vec[j].first.first){ if (count[j] + 1>count[i]){ if (max < count[j] + 1){ max = count[j] + 1; last_index = i; } count[i] = count[j] + 1; order[i] = j; } } } } res.pus...

uva 497 - Strategic Defense Initiative Solution #include<iostream> #include<algorithm> #include<vector> #include<string> #include<stdio.h> #include<string.h> using namespace std; vector<int> list,order; int convertStringToInt(string str){ int i, len=str.length(), sum = 0,mul=1; for (i = len - 1; i >= 0; i--){ sum = sum + (str[i] - 48)*mul; mul = mul * 10; } return sum; } int getMaxTargets(){ int len = list.size(),i,j,max=1,last_index=0; int *count = new int[len],*index=new int[len]; fill(count, count + len, 1); fill(index, index + len, -1); order.clear(); for (i = 1; i < len; i++){ for (j = 0; j < i; j++){ if (list[i] > list[j]){ if (count[j] + 1>count[i]){ count[i] = count[j] + 1; if (max < count[i]){ max = count[i]; last_index = i; } index[i] = j; } } } } order.push_back(last_index); for (i = 1; i < max; i++){ ...

uva 231 - Testing the CATCHER Solution #include<iostream> #include<algorithm> #include<vector> using namespace std; vector<int> list; int getMaxMissiles(){ long long len = list.size(),i,j,max=1; long long *count = new long long[len]; fill(count, count + len, 1); for (i = 1; i < len; i++){ for (j = 0; j < i; j++){ if (list[i] < list[j]){ if (count[j] + 1>count[i]){ count[i] = count[j] + 1; if (max < count[i]) max = count[i]; } } } } return max; } int main(){ int x; long long kk = 1; while (cin >> x){ if (x == -1) break; list.clear(); list.push_back(x); while (cin >> x){ if (x == -1) break; list.push_back(x); } if (kk != 1) cout << endl; cout << "Test #" << kk++ << ":" << endl << "  maximum possible interceptions: " << getMaxMissiles() << endl;...

uva 111 - History Grading Solution  #include<iostream> #include<algorithm> using namespace std; int calculate_lis(int *arr1,int *arr2,int n){ int i, j, k; int lis[25][25]; for (i = 0; i <= n; i++){ lis[i][0] = 0; lis[0][i] = 0; } for (i = 0; i < n; i++){ for (j = 0; j < n; j++){ if (arr1[i] == arr2[j]){ lis[i + 1][j + 1] = lis[i][j] + 1; } else{ lis[i + 1][j + 1] = max(lis[i][j + 1], lis[i + 1][j]); } } } return lis[n][n]; } int main(){ int correct_order[25], rank[20],i,j,n,x; cin >> n; for (i = 0; i <n; i++){ cin >> x; x--; correct_order[x] = i; } while (cin >> x){ x--; rank[x] = 0; for (i = 1; i < n; i++){ cin >> x; x--; rank[x] = i; } cout << calculate_lis(correct_order, rank, n) << endl; } return 0; }

437 - The Tower of Babylon Solution #include<iostream> #include<algorithm> #include<vector> using namespace std; class dimension{ public: int x; int y; int z; }; bool area_sort(dimension d1, dimension d2){ if ((d1.x * d1.y) > (d2.x * d2.y)) return true; return false; } int calculate_max_height(vector<dimension>&vec){ int max = 0, *height, len=vec.size(), i,j,sum; dimension d1,d2; height = new int[len]; for (i = 0; i < len; i++){ height[i] = vec[i].z; } max = height[0]; for (i = 1;i < len; i++){ d1 = vec[i]; for (j = 0; j < i; j++){ d2 = vec[j]; if (d1.x < d2.x && d1.y < d2.y){ sum = d1.z + height[j]; if (sum > height[i]){ height[i] = sum; if (sum > max) max = sum; } } } } return max; } int main(){ vector<dimension>vec; dimension d[90]; int n,i,k,x,y,z,temp,test_case=1; while (cin >> n){ if (n == ...

uva 11951 - Area #include<iostream> #include<algorithm> #include<string> #include<string.h> #include<stdio.h> using namespace std; void maxSum(const int *const arr,int len,int max,int &count,int &lowest_cost){ int i,j,sum=0; count=0; lowest_cost=0; for(i=0;i<len;i++){ sum=arr[i]; if(sum<=max){ for(j=i+1;j<len;j++){ sum=sum+arr[j]; if(sum>max){ sum=sum-arr[j]; break; } } if((j-i)>count){ count=j-i; lowest_cost=sum; }else if((j-i)==count && lowest_cost>sum){ lowest_cost=sum; } } } } int main() { int arr[105][105]; int lowest,count,temp_count,temp[105],i,j,n,m,k,final_lowest,test_case,max,test; cin>>test_case; test=1; while(test_case--){ cin>>n>>m>>max; final_lowest=0; count=0; for(i=0;i<n;i++) for(j=0;j<m;j++) cin>>arr[i][j]; for(i=0;i<n;i++){ fill(temp,t...

uva 10976 - Fractions Again?! #include<iostream> #include<algorithm> #include<vector> using namespace std; int main(){ unsigned int i, n,m,count; while (cin >> n){ vector<int>vec; m = 2 * n; count = 0; for (i = n+1; i <= m; i++){ if ((n*i)%(i-n) == 0){ count++; vec.push_back((n*i) / (i - n)); vec.push_back(i); } } cout << count << endl; i = 0; while (count--){ cout << "1/" << n << " = 1/" << vec[i++]; cout << " + 1/" << vec[i++] << endl; } } return 0; }

10667 - Largest Block  #include<iostream> #include<algorithm> #include<string> #include<stack> using namespace std; bool matrix[100][100]; int calculate_max_histogram_area(int *arr,int len){ stack<int> st; int i, max, temp,temp_sum,cur_index,sum; temp = 0; max = 0; temp_sum = 0; for (i = 0; i< len; i++){ if (arr[i]>0 && arr[i] >= temp){ temp = arr[i]; st.push(i); } else{ temp = arr[i]; while (true){ if (st.empty()) break; cur_index = st.top(); if (arr[cur_index] == temp) break; st.pop(); sum = arr[cur_index] * (i - cur_index); if (sum > max){ max = sum; } } if (i < len && arr[i]>0) st.push(i); } } while (!st.empty()){ cur_index = st.top(); st.pop(); sum = arr[cur_index] * (i - cur_index); if (sum > max){ max = sum; } } return max; } int calculate_max_sub_matrix(int n){ ...

uva- 836 - Largest Submatrix   #include<iostream> #include<algorithm> #include<string> #include<stack> using namespace std; int calculate_max_histogram_area(int *arr,int len){ stack<int> st; int i, max, temp,temp_sum,cur_index,sum; temp = 0; max = 0; temp_sum = 0; for (i = 0; i< len; i++){ if (arr[i]>0 && arr[i] >= temp){ temp = arr[i]; st.push(i); } else{ temp = arr[i]; while (true){ if (st.empty()) break; cur_index = st.top(); if (arr[cur_index] == temp) break; st.pop(); sum = arr[cur_index] * (i - cur_index); if (sum > max){ max = sum; } } if (i < len && arr[i]>0) st.push(i); } } while (!st.empty()){ cur_index = st.top(); st.pop(); sum = arr[cur_index] * (i - cur_index); if (sum > max){ max = sum; } } return max; } int calculate_max_sub_matrix(string *input, int n){ ...

uva 108 - Maximum Sum - Solution using Kadane Algorithm #include<iostream> #include<algorithm> using namespace std; void kadane_algo(int *arr, int len, int &max_value){ if (len == 0) return; int tempSum  = arr[0]; if (tempSum > max_value) max_value = tempSum; for (int i = 1; i < len; i++){ if (tempSum < 0){ if (max_value <= arr[i]){ tempSum = max_value = arr[i]; } else{ tempSum += arr[i]; if (tempSum < arr[i]) tempSum = arr[i]; } } else{ tempSum += arr[i]; if (tempSum < arr[i]) tempSum = arr[i]; if (tempSum > max_value){ max_value = tempSum; } } } } void calculate_max_2d_rect_sum(int arr[][100], int row,int &max_value){ int temp[100], i, j, k, temp_max_value; max_value=temp_max_value = arr[0][0]; for (i = 0; i < row; i++){ fill(temp, temp + row, 0); for (j = i; j < row; j++){ for (k = 0; k < row; k++){ temp[k]...