COCI '08 Contest 5 #4 Lubenica

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 0.6s
Memory limit: 64M

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

Children in school are having fun instead of listening to the teacher. With their iPhone devices the children throw watermelons at each other on the Facebook social site.

The game started when Goran threw one watermelon at each of his friends during the first class that day. During subsequent classes, all children (including Goran) behaved like this:

  • If they had been hit by an odd number of watermelons during the previous class, they threw exactly one watermelon at each of their friends;

  • If they had been hit by an even number of watermelons (including zero), then they hit each of their friends with two watermelons.

The children are numbered 1 through N, Goran obviously being number 1. The friend relationships between the children are also known.

Write a program that will calculate the total number of watermelons thrown after H classes.

Input Specification

The first line contains two integers N and H (1 \le N \le 20, 1 \le H \le 1\,000\,000\,000), the number of kids and classes.

Each of the following N lines contains a string of N characters 0 or 1. The character (A, B) in this matrix is 1 if children A and B are friends.

No child will be their own friend. The input matrix will be symmetric.

Output Specification

Output the number of watermelons after H classes.


In test cases worth 50\% of points, H will be at most 1000.

Sample Input 1

4 1

Sample Output 1


Sample Input 2

4 2

Sample Output 2


Sample Input 3

5 3

Sample Output 3


In the second example, Goran throws two watermelons during the first class. During the second class, children 1 and 4 each throw two watermelons at 2 and 3 each, while 2 and 3 throw one watermelon at 1 and 4. A total of 12 watermelons is thrown during the second class.


  • 0
    4fecta  commented on Oct. 9, 2019, 6:45 p.m.

    For the third sample, why is the output not 23?