0 / 0 / 0
Регистрация: 07.09.2019
Сообщений: 3
1

Задача H. Мадагаскар [C, B’]

07.09.2019, 15:51. Показов 807. Ответов 0

Лев Алекс, будучи истинным царем зверей, подарил на День Рождения Марти игрушечный зоопарк. Эта модель зоопарка крайне простая и ее можно представить как линию, на которой расположены звери и кормушки с едой для них. Каждый из зверей принадлежит какому-то виду. Зверь
может кушать только ту еду, которая предназначена для его вида, и для каждого вида эта еда
различна.
Марти уже расставил суммарно 2n зверей и кормушек на линии. В зоопарке количество кормушек равно количеству зверей. Теперь он хочет начать процесс поедания зверем еды из кормушек.
Один шаг этого процесса выглядит следующим образом:
1. Марти выбирает какого-то зверя, стоящего на линии.
2. Он двигает его в какую-то сторону вдоль этой линии.
3. Зверь не должен столкнуться ни с каким другим зверем или кормушкой за исключением кормушки с едой, соответствующей виду этого зверя.
4. Когда зверь находится в той же точке, что и кормушка с едой его вида, он съедает всю еду, и
тогда Марти убирает и этого зверя, и эту кормушку с линии.
Помогите узнать Марти, можно ли провести этот процесс так, чтобы животных на линии не
осталось, иными словами, все животные были накормлены.

Формат входных данных
Первая строка содержит строку из 2n(1 6 n 6 50000) символов латинского алфавита. Если i-й
символ строки является строчной буквой, это значит, что на i-м месте линии, если перечислять объекты на линии слева направо, стоит кормушка с едой, которую могут есть звери вида, обозначаемого
соответствующим заглавным символом. Если же i-й символ строки является заглавной буквой, то
на i-м месте линии стоит зверь вида, обозначаемого этим символом.

Формат выходных данных
Если невозможно провести процесс желанным образом, выведите «Impossible».
Если это возможно, выведите «Possible», а затем для каждого из зверей в том порядке, в
котором они описаны во входных данных, выведите порядковый номер кормушки, еду из которой
он должен съесть. Кормушки нумеруются с 1 в порядке, в котором даны во входных данных.

Примеры
ABba Possible 2 1

ABab Impossible

Замечание
В первом примере зверь B съест еду из кормушки b, а затем зверь A съест еду из кормушки a.
Во втором примере для зверя A подойдет только кормушка a, а для зверя B — кормушка b.
Решения не существует, поскольку ни один из них не может достигнуть желаемой еды, ведь иначе
он столкнется с чем-то другим.
0

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
07.09.2019, 15:51
Ответы с готовыми решениями:

Мадагаскар
Лев Алекс, будучи истинным царем зверей, подарил на День Рождения Марти игрушечный зоопарк. Эта...

Мадагаскар
Лев Алекс, будучи истинным царем зверей, подарил на День Рождения Марти игрушечный зоопарк. Эта...

Задача: В некотором государстве ввели компьютерный паспорт гражданина.(задача)
Доброго времени суток,форумчане. Хотелось бы попросить помощи в решении одной задачи от умных...

Задача на k-тую цифру последовательности, задача на схему Горнера.
Ну, собственно опять прошу помощи... Задача 1: Определить k-тую цифру последовательности...

0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
07.09.2019, 15:51

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Задача на перебор вариантов. Задача Л.Эйлера. Про чиновника
Задача Л.Эйлера. Некий чиновник купил лошадей и быков на сумму 1770 талеров. За каждую лошадь он...

Первая смешанная задача для волнового уравнения на отрезке (задача о колебаниях ограниченной струны) методом Фурье
Решить первую смешанную задачу для волнового уравнения на отрезке (задача о колебаниях ограниченной...

Задача о размещении весов по ящикам (задача о рюкзаках)
Есть упорядоченный по невозрастанию набор весов предметов w1..wn, которые необходимо распределить...

Задача на файл и задача на создание очереди
1 Дан символьный файл, содержащий, по крайней мере, один символ пробела. Удалить из файла все...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.