時間制限:1000ミリ秒
メモリ制限:30000KB
主 X-部分因子列
問題
nを任意の正の整数とする。nの因数とは、nを余りなしに割り切る任意の数のことである。例えば、52÷13=4なので、13は52の因数である。nの部分列とは、リーディングゼロのない数字で、nの10進表記から1つかそれより多くの桁を除去した数である。例えば、2, 13, 801, 882, それと1324は8013824の部分列である。いっぽう、214は部分列ではない(桁の並び替えはできない)。8334も部分列ではない(オリジナルの数字を重複させて出現させている),8013824も部分列ではない(少なくとも1桁は除去しなければならない)。また01も部分列ではない(リーディングゼロは禁止)。nの部分因子とは、1より大きい整数で、nの因数であってかつnの部分列であるようなもののことである。8013824は8, 13, 14という部分因子をもつ。部分因子をもたない数もある; 例えば、6341は6,3,4,63,64,61,34,31,41,634,631,641,341のいずれにも整除されない。
nのX-部分因子列とは、単調減少な整数列n1, ..., nkであって、
(1) n = n1
(2) k ≧ 1
(3) 全ての1 ≦ i < kなるiについて、n_{i+1}はn_iからn_iの部分因子のもつ桁を除去し、続いてリーディングゼロを(存在するならば)除去することで得られる数である。
(4) n_kは部分因子をもたない。
という条件を満たす数列のことである。「X-部分因子」という言葉は、数字が進むにつれて、部分因子がxされるか、または破棄される、という意味を意図している。例えば、2004は2つの異なるX-部分因子列をもつ。そのうち1つは、2つの方法によって生成される。下記の列は部分因子列を生成するために部分因子が除去されていく様子をあらわしたものである。
2004 4
2004 200 0
2004 200 0
主 X-部分因子列とは、最大長(上記における最大のk)を与えるX-部分因子列のことである。最大長が複数ある場合は、二項目が小さいものが主 X-部分因子列である。もしそれでも決まらなければ、三項目が小さいものを選ぶ。以下同様。全ての正の整数がユニークな主 X-部分因子列をもつ。(主でないものは複数のケースがあるかもしれない。2004の例のように)
入力
入力は1つかそれより多くの正整数からなる。それぞれは1,000,000,000より小さく、リーディングゼロを含まない。1行に1つの数が書かれている。入力の最後には、入力の終わりを意味する0が含まれている。
出力
各々の入力された正整数について、その主 X-部分因子列を、先述のフォーマット通りに出力せよ。
入力例
123456789 7 2004 6341 8013824 0
出力例
123456789 12345678 1245678 124568 12456 1245 124 12 1 7 2004 200 0 6341 8013824 13824 1324 132 12 1
出典
Mid-Central USA 2004