网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
liars
成绩 | 开启时间 | 2014年09月19日 星期五 10:07 | |
折扣 | 0.8 | 折扣时间 | 2014年09月26日 星期五 10:07 |
允许迟交 | 是 | 关闭时间 | 2014年09月26日 星期五 10:07 |
输入文件 | liars.in | 输出文件 | liars.out |
【题目描述】
有n个人,编号分别为1,2,…,n。这n个人中每个人不是诚实者就是说谎者,并且每个人都知道下一个人的身份(即第k个人知道第k+1个人的身份,1<=k<n,且第n个人知道第1个人的身份)。现在已知每个人对他下一个人的身份的判断,并且说谎者的人数不超过t,问哪些人一定是说谎者。注意,诚实者给出的判断一定是正确的,但说谎者给出的判断是不确定的,可能正确也可能错误。
【输入格式】
第一行一个整数T,表示数据个数。
下面接T组数据,每组数据两行。
第一行为两个正整数n和t,表示一共有n个人,且说谎者人数不超过t。
第二行为n个整数,每个数为0或1。第i个数若为0,则表示第i个人判断下一个人为诚实者;
若为1,则表示第i个人判断下一个人为说谎者。
【输出格式】
每组数据输出一行,每行两个整数。第一个整数表示一定是说谎者的人的个数,第二个数表示一定是说谎者的人中,编号最小的人的编号。若第一个数是0,则第二个数也为0。(若定义集合S={k|第k个人一定是说谎者},那么第一个数就是|S|,第二个数就是S中最小的数。若S为空集则第二个数为0)
【样例输入】
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
【样例输出】
1 3 2 4 0 0
【提示】
30%的数据中,n<=1000。
100%的数据中,n<=100000。
【来源】
在此键入。