Распространение вируса 2

@Ivan_bebrovich · Регистрация: 18.02.2022

Студворк — интернет-сервис помощи студентам

Владимир Петрович преподает в классе, в котором учатся n детей. Недавно ему поступило сообщение о том, что в один из его учеников заболел очередной новой версией очень заразного вируса. Чтобы предотвратить эпидемию в классе, Владимир Петрович решил выявить всех детей, кто мог заразиться.

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

Помогите Владимиру Петровичу узнать для каждого школьника, заразен ли он на данный момент.

Входные данные:
Первая строка содержит числа n и m — число школьников и число контактов в списке (1≤n≤1000, 1≤m≤1000). Школьники занумерованы числами от 1 до n, изначально заразный школьник имеет номер 1. В следующих m строках записаны пары (ai,bi) — номера школьников, которые общались между собой. Пары заданы в том порядке, в котором происходили контакты.

Выходные данные:
Выведите строку из n символов (без пробелов). Символ с номером i должен быть равен 1, если школьник заразен, и 0, если нет.

Примеры:
входные данные
6 5
1 3
2 4
3 4
1 4
6 1
выходные данные
101101

входные данные
3 2
2 3
3 2
выходные данные
100

входные данные
4 3
1 2
2 3
3 4
выходные данные
1111

Примечание:
В первом примере происходит следующее:

общаются школьники 1 и 3, школьник 3 заражается
общаются школьники 2 и 4, оба из них не заразные, поэтому ничего не происходит
общаются школьники 3 и 4, школьник 4 заражается
общаются школьники 1 и 4, оба из них заразные, ничего не меняется
общаются школьники 1 и 6, школьник 6 заражается
Во втором примере школьник 1 ни с кем не общается, поэтому в конце никто кроме него не заразен.

В третьем примере все школьники заражаются по цепочке.

@shinzin · 19.02.2022, 13:43

up1

@vrm2 · 19.02.2022, 18:51

1. Создаем множество sick = set([1]), в котором будем хранить номера заразных ребят.
2. Пробегаем по всем парам контактов детей (a,b). Если в паре один из детей болеет if a in sick, то добавляем другого в множество заразных sick.add(b)
3. Пробегаем по всем номерам детей. Для каждого определяем заразность - если есть в множестве, то возвращаем 1, иначе 0.

@shinzin · 19.02.2022, 22:20

Чем мы заполняем множество sick = set([1]) ?

Добавлено через 40 секунд
Во втором "если в паре один из детей болеет if a in sick", но список sick же пустой. Или я что-то не так понял

@thyrex · 19.02.2022, 23:08

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
n, m = map(int, input().split())
sicks = [0]*(n+1)
sicks[1] = 1
for i in range(m):
    a, b = map(int, input().split())
    if sicks[a]:
        if not sicks[b]:
            sicks[b] = 1
    else:
        if sicks[b]:
            if not sicks[a]:
                sicks[a] = 1
s = "1"
for i in range(2, n+1):
    s += str(sicks[i])
print(s)

@vrm2 · 19.02.2022, 23:35

Сообщение от shinzin

Чем мы заполняем множество sick = set([1]) ?
Во втором "если в паре один из детей болеет if a in sick", но список sick же пустой. Или я что-то не так понял

Множество sick изначально не пустое. Оно содержит одно число - 1 (номер первого заразившегося ребенка).

Добавлено через 9 минут

Python
1
2
3
4
5
6
7
8
9
def solve(n: int, meets: List[Tuple[int, int]]) -> str:
    sick = {1}
    for a, b in meets:
        if a in sick:
            sick.add(b)
        if b in sick:
            sick.add(a)
    return ''.join('1' if i in sick else '0'
                   for i in range(1, n + 1))

Новые блоги и статьи Все статьи Все блоги /
Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .	SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer 8Observer8 08.02.2026 Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .

@Ivan_bebrovich 7 / 6 / 1 Регистрация: 18.02.2022 Сообщений: 30

	Распространение вируса 2 19.02.2022, 11:17. Показов 1170. Ответов 5 Метки нет (Все метки) Владимир Петрович преподает в классе, в котором учатся n детей. Недавно ему поступило сообщение о том, что в один из его учеников заболел очередной новой версией очень заразного вируса. Чтобы предотвратить эпидемию в классе, Владимир Петрович решил выявить всех детей, кто мог заразиться. К счастью, недавно в школе установили новую систему безопасности, которая, кроме других полезных функций, записывает все контакты школьников. Владимир Петрович получил список пар школьников, которые общались между собой. Контакты происходили в том порядке, в котором они указаны в списке. Владимир Петрович считает, что после контакта с заразным школьником здоровый школьник моментально заражается и начинает заражать других, с кем он общается. Помогите Владимиру Петровичу узнать для каждого школьника, заразен ли он на данный момент. Входные данные: Первая строка содержит числа n и m — число школьников и число контактов в списке (1≤n≤1000, 1≤m≤1000). Школьники занумерованы числами от 1 до n, изначально заразный школьник имеет номер 1. В следующих m строках записаны пары (ai,bi) — номера школьников, которые общались между собой. Пары заданы в том порядке, в котором происходили контакты. Выходные данные: Выведите строку из n символов (без пробелов). Символ с номером i должен быть равен 1, если школьник заразен, и 0, если нет. Примеры: входные данные 6 5 1 3 2 4 3 4 1 4 6 1 выходные данные 101101 входные данные 3 2 2 3 3 2 выходные данные 100 входные данные 4 3 1 2 2 3 3 4 выходные данные 1111 Примечание: В первом примере происходит следующее: общаются школьники 1 и 3, школьник 3 заражается общаются школьники 2 и 4, оба из них не заразные, поэтому ничего не происходит общаются школьники 3 и 4, школьник 4 заражается общаются школьники 1 и 4, оба из них заразные, ничего не меняется общаются школьники 1 и 6, школьник 6 заражается Во втором примере школьник 1 ни с кем не общается, поэтому в конце никто кроме него не заразен. В третьем примере все школьники заражаются по цепочке. 0

@shinzin -2 / 6 / 5 Регистрация: 19.01.2022 Сообщений: 201
	19.02.2022, 13:43
	up1 0

@vrm2 431 / 302 / 90 Регистрация: 03.12.2015 Сообщений: 741
	19.02.2022, 18:51
	1. Создаем множество `sick = set([1])`, в котором будем хранить номера заразных ребят. 2. Пробегаем по всем парам контактов детей `(a,b)`. Если в паре один из детей болеет `if a in sick`, то добавляем другого в множество заразных `sick.add(b)` 3. Пробегаем по всем номерам детей. Для каждого определяем заразность - если есть в множестве, то возвращаем 1, иначе 0. 0

@shinzin -2 / 6 / 5 Регистрация: 19.01.2022 Сообщений: 201
	19.02.2022, 22:20
	Чем мы заполняем множество sick = set([1]) ? Добавлено через 40 секунд Во втором "если в паре один из детей болеет if a in sick", но список sick же пустой. Или я что-то не так понял 0

Опции темы