JOI logo

第5回日本情報オリンピック 模擬試験1

2005年11月7日
情報オリンピック日本委員会

問題

 J中学校の運動会で次のようなクラス対抗の競技を行なうことになった. 各クラスから生徒代表の男女 n ペア

   (男子生徒 b1, 女子生徒 g1), (男子生徒 b2, 女子生徒 g2), … , (男子生徒 bn, 女子生徒 gn)

を選び, 0 から 9 までの数字が書かれた旗を自由に選んでもらい (それぞれの旗は十分な個数ある), 横一列に並んでもらう. ただし, ペアになっている男子生徒と女子生徒は同じ番号の旗を一人1つずつ 選ばなければならず, 並び順は

   b1 b2 … bn c gn … g2 g1

のように, 男子生徒達 n 人の並び順 b1 b2 … bn とは逆の順番 gn … g2 g1 で女子生徒達は 並ばなければならない. 中央の c には, クラス担任の先生があらかじめ審判長によって指定された 番号の付いた旗を持って立つ場合と, 立たないことを審判長に指定される場合とがある.

 こうして並んだ生徒達(と先生)が持った旗の番号 を 2n 桁(または 2n+1 桁)の整数と考えたとき, それが素数である方が勝ちである. ただし, 両クラスとも素数だった場合あるいは両クラスとも素数でなかった場合には, 数が大きい方が勝ちである. また,

   0 b2 … bn c gn … g2 0  あるいは  0 b2 … bn gn … g2 0

のように先頭に 0 が来るものは, 普通使われる数の表し方ではないので禁止されている.

 J中学校の生徒であるあなたは, 自分のクラスが勝つためにはどのように並ぶのがよいかを 考えなければならない.

 入力ファイルの1行目に正整数 n と 1桁の整数 c(先生が持つ旗の番号)が 1つの半角空白文字で区切られて書かれている. c<0 のときは, 先生が中央に立たないことを表わす. 5つの入力ファイルのうち4つでは 1≦n≦4 である.

 負けない並び方の順番

   b1 b2 … bn c gn … g2 g1  または  b1 b2 … bn gn … g2 g1

を出力せよ.

 入力ファイルの改行コードは CR+LF である. また, 出力ファイルにおいては, 出力の最後にも改行コードを入れること.

入力例1 入力例2 入力例3 入力例4
1 0 1 5 3 7 1 -1
出力例1 出力例2 出力例3 出力例4
101 757 9957599 11