問題一覧 > 通常問題

No.238 Mr. K's Another Gift

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 256 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 112
作問者 : evimaevima
1 ProblemId : 591 / 出題時の順位表
問題文最終更新日: 2015-11-14 17:49:15

問題文

(この問題は Codeforces Round #286 (Div. 2) の問題A の入力の制約を変更したものです。)

K氏が英小文字からなる文字列 $s$ をくれた。これに英小文字をちょうど一つ挿入して回文にしてほしいそうだ。
(回文とは、前から読んでも後ろから読んでも文字が同じ順番で出現するような文字列である。
例えば "noon", "testset", "a" はどれも回文であるが、 "test", "kitayuta" は回文ではない。)

挿入する文字としてどの英小文字を使ってもよく、それを $s$ のどの位置に挿入してもよい。
$s$ の先頭や末尾への挿入も可能である。
与えられた文字列 $s$ がすでに回文であっても、一文字を挿入しなくてはならない。

$s$ に英小文字を一つ挿入し、その結果文字列を回文にすることが可能ならば、そのようにして得られる回文を一つ出力せよ。
そうでなければ、 "NA" (引用符除く)と大文字で出力せよ。
得られる回文が複数存在する場合は、そのうちどれを出力してもよい。

入力

$s$

  • $1 \le |s| \le 10^5$
  • $s$ の各文字は英小文字である。

出力

$s$ に英小文字を一つ挿入して回文にすることが可能ならば、そのようにして得られる回文を一つ出力せよ。
そうでなければ、 "NA" (引用符除く)と大文字で出力せよ。
複数の解が存在する場合は、そのうちどれを出力しても正答となる。

サンプル

サンプル1
入力
revive
出力
reviver

末尾に 'r' を挿入すると回文になる。

サンプル2
入力
ee
出力
eye

この入力に対しては複数の解が存在する。例えば "eve" と出力しても正答となる。

サンプル3
入力
kitayuta
出力
NA

一文字を挿入するだけで回文にすることはできない。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。