시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
8 초 (추가 시간 없음) | 1024 MB | 2 | 2 | 2 | 100.000% |
あなたは "二進の錬金術師" の名を与えられた著名な錬金術師である.その二つ名が表す通り,求めに応じて '0' と '1' からなる二進文字列を意のままに錬成するのがあなたの得意分野だ.ただし,錬金術の基本は等価交換.無から有を生み出すことはできない.そのためあなたは以下の手順に従って二進文字列を錬成する.
あなたは与えられた二進文字列 t と二進文字列集合 S に対し,S を素材となる文字列集合とし,上記の手順に従って t を錬成したい.このとき,t を錬成する手順が複数通り考えられる場合,手順 3. における交換回数が少ないほど錬成に必要なエネルギーを抑えられるため,好ましい.それでもまだ複数通りの手順が考えられる場合,手順 2. の終了時点での二進文字列のうち辞書順で最小のものを採用することで錬成陣を簡潔化できるため,より望ましい.
あなたはできる限り瞬時に術を発動できるようにするため,補助装置として手順 2. の終了時点での最適な文字列を自動で求めるプログラムを開発することにした.ここで,どのような手順を踏んでも手持ちの S からは t を錬成できない場合も考えられる.その場合は "IMPOSSIBLE" と出力することとする.
入力は複数のデータセットからなる.
各データセットは 1 つの整数 n を含む 1 行から始まる.これは文字列集合 S に含まれる文字列が n 個であることを表し,1 ≤ n ≤ 100 を満たす. 続く n 行の i 行目は,S に含まれる i 番目の二進文字列 Si を表す.Si は '0' もしくは '1' のみからなり,その長さ |Si| は 1 ≤ |Si| ≤ 100 を満たす.すべての 1 ≤ i < j ≤ n について,Si ≠ Sj を満たすことが保証される. 続く 1 行は錬成したい文字列 t を表す.t は '0' もしくは '1' のみからなり,その長さ |t| は 1 ≤ |t| ≤ 100 を満たす.
入力の終わりは 1 つのゼロからなる行で表される. 全データセットの総数は 100 を超えない.
t を錬成する手順の過程として手順 2. の終了時点で作られうる文字列を 1 行に出力せよ.ただし,そのような文字列が複数考えられる場合,手順 3. における隣り合った 2 文字の交換回数が最小となる文字列を出力せよ.それでも複数考えられる場合,辞書順で最小のものを出力せよ.そのような文字列が存在しない場合,"IMPOSSIBLE" と出力せよ.
2 00 1 010 3 110 011 0 010010 3 110 010 11 0110010 0
001 000110 IMPOSSIBLE