아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

ぶりしゃぶしゃぶり部

시간 제한8초메모리 제한1024 MB

요약
S의 회문스러움을, 뒤쪽 절반에서 서로 겹치지 않는 구간을 골라 뒤집어 S를 회문으로 만들 때 구간 길이 제곱 합의 최솟값으로 정의하고, 불가능하면 -1을 출력한다.
난이도

보통10점 중 7점

유형
문자열, 동적 계획법
정답자
아직 제출이 없습니다

문제

次のニュースです．新型コロナウイルスの感染拡大により飲食店以外でのよりよい食事を求める動きが強まる中，ある部活動が注目を集めています．

その名も，ぶりしゃぶしゃぶり部．この新しい活動に取り組む，都内のあるグループを取材しました．

渋谷区のマンションの一室．10 代から 30 代までの若い男女が集まって鍋を囲っています．「このカニもういけるんじゃない？」「あ，ほんとだ」 外から見る限りは，普通のカニ鍋のようです．ぶりですらないようですが……？

このグループの代表を務める男性に話を聞きました． ICPC-JAG (International Collegiate Programming Contest Japanese Alumni Group) 代表 N さん「今日はICPC模擬国内予選の打ち上げです．」 記者「えっ，じゃあぶりしゃぶしゃぶり部というのはいったいなんなんでしょう？」 N さん「ぶりしゃぶしゃぶり部って回文っぽくないですか？」 記者「か，回文……？」 N さん「回文というのは，前から読んでも後ろから読んでも同じになる文のことです．回文っぽいっていうのは，そうですね……」

JAGのメンバーでありこの会話を横で聞きながらカニ鍋をつついていたあなたは，文字列の回文っぽさを判定するプログラムをここで書いてあげれば取材の助けになるかもしれないと思った．ここで，文字列の回文っぽさとは，次のように定められる数である．

  • 文字列後半（奇数長のときには中央の文字を含まない）から範囲の重複しない区間を 0 個以上の任意の個数選び，それぞれの区間の部分文字列を反転することで，全体の文字列を回文にすることを考える．回文になる区間の選び方全体が空でないとき，これらのうちそれぞれの区間の長さの二乗の総和の最小値を文字列の回文っぽさとする．回文になる区間の選び方が存在しないとき，回文っぽさは -1 とする．長さ n の文字列 S = S1 S2 ... Sn が回文であるとは，任意の i = 1, ..., n に対して Si = Sn+1-i が成り立つことのみをいう．

입력

入力は 50 個以下のデータセットからなる． 各データセットは次の形式で表される．

S

S は小文字アルファベットからなる文字列であり，1 ≤ |S| ≤ 20000 を満たす．

入力の終わりは # の 1 文字のみからなる行で表される．

출력

各データセットに対し，文字列 S の回文っぽさを 1 行に出力せよ．

예제1

  1. 예제 1

    입력
    burisyabusyaburibu
abcdefefbcda
satorarepotenetoperarotas
abcacb
#
    예상 출력
    33
13
0
-1