OJ Board

i tried to solve that problem,
i matched all the sample output and input,

and it also works for the sample test cases that i made.

is there any inner trick, then plz let me know. thanx in advance.

Did you consider that this problem has multiple input?
And what about this input:
4 5
1 1
1 2
2 1
2 2

Output is 2.

hi, thanx for ur reply. Quoting from the problem ---------
People may have different opinions as to which trees, according to Berkeley, have made a sound. How many different opinions are represented in the input? Two people hold the same opinion only if they hear exactly the same set of trees.

ur sample input is:
4 5
1 1
1 2
2 1
2 2
and output is: 2
but how?

cauze here people 1 hear the sound of tree 1,2
and people 2 also hear the sound of tree 1, 2

so as both of them hear the same set of tree
so just only one opinion holds.
So the output should be: 1

plz explain the matter.

The second opinion comes from persons 3 and 4, who don't hear any trees fall.

Stefan

thanx pochmann.

i totally missed about the cases who doesn't hear anything.

but can someone explain me, the matter of multiple input? how should one tackle the problems of multiple input?
thanx.

In multiple input the different testcases are separated by an empty line. I'd suggest reading line after line with gets(...) and analyzing them with sscanf(...).

char line[100];
int a, b;
while( gets( line ) && sscanf( line, "%d%d", &a, &b ) == 2 ){
...
}

Stefan

its possivel this kind of input data

1

3 4

if yes what is the result? (0??)

1

3 4
0 0

if yes what is the result?

2

3 4


if yes what is the result (2 zeros or 1 zero?)

I simply can

It is a very beautiful problem. You have to be careful about problem statements all the time.

INPUT:

2

100 5
1 1
2 2
3 3
4 1
5 2
6 3

0 0

Output:

4

0

Hope it will help you. Good luck

This problem is absolutely trivial if you use stl set in C++. I finished coding it in 2 mins and got AC

I've got AC and here's the answers:

its possivel this kind of input data

1

3 4

if yes what is the result? (0??)

No, the result should be 1, since all 3 people heard exactly no trees fell, their opinion would be the same, so there's only 1 set of opinion.

1

3 4
0 0

if yes what is the result?

This is not valid input data, since both i,j are numbered from 1

2

3 4


if yes what is the result (2 zeros or 1 zero?)

This set of data is not valid, since the first line of each test case must have P and T

1,2,3 hold the same opinions as 4,5 and 6 respectively this makes 3 opinions in total not 4. Is there something I am missing? I have read the problem statement many times

i stored the trees for each person and then join the people if the trees are the same.

it is of the order (P*P*T) . Does anyone have it better than this ? what is the idea.

other approach
arr of STL sets
even i store the trees for each person in a set ( and then compare the sets for each person i and j and put them in a people set if they are same ).


Anyone have better solution or faster one ?

Hint for fast one : q-sort

int q_recur(int st, int ed,int p)
part a=q_recur(st,j,p+1);
part b=q_recur(j+1,ed,p+1);

I am getting Wrong answer continuously. I can't think of any possible cases for which my code would fail. Can some one please help me and post some input/outputs on the board? Thanks in advance for the help.