Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: Finding Liars
Description There are n>=2 people labeled as 1, 2, ... , n such that each of them is either a truth-teller or a liar, and the number of liars is less than or equal to t for some t (<=n).
Each person i can test another person j in order to identify person j as truth-teller or liar by giving some question to person j. The outcome a _{i,j} of the test applied by person i to person j is 1 (0) if person i identifies person j as a liar (truth-teller). The test outcome a_{i,j} is reliable if and only if the testing person i is a truth-teller.
That is, the test outcome a _{i,j} is unreliable if and only if the testing person i is a liar. The following table shows the value of the test outcome a_{i,j} when person i tests person j.
Input The input consists of T test cases. The number of test cases (T ) is given in the first line of the input file. Each test case consists of two lines. The first line has two integers. The first integer is n (2<=n<=1000), the number of persons, and the second integer is t (0<=t<=n), the maximum number of liars. The second line contains n 0 or 1's that represent a1,2, a2,3, a3,4, ..., a(n-1),n, an,1. Output Print exactly one line for each test case. The line should contain two integers. The first integer is the number of all the definite liars. The second integer is the smallest label of definite liars. In case that the number of definite liars is equal to 0, then the second integer should be 0. Sample Input 3 5 2 0 1 1 0 0 7 2 0 0 1 0 0 1 1 9 8 1 0 0 0 0 1 0 0 0 Sample Output 1 3 2 4 0 0 Source |

[Submit] [Go Back] [Status] [Discuss]

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator