--->
78 задач
<---
Источники
Одна программистская компания решила разработать серию игр в жанре «Квест». Один из игроков сумел похитить сценарии игр, и теперь планирует составить описания прохождения всех квестов.
Во всех квестах приключения происходят в некотором здании, где имеется несколько комнат. Комнаты соединены друг с другом дверями. Чтобы открывать двери, можно использовать ключи. Также в игре присутствуют персонажи, объекты и предметы. Основная цель игры — спасти принцессу, которая находится в одной из комнат.
Игрок в квесте может поговорить с любым персонажем. После этого он узнает названия нескольких предметов, которые требуется принести этому персонажу, чтобы тот в свою очередь дал игроку некоторые другие предметы. Некоторые предметы можно найти на полу комнат. Также игрок может использовать предметы на объектах. В результате этого он получает некоторые другие предметы.
Напишите программу, которая, получив описание игрового мира квеста, создает описание его прохождения — последовательность действий, которые игрок должен совершить, чтобы успешно пройти квест — спасти принцессу.
Первая строка входного файла содержит число \(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
В марсианских сутках \(N\) часов. У марсиан Ятеп и Ашам есть часы со стрелками, которые работают почти так же, как земные – большая стрелка делает один оборот в час, а маленькая – один оборот в сутки. Ятеп и Ашам поссорились и решили не разговаривать, пока стрелки часов не совпадут. Определите точный момент времени, когда это случится.
Во входном файле задано число тестов \(K\) (0 ≤ \(K\)<\(10^4\)), далее для каждого теста указаны целые числа \(N\), \(A\), \(B\) и \(C\) (1<\(10^9\), 0 ≤ \(A\), 0 ≤ \(B\) < \(10^9\)). Числа \(A\), \(B\) и \(C\) означают, что Ятеп и Ашам поссорились в \(A\)+\(B\)/\(C\) часов.
Для каждого теста выведите искомое время в том же формате: числа \(A\), \(B\) и \(C\), такие, что искомое время равно \(A\)+\(B\)/\(C\) (0 ≤ \(A\), 0 ≤ \(B\), дробь \(B\)/\(C\) – несократимая).
2 12 11 0 1 12 0 0 1
0 0 1 1 1 11
В городе \(n\) автобусных остановок, через которые проходят \(k\) кольцевых автобусных маршрутов. Каждый маршрут задается списком номеров остановок, через которые он проходит, \(i\)-ый маршрут проходит по остановкам \(a_{i, 1}\), \(a_{i, 2}\), …, \(a_{i, l_i}\) (в этом порядке). По маршруту ходит ровно один автобус. В момент времени 0 этот автобус находится на остановке \(a_{i,1}\). На то, чтобы доехать до следующей на своем маршруте остановки, автобус тратит ровно одну минуту. Временем стоянки автобуса на остановке можно пренебречь. Все маршруты кольцевые, то есть через минуту после остановки \(a_{i, l_i}\) автобус оказывается на остановке \(a_{i, 1}\) и едет по маршруту еще раз.
Несколько человек в этом городе решили покататься на автобусах. При этом каждый из них составил план своего катания. План \(j\)-го человека состоит из остановки \(b_j\), на которой человек начнет свое катание и последовательности чисел \(c_{j, 1}\), \(c_{j, 2}\), …, \(c_{j, m_j}\). Эти числа означают следующее: в момент времени 0 человек придет на остановку \(b_j\) и дождется ближайшего автобуса (если в этот момент какой-то автобус находится на остановке \(b_j\), человек сядет в него). На этом автобусе он проедет \(c_{j, 1}\) остановок, после чего выйдет и дождется следующего автобуса на той остановке, где он окажется. На нем он проедет \(c_{j, 2}\) остановок, снова выйдет и снова дождется следующего автобуса. И так далее. Если в какой-то момент к остановке подъедет сразу несколько автобусов, то человек сядет в автобус с минимальным номером маршрута. Когда человек выходит из автобуса на какой-то остановке, он может уехать с этой остановки не раньше, чем через минуту.
Для каждого человека определите, через сколько минут после начального момента и на какой остановке закончится его катание.
Во входном файле записано сначала число \(n\), затем число \(k\). Далее записано \(k\) строк, задающих автобусные маршруты. Каждая строка начинается с числа \(l_i\), задающего длину маршрута, затем идет список остановок, через которые проходит маршрут: \(a_i\),1, \(a_i\),2,… \(a_i\),\(l_i\). Маршрут может несколько раз проходить через одну и ту же остановку.
Далее идет число \(p\) – количество людей, и затем p строк, задающих планы людей. Каждая строка содержит сначала числа \(b_j\) – номер начальной остановки и \(m_j\) – количество чисел в последовательности. Затем идут числа \(c_j\),1, \(c_j\),2, …, \(c_j\),\(m_j\).
Все числа во входном файле натуральные и не превышают 50.
В выходной файл для каждого человека выведите два числа: время в минутах, когда закончится его катание, и номер остановки, на которой это произойдет. Если же человек не сможет реализовать свой план до конца (на какой-либо остановке он не дождется автобуса), выведите для него два нуля.
6 4 4 1 2 3 5 2 3 4 5 5 2 1 3 2 2 4 3 3 1 4 1 2 3 4 2 1 1 6 3 1 2 3
20 1 2 3 0 0
Мальчику Васе очень нравится известная игра «Сапер». В нее играет один человек. Игра идет на клетчатом поле размером \(m\)×\(n\) (\(m\) строк, \(n\) столбцов). В некоторых клетках поля стоят мины. В каждой из остальных клеток записано либо число от 1 до 8 – количество мин в соседних с ней клетках, либо ничего не написано – это означает, что в соседних клетках мин нет. Клетки являются соседними, если они имеют хотя бы одну общую вершину. В одной клетке не может стоять более одной мины. Будем называть поле с расположенными на нем минами и числами картой.
Изначально все клетки поля закрыты. Игрок за один ход может открыть какую-нибудь клетку. После этого игроку показывается содержимое этой клетки, и если в открытой им клетке оказывается мина, он проигрывает. В противном случае игра продолжается. Цель игры – открыть все клетки, в которых нет мин.
У Васи на компьютере есть эта игра, но ему кажется, что все карты, которые в ней есть, некрасивые и неинтересные. Поэтому он решил нарисовать свои. При этом он хочет, чтобы карты, которые он нарисует, после того, как они будут открыты, выглядели красиво.
У Васи есть рисунки, нарисованные на клетчатой бумаге следующим образом: некоторые клетки закрашены в черный цвет, а некоторые оставлены белыми. Вася хочет по каждому такому рисунку сделать соответствующее ему поле для игры в «Сапера» по следующему правилу: если на рисунке клетка покрашена в черный цвет, то на этом месте должна быть либо мина, либо число от 1 до 8, если же клетка оставлена белой, то на игровом поле она должна быть пустой.
Напишите программу, которая сделает это за Васю.
В первой строке входного файла содержатся числа \(m\) и \(n\) (1 ≤ \(m\), \(n\) ≤ 100) – количество строк и столбцов соответственно. Далее идет таблица из \(m\) строк, по \(n\) чисел в каждой строке, задающая Васин рисунок. Каждое число в таблице равно 0 или 1, число 0 означает, что соответствующая клетка на рисунке белая, 1 – черная. Числа в строках разделяются пробелами.
Выходной файл должен содержать \(m\) строк по \(n\) символов – карту игрового поля, \(j\)-ый символ \(i\)-ой строки должен содержать символ «*» (звездочка) если в клетке (\(i\),\(j\)) стоит мина, цифру от 1 до 8, если в этой клетке стоит соответствующее число, либо «.» (точка), если клетка (\(i\),\(j\)) пустая. Символы пробелами не разделяйте. Если построить поле, соответствующее рисунку, невозможно, выходной файл должен содержать одну строку с сообщением «No solution».
3 5 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0
***** 23332 .....
3 3 0 1 0 0 0 0 0 0 0
No solution
В школе продолжительность каждого урока 45 минут, а перемены между уроками – всего 5 минут. Первый урок начинается ровно в 8 часов утра. Напишите программу, отвечающую на вопрос «во сколько в этой школе заканчивается \(K\)-ый урок?»
Вводится одно натуральное число \(K\), не превышающее 15.
Выведите время окончания \(K\)-ого урока: сначала часы, потом минуты, разделяя их пробелом.
1
8 45
6
12 55