WARush

SRMの結果とか、解けた問題のコードを書いていきます

SRM585 Div2 Medium "TrafficCongestionDivTwo"

問題

http://community.topcoder.com/stat?c=problem_statement&pm=12697

いくつかの都市があり、道路でつながっている。道路網の構造は、都市をノード・道路をエッジとしたときに完全二分木になっている。

あなたは木の高さを表すint treeHeightが与えられる。(完全二分木の高さとは、木のルートノードとリーフノードを結ぶ道路の数である)したがって、2^(treeHeight+1)-1だけの都市と、2^(treeHeight+1)-2だけの道路の数があることになる。

私たちはいくつかの車をこの道路網に送りたい。それぞれの車は出発する都市から目的の都市まで、同じ年を2度通らずに走る。(それぞれの車のルートは、出発地と目的地によって、一意に決められる事に注意せよ)出発する都市と、目的の都市は同じでもよく、この場合車は1つの都市を訪れるだけである。

私たちの目的はそれぞれの都市を訪れる車をちょうど1台にして、車を送り出すことである。このようにしたときに、送り出す車の最小を返せ。

制約

0 <= treeHeight <= 60




Editorials見たけど

これが最小だってなんでいえるのかよく分からん。