ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Чемпионат УрГУ 2004

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

G. Репка

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
В очередной раз посадил дед репку. Каждый год он сажал по репке и каждый год одна и та же история — вырастает не репка, а настоящий гигант. То ли удобрения у деда качественные, то ли фамилия деда Мичурин, то ли соседство с атомной станцией не проходит бесследно. Как водится, выросла репка большая-пребольшая, а вытаскивать ее опять деду.
Попробовал дед обратиться за помощью к бабке, но ту еще с прошлого урожая разбил радикулит, внучку пришлось лечить в Швейцарии (дорого обошлась деду та репка), а у жучки, кошки и мышки образовалась аллергия на корнеплоды.
Загоревал дед. А что делать! Репку тащить-то надо!
И вспомнил он про книжечку заветную, что лежала у него на чердаке — про учебник Пёрышкина по физике для средней школы. И вспомнил дед, что в той книжке описывается замечательная вещь — блоки, с помощью которых можно собрать конструкцию, заменяющую собой в вопросах вытаскивания репки и бабку, и внучку, и жучку, и кошку, и мышку.
Достал дед учебник, почитал, — и собрал. И задумался: а насколько эта система поможет выиграть ему в силе? Сидит на крылечке, думает…
Блок представляет собой колесо, через которое перекинута верёвка, и к оси которого привязана ещё одна верёвка. Если верёвка, привязанная к оси уходит вверх, а концы, перекинутой верёвки смотрят, соответственно вниз, то это блок первого типа. Если же верёвка, привязанная к оси уходит вниз, а концы, перекинутой верёвки смотрят, соответственно вверх, то это блок второго типа.
Помогите деду по заданной конфигурации блоков первого и второго типов определить получаемый выигрыш в силе, пока урожай не сгнил. Блоки можно считать невесомыми, а верёвки невесомыми и нерастяжимыми. Два блока, соединённые верёвкой, находятся на разной высоте.

Исходные данные

В первой строке находится число N (1 ≤ N ≤ 32) — количество блоков. Блоки пронумерованы числами от 1 до N. В последующих N строках описываются сами блоки следующим образом: T X1 X2 Y, где T – тип блока (1 или 2), X1 и X2 – номера блоков, к которым идут концы верёвки, перекинутой через текущий блок, Y – номер блока, к которому идёт верёвка, привязанная к оси текущего блока. Однако есть несколько исключений:
  1. Некоторые уходящие вверх от блоков верёвки крепятся непосредственно к потолку теплицы. (Дед выращивал репку в теплице) В этом случае вместо номера блока, к которому идёт верёвка, указывается число 0.
  2. Ровно одна уходящая от блока вниз верёвка ведёт к репке массой 1 кг. В этом случае в строке описания I-го блока вместо номера блока указывается число –1.
  3. Ровно одна уходящая от блока вниз верёвка остаётся свободной. В этом случае, строке описания I-го блока, вместо номера блока указывается число –2.
Все верёвки вертикальны.

Результат

Вам необходимо вывести массу груза (с точностью 4 знака после десятичной точки), которую необходимо подвесить к свободной верёвке, чтобы система блоков пришла в равновесие. Если такой массы не существует, то вывести строку «No solution». Если подойдёт любая масса, то вывести строку «Any».

Примеры

исходные данныерезультат
2
1 -1 2 0
2 1 0 -2
2.0000
4
1 3 2 0
2 1 0 4
1 -1 4 1
2 3 2 -2
No solution
4
1 2 2 0
2 1 1 -2
1 4 4 0
2 3 3 -1
Any
Автор задачи: Павел Егоров
Источник задачи: USU Championship 2004
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1344. Репка