読者です 読者をやめる 読者になる 読者になる

UVa10493 Cats, with or without Hats

問題文
http://uva.onlinejudge.org/external/104/10493.html

概要
葉ノード数がちょうど M で構成される N 分木は存在するか。
そのような N 分木のノード数が一意に定まるなら、"N M 全体のノード数" を出力。
複数存在するなら "Multiple" 存在しないなら "Impossible" を出力せよ。

問題文からわかる詳しい要件
ただし N >= 1 である。

解法
図を描く。木の深さを増すごとに必ず N-1 個分の新たな葉ノードができる。葉ノードがちょうど M 個になるとき 木の深さと全体のノード数が、ともに一意に定まる。
Multiple のケースは N = M = 1 のとき。木の深さを無限に増加させることができるため全体のノード数も無限に増える。

コーナーケースは 1つだけのノードで構成される N 分木である。全体のノード数を "Impossible" と出力せずに '1' を出力する。