|
package main |
|
|
|
import ( |
|
"bufio" |
|
"flag" |
|
"fmt" |
|
"os" |
|
"strconv" |
|
"strings" |
|
) |
|
|
|
type Reader struct { |
|
*bufio.Scanner |
|
} |
|
|
|
func NewReader() *Reader { |
|
scanner := bufio.NewScanner(os.Stdin) |
|
return &Reader{scanner} |
|
} |
|
|
|
func (r *Reader) scanInt() int { |
|
r.Scan() |
|
n, _ := strconv.Atoi(r.Text()) |
|
return n |
|
} |
|
|
|
func (r *Reader) scanIntArray() []int { |
|
text := r.scanText() |
|
strs := strings.Split(text, " ") |
|
ints := make([]int, len(strs)) |
|
for i, v := range strs { |
|
ints[i], _ = strconv.Atoi(v) |
|
} |
|
return ints |
|
} |
|
|
|
func (r *Reader) scanText() string { |
|
r.Scan() |
|
return r.Text() |
|
} |
|
|
|
func main() { |
|
r := NewReader() |
|
n := r.scanInt() |
|
|
|
m := [][]int{} |
|
for i := 0; i < n; i++ { |
|
m = append(m, r.scanIntArray()) |
|
} |
|
|
|
var algorithm = flag.Int("algorithm", 1, "select algorithm type: 1 - simple, 2 - fine") |
|
flag.Parse() |
|
|
|
fmt.Fprintf(os.Stderr, "Algorithm: %d\n", *algorithm) |
|
celeb := findCelebrity(m, *algorithm) |
|
|
|
if celeb != -1 { |
|
fmt.Printf("%d\n", celeb+1) |
|
} else { |
|
fmt.Println("no celeb") |
|
} |
|
} |
|
|
|
func knownByAll(m [][]int, j int) bool { |
|
for i := 0; i < len(m); i++ { |
|
if m[i][j] == 0 && i != j { |
|
return false |
|
} |
|
} |
|
return true |
|
} |
|
|
|
func knowAny(m [][]int, i int) bool { |
|
for j := 0; j < len(m); j++ { |
|
if m[i][j] == 1 && i != j { |
|
return true |
|
} |
|
} |
|
return false |
|
} |
|
|
|
func findCandidate(m [][]int) int { |
|
i := 0 |
|
j := 1 |
|
next := 2 |
|
n := len(m) |
|
for next <= n { |
|
if m[i][j] == 1 { |
|
i = next |
|
} else { |
|
j = next |
|
} |
|
next = next + 1 |
|
} |
|
if i == n { |
|
return j |
|
} |
|
|
|
return i |
|
} |
|
|
|
func findCelebrity(m [][]int, algorithm int) int { |
|
if algorithm == 1 { |
|
return findCelebrity1(m) |
|
} |
|
|
|
return findCelebrity2(m) |
|
} |
|
|
|
func findCelebrity1(m [][]int) int { |
|
for i := 0; i < len(m); i++ { |
|
if !knowAny(m, i) && knownByAll(m, i) { |
|
return i |
|
} |
|
} |
|
return -1 |
|
} |
|
|
|
func findCelebrity2(m [][]int) int { |
|
c := findCandidate(m) |
|
if knownByAll(m, c) && !knowAny(m, c) { |
|
return c |
|
} |
|
return -1 |
|
} |