[POI1999]步兵问题

成绩 0 开启时间 2013年01月22日 星期二 05:05
折扣 0.8 折扣时间 2013年01月22日 星期二 05:05
允许迟交 关闭时间 2013年01月22日 星期二 05:05
输入文件 mus.in 输出文件 mus.out

在Louis三世和他的重臣-红衣主教Richelieu时期的一个旅馆里n个步兵正在大口的吃肉喝酒。由于喝个不停,因此步兵们热心于吵架。一场喝醉了酒的争吵爆发了,每个步兵都谩骂着对方。

决斗是不可避免的。但是谁应该以什么顺序去打谁?他们决定(第一个回合来自他们的共同争吵)他们围成一圈按顺序选出一些人。被选出的士兵和他右边相邻的人打斗。失败的人离开游戏,为了更加精确,他的尸体将被仆人拖走。下一个步兵将站在失败者的旁边成为胜利者的邻居。

一些年后,当历史学家读了胜利者的记录后,他们意识到最终胜利的结果依靠一个按决斗顺序展开的圆环。他们注意到一个栅栏练习表明,谁靠着谁 能赢得一场决斗。它表现在(用数学语言)“A赢B”的关系不是及物的!步兵A比B打的更好,B比C更好,C比A更好是有可能的。当然,他们三个当中的首场 决斗影响了最后的结果。如果A和B先打,那么C最终会赢。但是如果B和C先打,那么A就最终会赢。历史学家被他们的发现感到入迷,决定去核实那么步兵能够 生存。法国的命运和整个文明的欧洲真正依靠这个!

任务

N个人以从1到n的连贯数字站成一行。他们要决斗n-1次。在第一个回合这些人中的一个(编号为I)打他右边的邻居,也就是编号为 I+1(如果I=n,则要打的人为编号为1的)。一个失败者离开游戏,圆环收缩以至下一个人能成为胜利者的邻居。我们被给出可能的决斗结果的表,用一个矩 阵形式。如果Ai,j = 1,那么编号为I的人总是战胜编号为j的人。如果Ai,j = 0,那么编号为I的人输给编号为j的人。如果存在一系列n-1的图,我们说编号为k的人赢得了这个游戏,赢得了最终的决斗。

写一个程序:

从文件读取矩阵A, 计算可能赢得比赛的人的编号, 把结果写到文件

输入

在文件的首行有一个整数n(满足不等式3<=n<=100)被记录。在接下来的n行的每一行里将出现有0或1组成的n位的字符 串。一个第I行第j列的数字表示Ai,j 。当然,对于i<>j ,Ai,j = 1 - Aj,i 。对于每一个I,Ai,i = 1。

输出

在输入文件的首行,应该写下m-可能赢得这个游戏的人数。在接下来的m行里,这些人的编号应该被按照升序记录,每一行一个。

样例输入  

7
1111101
0101100
0111111
0001101
0000101
1101111
0100001

样例输出  

3
1
3
6

备注

决斗顺序:1-2,1-3, 5-6, 7-1, 4-6, 6-1 得到最后胜利的是编号为6的人。你也能检查仅有两个人(1和3)更有可能赢得这个游戏。