Lesson: 10
Problem: 119
Title: Greedy Gift Givers
Difficulty Level: 2
Date: Dec 18, 2008
Site: UVA
Lets Consider 1st Sample input:
5
dave laura owen vick amr
dave 200 3 laura owen vick
owen 500 1 dave
amr 150 2 vick owen
laura 0 2 amr vick
vick 0 0
5 persons - dave,laura,owen,vick and amr
5 transactions-
1st one: dave gives 200$ to laura, owen and vic ( each will get 200/3 = 66)
After 1st transaction:
dave = -66*3 = -198
laura = 66
owen = 66
vic = 66
2nd One: owen gives 500$ to dave
Balance:
dave = -198 + 500 = 302
laura = 66 ( same )
owen = 66 - 500 = -434
vic = 66 ( same )
3rd One: amr gives 150 to vick and owen
Balance:
dave = 302
laura = 66
owen = -434 + 75 = -359
vic = 66 + 75 = 141
amr = -150
4th One: laura gives 0 to amr and vick
Balance:
dave = 302
laura = 66 - 0 = 66
owen = -359
vic = 141 + 0 = 141
amr = -150 + 0 = -150
5th one: No transcation.
So our final result:
dave 302
laura 66
owen -359
vick 141
amr -150
How can we solve this problem ? Main problem is string, how can we handle friends name ? If we consider a name as an integer, then our problem will be solved, i.e dave = 1, laura = 2, owen = 3, vic = 4 and amr = 5.
To do that ,we can use C++ STL Map ( Standard Templage Library). Dont worry, you do not need to know C++ to use Map. Lets see how can we use it..
It's very easy...first declear a map.
map<string,int>Map;
Here we declear a map named Map with string integer pair. Because we have to assign a name to an integer.
Next, Map["city"] = 1;
Map["dhaka"] = 2;
Here first we map city to 1 and dhaka to 2. If we retrieve our value, we can do this in this ways..
int d = Map["city"];
this time d will be 1, similarly
int c = Map["dhaka"];
we get c = 2.
I think you get an idea about the map.
lets see our complete source code:
#include<stdio.h>
#include<map>
#include<string>
using namespace std;
map<string,int>Map;
char Name[10][1100];
int Balance[100];
int N; // number of friends
void readCase() {
int i;
for(i = 0; i<N; i++ ) {
scanf("%s",Name[i]); // reading each friends name
Map[Name[i]] = i + 1; // mapping each name to an integer
}
}
void Cal() {
char ss[100];
int doner, i, j, k, d, p;
for(i = 0; i<N; i++) {
scanf("%s",ss);
doner = Map[ss];
scanf("%d",&d);
scanf("%d",&p);
if(p == 0) {
continue;
}
k = d/p;
Balance[doner] -= k*p;
for(j = 0; j<p; j++) {
scanf("%s",ss);
doner = Map[ss];
Balance[doner]+= k;
}
}
}
void printResult() {
int i, doner;
for(i = 0; i<N; i++) {
doner = Map[Name[i]];
printf("%s %d\n",Name[i],Balance[doner]);
}
}
void Clear() {
Map.clear();
int i;
for(i = 0; i<= N; i++) Balance[i] = 0;
}
int main() {
int i, p, d, doner, k, kase = 0;
char ss[100];
while(scanf("%d",&N) != EOF) {
if(kase++) printf("\n"); // have to print a blank line between two set
readCase();
Cal();
printResult();
Clear();
}
return 0;
If you can remove confusion about the map, the above code seems very easy to you. Send me a mail if you have any doubt. One point, 'string' is a class in C++.
string str; and char str[size]; consider same if you have no idea about c++.