Пятница, 13-ое, День Программиста |
---|
Закончено |
Письма счастья — сообщения, которые требуют от получателя переслать их копии как можно большему количеству людей, обычно с неким мистическим объяснением. Конечно, это всего лишь суеверие, и вы игнорируете такие письма — чего нельзя сказать о ваших друзьях. Известно, что сегодня такое письмо будет циркулировать среди ваших друзей, и вы хотите знать заранее, сколько его копий вы получите — конечно, пересылать его дальше вы не собираетесь!
Связи между вами и n - 1 вашими друзьями заданы массивом строк f из n элементов: j-ый символ i-ой строки (f[i][j]) — «1», если люди номер i и j будут обмениваться сообщениями (есть в контактах друг у друга), и «0» в противном случае. Человек номер 1 начинает рассылать сообщения всем своим контактам; каждый человек, получая письмо впервые, пересылает его всем своим контактам. Вы — человек номер n, и вы не пересылаете полученные письма.
Сколько копий этого письма вы получите?
Первая строка входных данных содержит целое число n (2 ≤ n ≤ 50) — количество задействованных людей. Следующие n строк содержат элементы массива f — строки длины n, состоящие из символов «0» и «1». Гарантируется, что выполняются равенства: f[i][j] = f[j][i], f[i][i] = 0, для всех i, j (1 ≤ i, j ≤ n).
Выведите целое число — количество копий письма, которые вы получите со временем.
4
0111
1011
1101
1110
3
4
0110
1010
1100
0000
0
4
0101
1001
0001
1110
2
В первом случае все посылают письма друг другу, так что вы получите копии от всех троих друзей.
Во втором случае вы не знаете никого из этих людей.
В третьем случае двое друзей посылают вам письма, но третий не знает ни одного из них и не получает письмо.
Название |
---|