Форум

Александр Симин: по-моему можно... // 14 сентября 2007, 12:46

хотя я и не очень уверен, что правильно - можно поочередно убирать из матрицы j-ую строку и j-ый столбец (как называется эта операция??? и считать сумму по оставшимся строкам/столбцам. В зависимости от того, поменялась ли сумма на N (все знают человека j) или не поменялась (человек j не знает никого) - и определяется, есть ли знаменитость.
Примерно так.

Сергей Чистович: Я не совсем понял, что ты предлагаешь, // 14 сентября 2007, 13:26

Но такое впечатление, что количество операций будет примерно N^3, нет? Сумму считать - это тебе не фунт изюму...

Понятно, что за 2N^2 сделать не проблема: пройтись по всей матрицен вдоль и поперек, да поискать ряд, где все единички и строку, где все нули. Но это слишком долго.

Александр Симин: Ну, // 14 сентября 2007, 15:35

я и предлагаю пройтись по всем, например, строчкам и поискать, где все нули. Потом для нулевых строк проверить соответствующие столбцы. Только сумму нужно считать для матрицы без j-й строки и j-го столбца, так как сам себя человек всегда знает... или нет?
Только ты определись с понятием "операция", так как для меня "поискать ряд, где все единички и строку, где все нули" - это непонятно. А сумма элементов любой строки/столбца - это имхо операция, нет? Кроме того, даже сама сумма не нужна, нужно сравнить больше она, равна или меньше нуля или N.

Сергей Чистович: Ты программист или что? // 14 сентября 2007, 17:22

Найти сумму N чисел - это N операций. Ладно, N-1. Проверить N чисел, являются ли они нулём - тоже N. Не очевидно?

Александр Симин: упаси Боже... // 14 сентября 2007, 17:26

неочевидно. Ладно, не буду мешать.