Woburn Challenge 1999
Fight Club
Brad Pitt's Fight Club has become quite big and so he wants to put some kind of organization into it. But remember the first two rules of Fight Club. No one can talk about Fight Club. But just on the off-chance that one of his minions loses his negligible mind in a fight and does talk about Fight Club, he wants to ensure that the entire organization is not compromised. So he does the following: He assigns one of his lackeys to come up with an organizational hierarchy subject to a few rules
- A person at a certain level is in charge of everyone below him in the hierarchy and knows the identity of ONLY those below him(thus, he can only compromise those below him)
- Everyone has exactly 1 person in charge of them, except Brad Pitt (see below). Why? Think about how the club would be compromised if this was not followed.
- Brad Pitt is the head of the hierarchy and thus has no boss. Therefore, no one knows his identity but conversely, he knows the identity of everybody (because everybody is under him).
This is all good, but we're forgetting that his followers are not exactly rocket scientists and so the man in charge of doing the hierarchy forgot to label the people in the hierarchy with their names. For extra security, everyone was labeled with a positive integer n (0 < n ≤ 20000). As a result, Brad Pitt doesn't know where he is on the hierarchy; to find out, he needs to scan the entire list. However, he doesn't even know if his rules were followed (writer's note: you just can't hire good help these days). So your job is a) to determine if the rules were followed and b) if so, determine which person in the list represents Pitt.
We will give you the hierarchy with numbers in place of the people in the hierarchy. If the rules were not followed, output "INVALID". Otherwise, output the number of the person that corresponds to Brad Pitt. (Note: you can safely assume that a valid hierarchy was not the result of multiple mistakes).
Input
The input will be pairs of integers x y, such that x is a boss of y. The numbers will be separated by (possibly multiple) white spaces (this includes returns!). The total number of people will be less than 200 and each boss will have no more than 10 people IMMEDIATELY below him (even in an invalid hierarchy). An input of '0 0' terminates the current hierarchy, while '-1 -1' denotes the end of data.Output
For each given heirarchy, output "INVALID" if the rules were not followed and Brad Pitt's number otherwise.Sample Input
3 1 3 2 2 4 0 0 3 1 1 3 0 0 -1 -1
Sample Output
3 INVALID
All Submissions
Best Solutions
Point Value: 10
Time Limit: 2.00s
Memory Limit: 16M
Added: Sep 29, 2008
Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3
Comments (Search)