Вот приходится осваивать теорию графов

[st256]

Вумные все-таки были эти графья :)

Вопрос такой. Пусть у меня есть граф (или виконт?), у которого весят $N$ вершин. Можно сказать, что эти вершины - мои исходные данные, массив длинной $N$.

Необходимо при помощи дуг эти вершины соеденить (через промежуточные вершины) с некой конечной вершиной. Это типа результат операции над исходным массивом данных длинной $N$.

При этом, в одну промежуточную вершину может входить не более 3-х дуг и выходить не более 1-й.

Собственно вопрос: найти минимально-возможное количество промежуточных вершин.

[paha]

Обозначим искомую величину через $P(N)$.

Очевидно, что $P(3)=0$ и $P(3N-1)=P(3N-2)=P(3N)=P(N)+N$.