Numoeba / ナミーバ

 A scientist discovered a strange variation of amoeba. The scientist named it numoeba. A numoeba, though it looks like an amoeba, is actually a community of cells, which always forms a tree. ...

( 2000 ACM ICPC Asia Regional Contest, Tsukuba, Problem F より)

ナミーバとは

ナミーバは木構造をなす細胞の集合体で，時間経過に伴いその形状を変化させる．

各細胞はナムボソームと呼ばれる正の奇数を持っている． ナムボソームは，3n+1問題(あるいはCollatzの予想)の基本演算，すなわち，

3倍して1を足し，奇数になるまで2で割る．

にもとづき，時間の経過とともに変化する．

例: 15 → 23 → 35 → 53 → 5 → 1

細胞の死滅や分裂は，以下のルールに従う． (詳しくは， ICPCの問題 か [2] を参照)

• ナムボソームが 1 になると，その細胞は死滅する．

• 木構造の上位が死ぬと下位も死ぬ(例外有り)．特にリーダが死ぬと全体が死ぬ．

• 最大ナンボソームを持つ細胞がリーダとなり，木構造のルートとなる． 最大値が複数ある場合は，前のリーダが留任する．

• リーダ細胞は新しい細胞をうむ(リーダボーナス)．

• ナムボソームが増加した葉細胞は新しい細胞を生む(葉ボーナス)．