/*
I have been getting wrong answer as well.
My algorithm is a little unconventional, but it should still work.. Tested it and it worked on all the inputs in the forum...
Algorithm (quite unconventional):
Will be using a 2d array heard[people][trees] to store all values. If the tree is heard, value will be the tree's number
BUT IN **STRING** FORM!
So after storing all the values, u will have the trees (IN ORDER - IMPT). We then loop thru this array and store the in another map.
The map will have the key as the trees in COMBINED STRING FORM ("2367") and the value as the person.
We will simply search the map for repeating strings (strcmp), eliminate them, and the length of the map will be the answer.
Is there something wrong with the algorithm or the code?
CODE:
*/
Code: Select all
#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <map>
#include <math.h>
#include <string.h>
#include <string>
using namespace std;
#define LOOP(times) for(int(i)=0;i<times;i++)
/*
Algorithm (quite unconventional)
Will be using a 2d array heard[people][trees] to store all values. If the tree is heard, value will be the tree's number
BUT IN **STRING** FORM!
So after storing all the values, u will have the trees (IN ORDER - IMPT). We then loop thru this array and store the in another map.
The map will have the key as the trees in COMBINED STRING FORM ("2367") and the value as the person.
We will simply search the map for repeating strings (strcmp), eliminate them, and the length of the map will be the answer.
*/
string convertToString(int number){
stringstream ss;//create a stringstream
ss << number;//add number to the stream
return ss.str();//return a string with the contents of the stream
}
int main () {
int cases,npeople, ntrees,person,tree;
string stropinion;
map<string,int> opinions;
map<string,int> ::iterator it;
//ifstream cin;
//cin.open("temp.in");
cin >> cases;
cin.ignore(100, '\n');
LOOP(cases){
cin >> npeople >> ntrees;
cin.ignore(100, '\n');
int heard[npeople][ntrees];
memset(heard, 0, sizeof(heard[0][0]) * npeople * ntrees);
//{ {1,2,3,4} , {1,2,4,5}, {1,2,4,5}} //how to do?
while (cin.peek()!='\n' && cin.peek() != -1) {
cin >> person >> tree;
cin.ignore(100, '\n');
if(person>0 && tree>0){
heard[person][tree] = 1;
}
}
for(int a=1;a<=npeople;a++){
stropinion="";
for(int b=1;b<=ntrees;b++){
if(heard[a][b] == 1){
stropinion += convertToString(b)+".";
}
}
//this will still work for the test case if people hear no trees fall - becomes:""
opinions[stropinion] = 0;
}
/*
for(it=opinions.begin();it!=opinions.end();it++){
cout << it->first << " " << it->second << endl;
} cout << endl;
*/
cout << opinions.size() << endl;
opinions.clear();
}
//system("pause");
return 0;
}