TopCoder SRM675_Div1 : TreeAndPathLength3
TopCoder Statistics - Problem Statement
問題
入力として整数s(1 <= s <= 10000)が与えられる。
使用できるノードの数が500までとし、長さ3の単純パスの数が丁度sとなるように
木を構築せよ。 という問題。
解法
sに対して使用できるノード数が500のため、一本道の木ではパスの数が足りない。
0 - 1 - 2 - 3 - 4 の木を最初に作り、橋1 - 2を中心にノードを足し
乗算でパスの数が増えるようにして木を構築した。
途中でパスの数がsを超過したら、最後に足したノードを削除しノード4からエッジを1本ずつ足しsになるように調節する。
以下はs=8の時の図。
