Дима системный администратор в институте. На данный момент он разбирается с крупной

Дима системный админ в институте. На данный момент он разбирается с большой проблемой некие из компьютеров в дисплейных классах дружественной вузу школы заражены компьютерным вирусом. Антивирусное ПО не подсобляет вирус очень свежайший...

Дима нашёл компьютер, с которого началось инфецирование, после чего собрал лог по всем переданным по локальной сети пакетам. Выяснилось, что в случае, если компьютер получил данные от компьютера, зараженного вирусом, компьютер заражается (при этом если компьютер только отправлял данные на зараженный компьютер, инфецирования не происходит).

Так как размер лога очень великой, Дима предлагает распараллелить усилия и просит Вас написать программку, которая обусловит перечень заражённых компов (а сам он будет разбираться с тем, как обезоружить вирус на определенном компьютере).

Формат ввода
Входные данные состоят из нескольких (не более 30) тестовых образцов.

1-ая строчка каждого тестового образца содержит два целых числа N и M (0 lt; N 2 104, 0 M 2 104), где N количество компьютеров в школьной сети и M количество записей в логе о переданных пакетах данных.

В следующих M строчках задаются пакеты, по одному на строчку. Каждый пакет задаётся тремя целыми числами ti, si и di временем отправки пакета, номером компьютера, с которого был отправлен пакет и номером компьютера, на который был выслан пакет, соответственно (0 ti 109, 1 si, di N, si

Задать свой вопрос
1 ответ

Программа ни питоне 3, наивно реализующая то, что написано в задаче:

while True:

   n, m = map(int, input().split())

   if n == 0:

       break

   infected = set([1])

   log = [[int(i) for i in input().split()] for _ in range(m)]

   log.sort(key=lambda x: x[0])

   for entry in log:

       if entry[1] in infected:

           infected.add(entry[2])

   print(len(infected))

Считываем n и m, если это не нули, идем далее. Считываем лог, на всякий случай сортируем его так, чтоб записи шли в хронологическом порядке. Создаем огромное количество зараженных компов, затем для каждой записи в логе проверяем, был ли отправитель заражен, если да - прибавляем получателя в перечень зараженных. В конце выводим количество зараженных компов.

, оставишь ответ?
Имя:*
E-Mail:


Последние вопросы

Добро пожаловать!

Для того чтобы стать полноценным пользователем нашего портала, вам необходимо пройти регистрацию.
Зарегистрироваться
Создайте собственную учетную запить!

Пройти регистрацию
Авторизоваться
Уже зарегистрированны? А ну-ка живо авторизуйтесь!

Войти на сайт