## Another Contest 2 Problem 2 - Poutine

View as PDF

Points: 10
Time limit: 0.6s
Memory limit: 256M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Fast Fingers Thomas has just finished conducting a tryout for a poutine-eating contest, and needs to produce a ranklist. However, the scoreboard has crashed and the rankings are lost! Individual beat individual if individual ate more poutine than individual . He vaguely remembers that some individuals ate more poutine than other individuals, but might not have enough data to fully reconstruct the ranklist. He does remember that there were no ties in the contest.

He decides to email all the participants with a list of pairs of individuals, and expects to get a response with, for each pair, which individual did better.

Compute the minimum possible size of the list such that, independent of what responses he gets back with regards to which individual ate more poutine, he is guaranteed to be able to construct a correct full ranklist.

#### Constraints

There exists some ranklist consistent with the input.

#### Input Specification

The first line contains a single positive integer, .

The next lines contains a binary string of length . If the th character of the th line is 1, then individual definitely did better than individual . Otherwise, the th character of the th line is 0.

#### Output Specification

Output the minimum number of pairs needed to always ascertain the ranklist.

#### Sample Input

3
011
000
000

#### Sample Output

1