11659 - Informants

[plamplam]

Some test cases:

Code: Select all

19 3
12 -10
16 -4
9 11

2 6
1 -1
2 2
2 -1
2 1
1 2
2 -1

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

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

11 5
11 8
6 8
4 -11
3 -1
9 1

11 1
5 -6

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

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

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

19 6
11 18
12 -9
18 -5
7 14
1 16
14 -10

12 4
5 -2
6 2
1 -11
2 -10

16 1
7 1

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

16 1
9 -4

5 1
2 3

2 1
1 -2

12 1
10 -6

18 3
8 11
13 -9
7 -1

1 10
1 -1
1 1
1 -1
1 1
1 -1
1 -1
1 -1
1 1
1 1
1 1

13 7
13 13
1 8
12 5
4 11
5 3
13 11
8 -8

1 1
1 1

1 1
1 -1

0 0

Code: Select all

17
0
1
1
9
10
7
3
2
16
10
16
7
15
5
1
11
16
0
11
1
0

[brianfry713]

Imagine on 11659 that "A says B and C are not reliable", "B says A is not reliable but C is reliable" and "C says A is not reliable but B is reliable". What is the maximum number of reliable informants in this case ? And why ?

Input:

Code: Select all

3 6
1 -2
1 -3
2 -1
2 3
3 -1
3 2
0 0

Correct output is 2, B and C could be reliable.