трубопровод

[Smitt&Wesson]

Сообщение от rrrFer

неа, он же 3 месяца решал задачу со сложностью 2% - т.е. ту, которая мало отличается от хелловорлда. А тут вдруг...

я не знаю что такое "открытый граф". Гугл тоже не знает. Дай ссылку почитать?

Как по мне, задача более чем тривиальная - нужен обыкновенный обход дерева.

Ссылки нет, но любое дерево, можно представить графом, как и граф - деревом. Листья "открытого графа", можно объединить в вершину с нулевым балансом хорд.
Тогда, его можно решить матричным методом. Есть у меня литературка на этот счёт, но рыться - лениво.

[Poma][a]

Есть у меня литературка на этот счёт, но рыться - лениво.

Просим! Просим!

неа, он же 3 месяца решал задачу со сложностью 2% - т.е. ту, которая мало отличается от хелловорлда. А тут вдруг...

Мда.. Логика зашкаливает..

Листья "открытого графа", можно объединить в вершину с нулевым балансом хорд.

Нулевой баланс хорд? Что это? Суммарная стоимость хорд = 0?

Как по мне, задача более чем тривиальная - нужен обыкновенный обход дерева.

Какой обход? Тут нужно дерево построить, а затем спускаться листа к корню (или Вы это имели ввиду под "обходом")
А вот как строить эту махину..?

И да.. если можно связать значение предка и его сына, то задача скатывается к циклу.. Осталось лишь вывести эту формулу.. Ну, кто смелый?

[Stilet]

Ребята, вы что на Докторскую идете?

[Smitt&Wesson]

Сообщение от Stilet

Ребята, вы что на Докторскую идете?

А почему-бы и нет? Вроде, как не запрещено.

[rrrFer]

Какой обход? Тут нужно дерево построить, а затем спускаться листа к корню (или Вы это имели ввиду под "обходом")
А вот как строить эту махину..?

Да, обход дерева - это именно то, что вы описали - можно в книжках посмотреть, можно даже в вики. Обходы могут быть разные, но суть не меняется.

Пошаговый перебор элементов дерева по связям между узлами-предками и узлами-потомками называется обходом дерева.

(с вики)

А вот как строить эту махину..?

Хитрость олимпиадных задач в том, что махину строить не надо (60 уровней дерева это очень много) - если будем строить то не пройдем тесты по времени (я гарантирую). Тут нужна только одна ветка дерева и, мне кажется, есть тут магия цифр.

По номеру начальной задвижки наверняка можно определить уровень. По номеру уровня и номеру начальной задвижки - определить родитескую задвижку. Вобщем ИМХО, надо посмотреть на рис. 1, почесать репу и придумать формулу. Посмотреть на рис. 2, проверить формулу. Написать программу.

[Stilet]

А почему-бы и нет? Вроде, как не запрещено.

Ну тогда во имя Ливерной - ГОСТ 1 вам, сударь, в помошь

rrrFer

Т.е.

s:string;
read(i);
case i of
 7,8:s:='4 2 1';
 9:s:='5 2 1';
 10,11:s:='6 3 1';
 4,5:s:='2 1';
 6:s:='3 1';
 2,3:s:='1';
end;
write(s);

Так чтоли?

[Smitt&Wesson]

Ребяты, либо я тупой, либо, задачка поставлена не корректно.
Либо, одно из двух.
Нельзя оптимизировать решение, простым обходом дерева. Ну, добрались мы до вершины, Каким боком, будут видны другие? Матрица, даёт соотношение. Дерево, такой особенностью не обладает.

[rrrFer]

Так чтоли?

Я не понял что это.

Кстати, там на acmp есть обсуждение. Люди там подверждают, что есть тут игра числами и деерво строить не нужно. Номера вершины более чем достаточно. По номеру можно определить родительский узел, и делать это до тех пор, пока номером не станет единица (ну это очевидно даже).

В обсуждении пишут про то, что задача сильно связана с числами Фибоначчи. Если посмотреть на элемент из которого строится трубопровод - то можно согласиться (ну что-то такое есть), но лично я не решал задачу, а сходу не обнаружил как именно сюда вкрутить фибоначчи. Кажется, числа фибоначчи должны отражать количество узлов на уровне.

Нельзя оптимизировать решение, простым обходом дерева. Ну, добрались мы до вершины, Каким боком, будут видны другие?

Дочернюю стопудово можно получить по номеру. Дочитай задачу до конца, посмотри как там вершины нумеруются.

[Smitt&Wesson]

rrrFer, Я так понимаю, в преобразованиях матиц в деревья и наоборот, Вы не очень. Любую матрицу, можно представить деревом, и любое дерево - матрицей. Закон транзакций.

[Poma][a]

Я так понимаю, в преобразованиях матиц в деревья и наоборот, Вы не очень.

Не-не-не.. Все гениально..

Кажется, числа фибоначчи должны отражать количество узлов на уровне.

Прекрасная гипотеза.. Пойду проверю.. Спасибо!

Я не понял что это.

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

Матрица, даёт соотношение.

Какое соотношение? Чего к чему?
Матрица здесь вообще ни как не поможет.. тут только химичить с указателями и списками.. (или магия чисел, как предложили выше)