MUSKET - Musketeers

no tags 

In the time of Louis XIII and his powerful minister cardinal Richelieu in the Full Barrel Inn n musketeers had consumed their meal and were drinking wine. Wine had not run short and therefore the musketeers were eager to quarrel, a drunken brawl broke out, in which each musketeer insulted all the others.

A duel was inevitable. But who should fight who and in what order? They decided (for the first time since the brawl they had done something together) that they would stay in a circle and draw lots in order. A drawn musketeer fought against his neighbor to the right. A looser "quit the game" and to be more precise his corpse was taken away by servants. The next musketeer who stood beside the looser became the neighbor of a winner. 

After years, when historians read memories of the winner they realized that a final result depended in a crucial extent on the order of duels. They noticed that a fence practice had indicated, who against who could win a duel. It appeared that (in mathematical language) the relation "A wins B" was not transitive! It could happen that the musketeer A fought better than B, B better than C and C better than A. Of course, among three of them the first duel influenced the final result. If A and B fight as the first, C wins eventually. But if B and C fight as the first, A wins finally. Historians fascinated by their discovery decided to verify which musketeers could survive. The fate of France and the whole civilized Europe indeed depended on that!


N persons with consecutive numbers from 1 to n stay in a circle. They fight n-1 duels. In the first round one of these persons (e.g. with the number i) fights against its neighbor to the right, i.e. against the person numbered i+1 (or, if i=n, against the person numbered 1). A looser quits the game, and the circle is tighten so that the next person in order becomes a winner's neighbor. We are given the table with possible duels results, in the form of a matrix. If Ai,j = 1 then the person with the number i always wins with the person j. If Ai,j = 0 the person i looses with j. We can say that the person k may win the game if there exists such a series of n-1 drawings, that k wins the final duel.
Write a program which:

  • reads matrix A from the standard input,
  • computes numbers of persons, who may win the game,
  • writes them into the standard output.


The number of test cases t is in the first line of input, then t test cases follow separated by an empty line. In the first line of each test case integer n which satisfies the inequality 3<=n<=100 is written. In each of the following n lines appears one word consisting of n digits 0 or 1. A digit on j-th position in i-th line denote Ai,j. Of course Ai,j = 1 - Aj,i, for i<>j. We assume that Ai,i = 1, for each i


For each test case in the first line there should be written m - the number of persons, who may win the game. In the following m lines numbers of these persons should be written in ascending order, one number in each line.


Sample input:

Sample output:

The order of duels: 1-2, 1-3, 5-6, 7-1, 4-6, 6-1 gives a final victory to the person numbered 6. You can also check that only two persons more (1 and 3) may win the game.

hide comments
kass_97: 2017-01-12 21:17:42

Had some serious work to do, finally done with dp approach....feeling good :D

Kunal Singhal: 2013-10-22 15:49:47

What are the constraints on number of test cases? Will an O(n^3) solution work?

Added by:Piotr Łowiec
Time limit:1.169s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Resource:6th Polish Olympiad in Informatics, stage 1