Задача H. Атака клонов
Задачу добавил: alef
Успешно сдано решений: 13
Задача H. Атака клонов
— Грустно, наверное, жить в Хипе. Неужели никто не может освободить подданных господина Маллока? – спросил Валя бабушку Тини.
— Даже не знаю… – задумалась бабушка Тини. – Случается, в Хип проникает злой колдун Сурив. Но он никого не освобождает, а подчиняет своей власти…
Как узнали ребята, Сурив может подчинить себе только тех подданных господина Маллока, рядом с домом которых он непосредственно находится. Однако он способен создавать своих двойников в количестве, достаточном, чтобы они подчинили себе подданных господина Маллока, проживающих в соседних домах. Соседними домами считаются дома, непосредственно связанные между собой дорогой.
На создание любого ненулевого количества двойников Сурив тратит K единиц времени. Его двойники также обладают этой способностью, и также могут создавать любое количество своих двойников за K единиц времени.
Созданные двойники мгновенно перемещаются к соседним домам, и процесс продолжается.
Ваша задача – написать программу, вычисляющую, сколько домов оказалось под властью злого колдуна, если он проник в Хип T единиц времени назад, а также получить список домов, которые окажутся под его властью следующими.
Формат входного файла input.txt
Первая строка – целые числа N (1 <= N <= 1000), M (1 <= M <= N), K (0 <= K <= 10000), T (1 <= T <= 10000000).
N – количество домов подданных господина Маллока
M – номер дома, в который проник злой колдун Сурив
K – количество единиц времени, необходимых для создания двойников
T – время, которое прошло с момента проникновения Сурива в Хип.
В каждой из следующих N строк содержится информация о дорогах между домами. В строке № j сначала указывается количество домов, которые непосредственно связаны с домом № j–1, затем через пробел указаны номера домов.
Формат выходного файла output.txt
Первая строка – количество домов, которые оказались под властью Сурива спустя время T после его проникновения в Хип.
Вторая строка – номера домов, которые будут заражены следующими, через пробел. Номера домов должны быть упорядочены по возрастанию. Если таких домов нет, выведите во второй строке 0.
Пример входного файла
2 2 5 3
1 2
1 1
Пример выходного файла
1
1