В очередной раз посадил дед репку. Каждый год он сажал по репке и каждый год одна и та же история — вырастает не репка, а настоящий гигант. То ли удобрения у деда качественные, то ли фамилия деда Мичурин, то ли соседство с атомной станцией не проходит бесследно. Как водится, выросла репка большая-пребольшая, а вытаскивать ее опять деду.
Попробовал дед обратиться за помощью к бабке, но ту еще с прошлого урожая разбил радикулит, внучку пришлось лечить в Швейцарии (дорого обошлась деду та репка), а у жучки, кошки и мышки образовалась аллергия на корнеплоды.
Загоревал дед. А что делать! Репку тащить-то надо!
И вспомнил он про книжечку заветную, что лежала у него на чердаке — про учебник Пёрышкина по физике для средней школы. И вспомнил дед, что в той книжке описывается замечательная вещь — блоки, с помощью которых можно собрать конструкцию, заменяющую собой в вопросах вытаскивания репки и бабку, и внучку, и жучку, и кошку, и мышку.
Достал дед учебник, почитал, — и собрал. И задумался: а насколько эта система поможет выиграть ему в силе? Сидит на крылечке, думает
Блок представляет собой колесо, через которое перекинута верёвка, и к оси которого привязана ещё одна верёвка. Если верёвка, привязанная к оси уходит вверх, а концы, перекинутой верёвки смотрят, соответственно вниз, то это блок первого типа. Если же верёвка, привязанная к оси уходит вниз, а концы, перекинутой верёвки смотрят, соответственно вверх, то это блок второго типа.
Помогите деду по заданной конфигурации блоков первого и второго типов определить получаемый выигрыш в силе, пока урожай не сгнил. Блоки можно считать невесомыми, а верёвки невесомыми и нерастяжимыми. Два блока, соединённые верёвкой, находятся на разной высоте.
Исходные данные
В первой строке находится число N (1 ≤ N ≤ 32) — количество блоков. Блоки пронумерованы числами от 1 до N. В последующих N строках описываются сами блоки следующим образом: T X1 X2 Y, где T – тип блока (1 или 2), X1 и X2 – номера блоков, к которым идут концы верёвки, перекинутой через текущий блок, Y – номер блока, к которому идёт верёвка, привязанная к оси текущего блока. Однако есть несколько исключений:
- Некоторые уходящие вверх от блоков верёвки крепятся непосредственно к потолку теплицы. (Дед выращивал репку в теплице) В этом случае вместо номера блока, к которому идёт верёвка, указывается число 0.
- Ровно одна уходящая от блока вниз верёвка ведёт к репке массой 1 кг. В этом случае в строке описания I-го блока вместо номера блока указывается число –1.
- Ровно одна уходящая от блока вниз верёвка остаётся свободной. В этом случае, строке описания 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