AtCoder Beginner Contest 007

B - 辞書式順序


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題文

文字列 A が与えられる。小文字アルファベット(a-z)のみを使って辞書順比較したとき文字列 A より小さいものを1つ何でも良いので出力せよ。ただし、文字列は 1 文字以上 100 文字以下でなければならない。もし存在しない場合は "-1" を出力せよ。

ただし、ある文字列 S=S_1S_2...S_nT=T_1T_2...T_m について、辞書順比較した際に S<T であるとは、次のどちらか一方の状態が成り立っていることを言う。

  • ある整数 i (1≦i≦{\rm min}(n,m)) に関して、 1≦j≦i−1 を満たすどの整数 j に関しても S_j=T_j が成立し、かつ S_i<T_i が成立する
  • 任意の整数 i (1≦i≦{\rm min}(n,m)) に関して、 常に S_i=T_i が成立し、かつ |S|<|T| である。ただし |X| は文字列 X の長さを表すものとする。

なにやら頭が痛くなる記述だが、言い換えると次の通りである。

  • それぞれの文字列の同じ位置同士を先頭から比較していって、初めて不一致になったら、その文字同士の(アルファベットでの)比較結果が文字列の全体の比較結果である。 例えば、"abcd""ax" を比較すると、2 文字目で、'b'<'x' となるので、"abcd"<"ax" である。
  • もし、比較している途中で片方の文字列が尽きてしまったら、文字列の長さが短い方が小さい。例えば "ab" < "abc"である。

入力

入力は以下の形式で標準入力から与えられる。

A
  • 1 行目には、文字列 A (1 ≦ |A| ≦ 10) が与えられる。|A|は文字列 |A| の長さを表す。Aは小文字アルファベット(a-z)のみから成る。

出力

文字列 A より小さい文字列を 11 行に出力せよ。ただし、小文字アルファベット(a-z)のみを用いており、長さは1以上100以下でなければならない。解が複数ある場合はどれを出力しても良い。存在しない場合は、代わりに "-1" を出力すること。出力の末尾に改行をいれること。


入力例1

xyz

出力例1

xy

もちろん、"xy" の他に、"abcd" 等を出力しても正答として扱われる。


入力例2

c

出力例2

b

"a" もしくは "b" が正答として扱われる。


入力例3

a

出力例3

-1

"a" より小さい文字列は存在しない。出力する文字列は長さ1以上でなければならないため、""(空文字列)は不適切であることに注意せよ。


入力例4

aaaaa

出力例4

aaaa

Submit提出する