Problems based on Maps

Problems:

Here is the list of problems you can do to practice maps:

• UVa 00417 - Word Index
• UVa 00484 - The Department of ... 
• UVa 00860 - Entropy Text Analyzer
• UVa 00939 - Genes
• UVa 10132 - File Fragmentation
• 6. UVa 10138 - CDVII 
• 7. UVa 10226 - Hardwood Species * 
• 8. UVa 10282 - Babelfish
• 9. UVa 10295 - Hay Points
• 10. UVa 10686 - SQF Problem
• 11. UVa 11239 - Open Source 
• 12. UVa 11286 - Conformity *
• 13. UVa 11308 - Bankrupt Baker
• 14. UVa 11348 - Exhibition
• 15. UVa 11572 - Unique Snowflakes * 
• 16. UVa 11629 - Ballot evaluation
• 17. UVa 11860 - Document Analyzer
• 18. UVa 11917 - Do Your Own Homework
• 19. UVa 12504 - Updating a Dictionary
• 20. UVa 12592 - Slogan Learning of Princess

Here is the link to the questions on Uva: https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=631

Here are my solutions and hints for a few of them.

Solutions and hints

Uva 10226: Harwood Species

Simple use of maps.

                                  

#include <bits/stdc++.h>
	using namespace std;
	#define MAXINT abs(~(int)0)
	#define MININT ~(int)0
	int main(int argc, char const *argv[]) {
	int T;
	scanf("%d", &T);
	int i=1;
	getchar();
	getchar();
	while (T--) {
	map<string, float> trees;
	string s;
	int numberofTrees = 0;
	while (getline(cin, s) && s!="") {
	if(trees.find(s)!=trees.end()){
	trees[s] +=1;
	}else{
	trees[s] = 1;
	}
	numberofTrees++;
	}
	if(i>1)
	printf("\n");
	for (map<string, float>::iterator t =trees.begin();t != trees.end(); t++) {
	cout<<t->first;
	printf(" %.4f\n", (t->second/numberofTrees)*100);
	}
	i++;
	}
	return 0;
	}

Uva 10282: BabelFish

Simple, simple usage of maps.

int main(int argc, char const *argv[]) {
	string line, a, b;
	std::map<string, string> dictionary;
	while (getline(cin, line)&&line!="") {
	istringstream sin(line);
	sin>>a>>b;
	dictionary[b]=a;
	}
	while (cin>>a) {
	map<string, string>::iterator it = dictionary.find(a);
	if(it==dictionary.end()){
	cout<<"eh"<<endl;
	}else{
	cout<<it->second<<endl;
	}
	}
	return 0;
	}

Uva 484: The department of redundancy department

Use map to maintain frequency, and one other container to store the data headings.

int main(int argc, char const *argv[]) {
	int ar;
	map<int, int> map;
	std::vector<int> v;
	while (scanf("%d", &ar)!=EOF) {
	if(map.find(ar)!=map.end()){
	map[ar] +=1;
	}
	else{
	map[ar] = 1;
	v.push_back(ar);
	}
	}
	for(vector<int>::iterator it=v.begin(); it!=v.end();it++){
	cout<<*it<<" "<<map[*it]<<'\n';
	}
	return 0;
	}

Uva 11286: Conformity

input the course as five integers, sort them, convert each to string and create a single string with them. Use this string as a key in your maps.

int main(int argc, char const *argv[]) {
	int n;
	while (scanf("%d", &n), n!=0) {
	map<string, int> courses;
	int max = 0;
	int counter=0;
	while (n--) {
	int arr[5];
	scanf("%d %d %d %d %d\n", &arr[0], &arr[1], &arr[2], &arr[3], &arr[4]);
	sort(arr, arr+5);
	string str = to_string(arr[0])+ to_string(arr[1])+ to_string(arr[2])+ to_string(arr[3])+ to_string(arr[4]);
	if(courses.find(str)!=courses.end()){
	courses[str] +=1;
	}else{
	courses[str] = 1;
	}
	}
	for(auto it=courses.begin();it!=courses.end();it++){
	if(it->second > max){
	max = it->second;
	counter=max;
	continue;
	}
	if(it->second==max){
	counter+=it->second;
	}
	}
	cout<<counter<<endl;
	}
	return 0;
	}

Uva Hay Points: 10295

Simple

int main(int argc, char const *argv[]) {
	int m, n;
	scanf("%d %d", &m, &n);
	map<string, int> map;
	string s;
	int dollar;
	while (m--) {
	cin>>s;
	scanf("%d", &dollar);
	map[s]= dollar;
	}
	while (n--) {
	int sum=0;
	string s;
	while (cin>>s) {
	if(s==".")
	break;
	if(map.find(s)!=map.end()){
	sum += map[s];
	}
	}
	cout<<sum<<endl;
	}
	return 0;
	}

Uva word-index 417

Use recursion to create the array up to vwxyz, than the problem is simple.

char arr[26];
	vector<string> v;
	bool comp(string a, string b){
	if(a.length()!=b.length())
	return a.length()<b.length();
	return a<b;
	}
	void generate(int counter, int start, string s){
	if(counter==5 || start==26){
	if(s!="")
	v.push_back(s);
	return;
	}
	generate(counter, start+1, s);
	generate(counter+1, start+1, s+arr[start]);
	}
	int main(int argc, char const *argv[]) {
	////generating the arr first;
	map<string, int> map;
	for(int i=0; i<26;i++){
	arr[i]=i+'a';
	}
	string s="";
	generate(0, 0, s);
	sort(v.begin(), v.end(), comp);
	int i=1;
	for(auto it=v.begin();it!=v.end();it++,i++){
	map[*it] = i;
	}
	/////////this completes the preperation for the map
	string t;
	while(getline(cin, t)&&t!=""){
	if(map.find(t)!=map.end())
	cout<<map[t]<<endl;
	else
	cout<<0<<endl;
	}
	return 0;
	}