Вопрос № 62499: Помогите пожалуйста решить задачу! Хотя бы основную идею решения.
Итак, задача:
В классе N учеников. Марья Ивановнв попросила некоторых из них прочитать книгу. Книга существует в одном экземпляре. Поэтому решено было отдать книгу одному из уч...
Вопрос № 62.499
Помогите пожалуйста решить задачу! Хотя бы основную идею решения.
Итак, задача:
В классе N учеников. Марья Ивановнв попросила некоторых из них прочитать книгу. Книга существует в одном экземпляре. Поэтому решено было отдать книгу одному из учеников. Он должен прочесть ее и отнести другому ученику, кто еще не читал книгу. В свою очередь, этот ученик, после прочтения книги, передаст ее еще кому-нибудь, кто не читал ее и т. д. Класс организован недавно => не все знают адреса друг друга, а именно: для любых двух учеников из класса только один из них обязательно знает адрес другого. Необходимо
составить список из нескольких учеников таким образом, чтобы их количество было максимальным и каждому ученику (за исключением последнего) был известен адрес следующего за ним по списку одноклассника.
В первой строке входного файла содержится число N(3<N<300)- кол-во учеников в классе. В следующих N строках идет описание класса. В (i+1)-ой строке записано N нолей или единиц. 0 на j-ой позиции означает, что ученик с номером i не знает адрес ученика с номером j, 1 означает, что знает. Считается, что ученик не знает своего собственного адреса. Гарантируется, что для любых двух учеников ровно один из них знает адрес другого.
В выходной файл выведите последовательность чисел соответствующую максимальному по длине списку. Нумерация должна быть такая же как и во входном файле. Время выполнения программы-2сек. Ограничение по памяти-64Mb
Приложение:
Отправлен: 13.11.2006, 21:29
Вопрос задал: Ch_k (статус: Посетитель)
Всего ответов: 1 Мини-форум вопроса >>> (сообщений: 0)
Отвечает: Verena
Здравствуйте, Ch_k!
Можно попробовать загнать информацию о классе в двумерный массив записей такого вида:
Type klass = record
adr: integer;
kn: boolean;
End;
Var a: array [1..300,1..300] of klass;
Потом возьмём дополнительную матрицу в две строки, куда будем записывать альтернативные пути обхода - текущий и предыдущий. При обходе матрицы - описания класса будем проверять: если адрес известен (текущий adr=1) и книги у претендента ещё не было (его kn=false), то можно туда пойти. Сделав два обхода сравним результат по количеству элементов в 1 и 2 строках вспомогательной матрицы, выбираем лучший из них, записываем в 1-ю строку и сравниваем дальше. А чтобы сэкономить память можно использовать динамические
массивы вместо статических.
--------- Эта история - не для истории, понимаешь?
Ответ отправила: Verena (статус: 2-ой класс)
Ответ отправлен: 13.11.2006, 22:04
