Распространение вируса 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))

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .

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

	Распространение вируса 2 19.02.2022, 11:17. Показов 1168. Ответов 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