Страница: 1 Отображать по:

#1751

Квест

Темы: [Задачи на моделирование] [Разбор выражений]

Источники: [ Личные олимпиады, Открытая олимпиада школьников, 2008-2009, Заочный этап, Задача K ]

Одна программистская компания решила разработать серию игр в жанре «Квест». Один из игроков сумел похитить сценарии игр, и теперь планирует составить описания прохождения всех квестов.

Во всех квестах приключения происходят в некотором здании, где имеется несколько комнат. Комнаты соединены друг с другом дверями. Чтобы открывать двери, можно использовать ключи. Также в игре присутствуют персонажи, объекты и предметы. Основная цель игры — спасти принцессу, которая находится в одной из комнат.

Игрок в квесте может поговорить с любым персонажем. После этого он узнает названия нескольких предметов, которые требуется принести этому персонажу, чтобы тот в свою очередь дал игроку некоторые другие предметы. Некоторые предметы можно найти на полу комнат. Также игрок может использовать предметы на объектах. В результате этого он получает некоторые другие предметы.

Напишите программу, которая, получив описание игрового мира квеста, создает описание его прохождения — последовательность действий, которые игрок должен совершить, чтобы успешно пройти квест — спасти принцессу.

Входные данные

Первая строка входного файла содержит число \(N\) — количество комнат в игре. Следующие \(N\) строк содержат названия комнат. Следующая строка содержит \(M\) — количество дверей. Следующие \(M\) строк описывают двери — каждая строка содержит номера комнат, разделенных дверью, и название ключа, который открывает эту дверь.

Затем следует описание содержимого комнат. Каждое описание начинается с трех целых чисел: \(c\) — количество персонажей в комнате, \(o\) — количество объектов в комнате и \(i\) — количество предметов на полу в комнате.

Следующие строки содержат описание персонажей. Каждое описание состоит из трех строк. Первая строка содержит имя персонажа. Следующая строка содержит названия одного или более предметов — те предметы, которые игрок должен принести данному персонажу. Последняя строка также содержит названия одного или более предметов — предметы, которые персонаж даст игроку после того, как тот принесет ему запрошенные предметы. Описание объектов в том же формате идет после персонажей. Отличие объектов от персонажей заключается в следующем: после того как игрок отдает предметы персонажу, они остаются у персонажа, а после использования на объекте предметы остаются у игрока. Также прежде чем дать что-либо персонажу требуется поговорить с ним. Последние \(i\) строк описания комнаты содержат названия предметов, которые находятся в ней на полу. Если в одной строке перечисляется несколько предметов, их названия разделяются запятой.

Последние две строки входного файла содержат название комнаты, в которой игрок исходно находится, и название комнаты, в которой заперта принцесса.

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

Выходные данные

Выведите последовательность действий, которую требуется выполнить, чтобы выиграть.

Игрок может:

· говорить с персонажем (talk to …),

· давать предметы персонажу (give … to …) после того, как поговорит с ним,

· брать предметы у персонажа (take … from …) непосредственно после того, как даст ему то, что ему требуется,

· использовать предметы на объектах (use … on …),

· брать предметы у объекта (take … from …) непосредственно после того, как использует на нем то, что требуется

· поднимать объекты с пола (pick …),

· открывать двери с помощью ключей (open door to …),

· переходить из комнаты в комнату (go to …), если эти комнаты непосредственно соединены открытой дверью,

· спасти принцессу (save princess), если игрок находится в комнате, где она заперта.

Следуйте формату, приведенному в примере. Игрок должен всегда давать персонажу или использовать на объекте все необходимые предметы, а также забирать объекты у персонажа или объекта в одно действие.

Если выиграть невозможно, выведите “dead princess” в первой строке выходного файла.

Примеры

Входные данные

2
white room
black room
0
0 0 0
0 0 0
white room
black room

Выходные данные

dead princess

Входные данные

4
white room
black room
blue room
green room
3
1 3 crystal key
1 4 esmerald key
2 3 strange key
0 0 2
crystal key
oranges
0 0 0
2 1 0
Wild Joe
rat, red pepper, coin
strange key
Dead man
orange juice
red pepper, esmerald key
squeezer
oranges
orange juice
0 1 1
monkey
oranges
coin
rat
white room
black room

Выходные данные

pick crystal key
pick oranges
open door to blue room
go to blue room
use oranges on squeezer
take orange juice from squeezer
talk to Dead man
give orange juice to Dead man
take esmerald key and red pepper from Dead man
go to white room
open door to green room
go to green room
pick rat
use oranges on monkey
take coin from monkey
go to white room
go to blue room
talk to Wild Joe
give coin, red pepper and rat to Wild Joe
take strange key from Wild Joe
open door to black room
go to black room
save princess

#3198

Числовые промежутки

Темы: [Разбор выражений]

Источники: [ Личные олимпиады, Открытая олимпиада школьников, 2010-2011, Заочный этап, Задача D ]

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

Интервал. Обозначается (x, y), включает в себя все числа z: x < z < y.
Полуинервалы. Обозначаются [x, y) и (x, y], включают в себя все такие z, что x ≤ z < y и x < z ≤ y соответственно.
Отрезок. Обозначается [x, y] и включает в себя все числа z: x ≤ z ≤ y.

В качестве домашней работы Васе досталось посчитать количество целых чисел в каждом из данных промежутков. Поскольку они ещё не проходили вещественных чисел, \(x\) и \(y\) рациональные: \(x\) = \(a \over b\) , \(y\) = \(c \over d\) (\(a\) и \(c\) целые, \(b\) и \(d\) целые положительные)

Рассмотрим пример: [\(3 \over 2\), 4) В данном случае \(d\) = 1, поэтому вместо \(4 \over 1\) пишут просто 4. В этом множестве содержится два целых числа: 2 и 3, а число 4 не содержится.

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

Входные данные

Первым символом идёт открывающаяся квадратная или круглая скобка. Далее записано число x в формате \(a \over b\) либо a, где |a| ≤ 10⁹, 0 < b ≤ 10⁹. После следует запятая и пробел. Потом — число y в таком же формате. Далее — закрывающаяся квадратная или круглая скобка. После неё идёт перевод строки и конец файла.

Гарантируется, что данный числовой промежуток не является пустым (то есть содержит в себе хотя бы одно число, не обязательно целое).

Выходные данные

По заданному числовому промежутку выведите единственное число — количество целых чисел в нём.

Примеры

Входные данные

[3/2, 4)

Выходные данные

Входные данные

[-2/4, 5/3]

Выходные данные

Входные данные

[-1000, 1000]

Выходные данные

Входные данные

[-2, 4/3]

Выходные данные

Страница: 1 Отображать по:

Выбрано

Отменить

Добавить в контест