Codeforces #293 Div.2 A: Vitaly and Strings

B問題より正答者が少ないA問題。No such stringsと出力して一回WAを食らってしまった。

問題はこちら。

問題

同じ文字数の英小文字からなる文字列sとtが与えられる。sは辞書順でtより小さい。辞書順でsより大きく、tより小さい文字列を１つ答えよ。そういった文字列がないときは"No such string"と答えよ。

解説

いくつか場合分けをして考える。

i番目の文字で s[i] < c < t[i] となる文字cがある場合は (sのi-1文字目まで)+c+(必要な数の任意の文字) が答えとなる。

s[i] < t[i] でs[i]より大きく、t[i]より小さい文字がない場合はつぎの２つを考える。

1. s[j] < "z" (j > i)となる文字 s[j]があるかどうか。
2. t[j] > "a" (j > i)となる文字 t[j]があるかどうか。

1を満たす文字がある場合は (sのi文字目まで)+(必要な数のz)、2を満たす場合は (tのi文字めまで)+(必要な数のa)で条件を満たす文字列となる。 答えとなる文字列がなければ "No such string" を答える。

s = raw_input()
t = raw_input()
n = len(s)
for i in xrange(n):
    d = ord(t[i])-ord(s[i])
    if d > 1:
        print s[:i]+chr(ord(s[i])+1)+s[i+1:]        
        exit()
    if d == 1 and i < n-1:
        for j in xrange(i+1,n):
            if s[j] < "z":
                print s[:i+1]+"z"*(n-i-1)
                exit()
            if t[j] > "a":
                print t[:i+1]+"a"*(n-i-1)
                exit()
print "No such string"