Contest.samsu.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 

Задача 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

Сдать задачу

Задать вопрос жюри по этой задаче