2002db

Problem B: Pile Up! 積み上げろ！

1,2,3,・・・,mと番号が付いてる箱がある。「どの番号の箱をどの番号の箱の上に置け」という指示が与えられる。操作を全て行うと、積み上げた箱の列ができる。積み上げた数が小さい順に表示する。

「AをBに置け」という指示の時、次の場合がある。

• AとBが違う列にある場合
  • Aの上に何か乗っている場合は、乗っているものをすべて床に置いてからAを持ち上げる。
  • Bの上に何か乗っている場合は、そのまま一番上にAを置く。
• AとBが同じ列にある場合
  • AがBの下にある場合は、Aの上のものをすべて床に下ろしてから、AをBの上に置く。
  • AがBの上にある場合は、命令を無視する。
  • 「床に置け」という指示は「A 0」という命令になる。

入力

• まず、箱の数m
• 次にどの箱(I)を、どの箱(J)の上に置けと言う指示。IとJが0なら終了。

解答例

各列と、列にどの箱が置いてあるか、というデータ構造を2次元配列で表現し、命令どおりの処理を行う。処理が終わったら各列の個数を求め、ソートして小さい順に表示する。

• 河原 2002db1.c 無駄な処理があるかも。解けてないことが判明。