Дилема Ромеро#434
Ромеро, охоронець в офісній будівлі в центрі Бінгемтона, розпочав свій день як звичайно. Однак цей день був інакшим. За кілька годин до того, як він прокинувся, щоб іти на роботу, у новинах почали з'являтися повідомлення про зомбі.
З часом на вулицях стало більше зомбі, і провідні науковці не могли пояснити, чому це відбувається. Близько полудня Ромеро спустився в кафетерій на обідню перерву. Його обід перервали крики, і він зрозумів, що щось не так. Вставши, щоб побачити, хто кричить, він побачив у кафетерії кількох зомбі, які прямували до нього. Наляканий, Ромеро швидко побіг до кабінету охорони і замкнув двері.
Після того, як він подолав шок, Ромеро зрозумів, що не може залишатися замкненим у кабінеті безкінечно. Він перевірив камери спостереження і з жахом побачив, як за його колегами ганяються зомбі. Ситуація у будівлі погіршувалась, і Ромеро усвідомив, що якщо він не залишить будівлю скоро, то зомбі заповнять усе приміщення. На моніторах Ромеро побачив, що його друг Гаррісон вижив, забарикадувавшись у своєму офісі. Ромеро почав шукати зброю в кабінеті охорони, але, на жаль, знайшов лише рушницю з кількома набоями.
Допоможіть Ромеро врятувати друга і втекти з будівлі. У Гаррісона немає зброї чи доступу до камер спостереження, і якщо Ромеро не врятує його, Гаррісон залишиться забарикадованим у своєму офісі, де його врешті атакують зомбі. Обидва друзі можуть проходити крізь двері швидше, ніж зомбі, а зомбі повільні й недостатньо кмітливі, щоб відчиняти двері самостійно. Однак зомбі дуже наполегливі — вони битимуть у двері, доки не зламають їх. Щоб врятувати Гаррісона, Ромеро має дістатися до кімнати, де знаходиться Гаррісон, швидше за зомбі.
Завдяки камерам спостереження Ромеро знає, де перебуває друг, а також у яких кімнатах знаходяться зомбі, а в яких ні. Коли Ромеро заходить до кімнати із зомбі, він використовує один набій для рушниці, щоб йти далі. Якщо він заходить у кімнату із зомбі і більше не має набоїв, зомбі перемагають і вбивають його. Тобто, якщо Ромеро починає втечу з набоями, його шлях до виходу з будівлі може проходити не більше ніж через кімнат, зайнятих зомбі.
Вхід складається з шести блоків:
У першому рядку зазначено кількість набоїв для рушниці. У другому рядку — назва кімнати, де знаходиться Ромеро, у третьому — назва кімнати, де забарикадувався Гаррісон. Далі йде число і список із кімнат, які спочатку зайняті зомбі (кожна назва кімнати у окремому рядку). П'ятий блок — це число і список із кімнат із вихідними дверима (кожна назва кімнати у окремому рядку). Вхід закінчується числом і списком із внутрішніх дверей (по одному в кожному рядку). Опис внутрішніх дверей складається з назв двох кімнат, з'єднаних дверима, після чого йдуть два числа: час, необхідний Ромеро й Гаррісону, щоб пройти крізь двері, та час, який потрібен зомбі, щоб проламати двері й пройти. Ви можете вважати, що друге число завжди більше за перше.
Ваша програма повинна вивести максимальну кількість друзів, які можуть вижити. Якщо Ромеро не зможе втекти, ваша програма повинна вивести . Якщо Ромеро може втекти сам, але не врятує Гаррісона, виведіть . Якщо Ромеро зможе врятувати Гаррісона й успішно втече, виведіть .
Вважайте, що під час руху Ромеро й Гаррісона між кімнатами вони не піддаються атакам зомбі. Також вважайте, що якщо Ромеро і зомбі одночасно прибудуть до Гаррісона, Ромеро зможе захистити друга, якщо у нього залишився хоч один набій. Назви кімнат не містять пробілів, і всього буде не більше кімнат і не більше внутрішніх дверей.
Приклад 1