A Wild Goose Chase

View as PDF

Points: 7 (partial)
Time limit: 0.5s
Memory limit: 128M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Recently, geese was murdered! The city has asked you to help Ducktective to figure out who murdered geese. There are foxes numbered to suspected to have killed geese. Ducktective is a very patient duck, and he has gotten every fox to say a statement. A fox either accuses another fox or accuses every fox beside themselves. With this information, Ducktective can determine that if exactly foxes are accusing a fox, that fox is guilty.

Given the list of foxes and their statements, help Ducktective determine who is guilty.

Input Specification

You will receive lines of input. The first line of input will contain two positive space-separated integers , the number of suspects and .

The next lines will contain two positive integers. The first integer , represents the fox. The next integer represents their statement. There are two options for . It can either be -1, meaning they are accusing every fox beside themselves, or it can be any integer from to , the number of the fox they are accusing.

Output Specification

On a single line, output the fox(es) who are guilty in increasing order. If it is inconclusive, i.e. no fox seems to be guilty, then print -1.

Sample Input 1

3 1
1 -1
2 3
3 -1

Sample Output 1

1

Sample Input 2

9 1
1 -1
2 1
3 1
4 1
5 1
6 1
7 8
8 7
9 1

Sample Output 2

2 3 4 5 6 9

• commented on July 7, 2020, 9:40 a.m.

Their still has to be some mistake in the sample input. For sample input 1, fox 1 accuses 2 and 3, fox 2 accuses 3, and fox 3 accuses 1 and 2. In this case, fox 1 would have one accusation, fox 2 would have two accusations, and fox 3 would have two accusations. Since T = 1, all three foxes should be guilty (since their accusation amounts are greater than 1). Why is only fox 1 guilty then?

• commented on July 7, 2020, 1:31 p.m.

The problem states:

Ducktective can determine that if 𝑇 foxes are accusing a fox, that fox is guilty.

What is meant by this is that exactly foxes must be accusing a fox for Ducktective to consider them guilty. The problem statement has been updated for clarity.

Regardless, your solution is still wrong.

(Hint: You don't take into account what happens if no fox seems to be guilty.)

• commented on April 30, 2020, 10:47 p.m. edited

It seems that the intended solution is not correct.

For this test case

5 2
1 -1
2 3
3 4
4 5
5 2

make sure that your program prints 2 3 4 5.

Edit: The problem statement has been updated to be correct.

• commented on April 16, 2020, 4:19 p.m. edited

Great problem!