Повар Павел любит рекурсивные салаты. Например, его любимый салат «раздув» состоит из 30% огурцов, 20% помидоров и 50% салата «разгон». Салат «разгон» состоит из 40% хлеба, 20% огурцов и 40% салата «раздув».
Для каждого из любимых салатов Павла известен его рецепт в виде процентного содержания всех его составляющих. Составляющим салата может быть базовый ингредиент или другой салат. Ваша задача — составить рецепты салатов Павла, в которых бы все составляющие являлись базовыми ингредиентами.
Исходные данные
Входные данные содержат рецепты салатов Павла.
Названия салатов и базовых ингредиентов состоят из строчных латинских букв и имеют длину не более 10. Если для какого-то составляющего указан рецепт, то оно является салатом. В противном случае, оно является базовым ингредиентом. Все рецепты перечислены в лексикографическом порядке названий салатов. Все составляющие в рецепте также перечислены в лексикографическом порядке. Все процентные содержания являются целыми числами от 1 до 100, сумма процентных содержаний в одном рецепте равняется 100.
В общей сложности входные данные содержат не более 10 различных салатов и не более 10
различных базовых ингредиентов. Используйте формат входных данных, приведённый в примерах.
Результат
Выведите рецепты салатов Павла, в которые входят только базовые ингредиенты. Рецепты и составляющие в каждом рецепте должны быть перечислены в лексикографическом порядке. Процентные содержания должны быть выведены с абсолютной или относительной погрешностью не более 10−3. Сумма процентных содержаний в каждом рецепте должна равняться 100. Если в салат не входит некоторый базовый ингредиент, его название должно быть выведено с процентным содержанием 0. Гарантируется, что входные данные таковы, что задача всегда имеет в точности одно решение.
Примеры
исходные данные | результат |
---|
razduv : cucumber 30 razgon 50 tomato 20
razgon : bread 40 cucumber 20 razduv 40
| razduv : bread 25.0 cucumber 50.0 tomato 25.0
razgon : bread 50.0 cucumber 40.0 tomato 10.0
|
razduv : cucumber 100
razgon : tomato 100
| razduv : cucumber 100.0 tomato 0
razgon : cucumber 0 tomato 100.0
|
Автор задачи: Павел Климов
Источник задачи: Открытый командный чемпионат УрФУ по программированию — 2013