Темы
Информатика(2656 задач)
--->
173 задач
<---
Одна программистская компания решила разработать серию игр в жанре «Квест». Один из игроков сумел похитить сценарии игр, и теперь планирует составить описания прохождения всех квестов.
Во всех квестах приключения происходят в некотором здании, где имеется несколько комнат. Комнаты соединены друг с другом дверями. Чтобы открывать двери, можно использовать ключи. Также в игре присутствуют персонажи, объекты и предметы. Основная цель игры — спасти принцессу, которая находится в одной из комнат.
Игрок в квесте может поговорить с любым персонажем. После этого он узнает названия нескольких предметов, которые требуется принести этому персонажу, чтобы тот в свою очередь дал игроку некоторые другие предметы. Некоторые предметы можно найти на полу комнат. Также игрок может использовать предметы на объектах. В результате этого он получает некоторые другие предметы.
Напишите программу, которая, получив описание игрового мира квеста, создает описание его прохождения — последовательность действий, которые игрок должен совершить, чтобы успешно пройти квест — спасти принцессу.
Первая строка входного файла содержит число \(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
Из множества всех натуральных чисел от \(1\) до \(N\) требуется выделить такое подмножество, чтобы в нем не было бы никаких двух чисел, отличающихся ровно в два раза (то есть если некоторое число \(X\) входит в это подмножество, то число \(2X\) заведомо в него не входит).
Напишите программу, которая по введенному числу N определяет, какое наибольшее количество чисел от \(1\) до \(N\) может быть включено в такое подмножество.
Например, для \(N=8\) ответ \(5\), подмножество может быть таким: \(1, 3, 4, 5, 7\).
Вводится одно натуральное число \(N\) (\(1\) ≤ \(N\) ≤ \(10^9\)).
Выведите искомое максимальное количество чисел от \(1\) до \(N\), которые могут быть включены в подмножество так, чтобы в этом подмножестве не оказалось бы чисел, отличающихся ровно в два раза.
8
5
50
33
В неориентированном связном графе \(N\) вершин и \(M\) ребер, каждое из которых имеет вес, выражающийся натуральным числом (разные ребра могут иметь разные веса). В графе нет петель (т.е. ребер, ведущих из вершины в нее саму) и кратных ребер (т.е. между любыми двумя вершинами не более одного ребра).
Весом пути из одной вершины до другой называется сумма весов ребер, по которым этот путь проходит. Кратчайшим путем между двумя вершинами называется путь минимального возможного веса между этими вершинами. Считается, что длина кратчайшего пути от вершины до неё самой равна нулю.
В этом графе вычислили длины кратчайших путей между всеми парами вершин и записали их в виде таблицы. В этой таблице число на пересечении \(i\)-ой строки \(j\)-ого столбца равно длине кратчайшего пути из вершины номер \(i\) в вершину номер \(j\).
После этого исходный граф был утерян.
Напишите программу, которая по заданной таблице кратчайших расстояний восстановит какой-нибудь граф, которому эта таблица могла бы соответствовать, либо установит, что графа описанного в условии вида, которому могла бы соответствовать данная таблица, не существует.
Вводятся числа \(N\) и \(M\), а затем таблица кратчайших расстояний (\(1 ≤ N ≤ 300, 0 ≤ M ≤ 1000\), элементы таблицы кратчайших путей — целые неотрицательные числа, не превышающие \(10^6\)).
Если такой граф существует, выведите в первой строке сообщение YES, в противном случае — сообщение NO. Если граф существует, то начиная со второй строки выведите \(M\) троек чисел, описывающих ребра. Каждое ребро описывается номерами вершин, которые оно соединяет, и весом. Веса всех ребер не должны превышать \(10^6\).
4 4 0 1 2 5 1 0 3 4 2 3 0 7 5 4 7 0
YES 1 2 1 1 3 2 2 4 4 1 4 5
3 2 0 1 1 1 0 1 1 1 0
NO
Петя занимается разведением дракончиков. У него есть \(M\) зеленых дракончиков и \(K\) желтых. У Пети есть \(N\) двухместных аквариумов для дракончиков и \(M+K–2N\) одноместных.
Петя, понаблюдав некоторое время за своими дракончиками, установил, что некоторые пары дракончиков не могут жить вместе (будучи помещенными в один аквариум они тут же начинают драться), а также некоторые дракончики совершенно не переносят одиночества и поэтому не могут жить в одноместном аквариуме.
Петя хочет с использованием своих знаний так разместить дракончиков по аквариумам, чтобы в каждом двухместном аквариуме обязательно был один зеленый дракончик и один желтый, и при этом драконы, не переносящие одиночества, обязательно были бы помещены в двухместный аквариум, и в двухместном аквариуме никогда не оказывалось бы двух драконов, которые не могут жить вместе.
Вводятся числа \(M, K, N\) (\(M ≥ 1, K ≥ 1, N ≥ 0, N ≤ M, N ≤ K, M + K ≤ 200\)). Будем считать, что зеленые дракончики пронумерованы числами от \(1\) до \(M\), а желтые – числами от \(M+1\) до \(M+K\).
Далее идет число \(T\) (\(0 ≤ T ≤ MK\)) – количество пар дракончиков, про которых известно, что они не переносят друг друга. Далее идет \(T\) пар чисел, описывающих номера не переносящих друг друга дракончиков (первое число каждой пары описывает зеленого дракончика, второе – желтого). Далее идет число \(Q\) (\(0 ≤ Q ≤ M + K\))– количество дракончиков, не переносящих одиночества. Далее идет \(Q\) чисел, задающих номера этих драконов.
В случае если разместить дракончиков по аквариумам требуемым образом нельзя, выведите единственное слово NO. В противном случае первая строка должна содержать YES. В следующие \(N\) строк выведите \(N\) пар чисел, задающих номера дракончиков, которых нужно поместить в двухместные аквариумы.
2 1 1 1 1 3 1 1
NO
2 2 1 1 1 3 1 2
YES 2 4
Вася увлекается изобретением новых последовательностей и их исследованием. В этот раз он выписал на доске последовательность:
1 2 3 2 3 4 3 4 5 4 5 6 5 6 7...После этого Вася задался вопросом, на каком месте в ней впервые встретится число \(k\)?
Напишите программу, которая ответит на его вопрос.
Вводится натуральное число \(k\) (\(1 ≤ k ≤ 100\)).
Выведите одно число – искомую позицию, на которой первый раз встретилось число \(k\). Члены последовательности нумеруются с единицы.
1
1
2
2
4
6