Problem:


Encryption System

A programmer developed a new encryption system.
However, his system has an issue that
two or more distinct strings are `encrypted' to the same string.

We have a string encrypted by his system. 
To decode the original string, we want to enumerate all the candidates of the string before the encryption.
Your mission is to write a program for this task.

The encryption is performed taking the following steps. Given a string that consists only of lowercase letters ('a' to 'z').

Change the first 'b' to 'a'. If there is no 'b', do nothing.

Change the first 'c' to 'b'. If there is no 'c', do nothing.

...

Change the first 'z' to 'y'. If there is no 'z', do nothing.

Input

The input consists of at most 100 datasets.
Each dataset is a line containing an encrypted string.
The encrypted string consists only of lowercase letters, and contains at least 1 and at most 20 characters.

The input ends with a line with a single '#' symbol.

Output

For each dataset,
the number of candidates n of the string before encryption should be printed in a line first,
followed by lines each containing a candidate of the string before encryption.
If n does not exceed 10, print all candidates in dictionary order;
otherwise, print the first five and the last five candidates in dictionary order.

Here, dictionary order is recursively defined as follows.
The empty string comes the first in dictionary order.
For two nonempty strings x = x1 ... xk and y = y1 ... yl, 
the string x precedes the string y in dictionary order if 

x1 precedes y1 in alphabetical order ('a' to 'z'), or

x1 and y1 are the same character and x2 ... xk precedes y2 ... yl in dictionary order.

Sample Input

enw
abc
abcdefghijklmnopqrst
z
#

Output for the Sample Input

1
fox
5
acc
acd
bbd
bcc
bcd
17711
acceeggiikkmmooqqssu
acceeggiikkmmooqqstt
acceeggiikkmmooqqstu
acceeggiikkmmooqrrtt
acceeggiikkmmooqrrtu
bcdefghijklmnopqrrtt
bcdefghijklmnopqrrtu
bcdefghijklmnopqrssu
bcdefghijklmnopqrstt
bcdefghijklmnopqrstu
0



Sample input:
enw
abc
abcdefghijklmnopqrst
z
#


Sample output:
1
fox
5
acc
acd
bbd
bcc
bcd
17711
acceeggiikkmmooqqssu
acceeggiikkmmooqqstt
acceeggiikkmmooqqstu
acceeggiikkmmooqrrtt
acceeggiikkmmooqrrtu
bcdefghijklmnopqrrtt
bcdefghijklmnopqrrtu
bcdefghijklmnopqrssu
bcdefghijklmnopqrstt
bcdefghijklmnopqrstu
0

Submission status: Wrong Answer

Solution code:
ans=[""]
ans.pop()
s=""
w=["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z","}"]
x=[0]
x.pop()
def uni(seq):
    seen = set()
    seen_add = seen.add
    return [ x for x in seq if x not in seen and not seen_add(x)]

def check(a):
	global s
	global w
	n=len(a)
	# print "before ",a
	for i in range(26):
		if i==0:
			continue
		a=a.replace(w[i],w[i-1],1);
	# print "after ",a
	if a==s[0:n]:
		return True
	else:
		return False

def foo(a,n):
	# print a
	global ans
	global x
	if n==len(a):
		if check(a):
			ans.append(a)
		return
	sz=len(a)
	t=a+s[sz]
	if check(t):
		foo(t,n)
	t=a+w[x[sz]+1]
	# print t
	if check(t):
		# print t
		foo(t,n)



while True:
	s = raw_input()
	if s=="#":
		break
	ans=[""]
	ans.pop()
	x=[0]
	x.pop()
	for i in range(len(s)):
		for j in range(26):
			if w[j]==s[i]:
				x.append(j)
	# print s
	foo("",len(s))
	ans=uni(ans)
	if len(ans)<=10:
		print len(ans)
		for i in range(len(ans)):
			print ans[i]
	else:
		print len(ans)
		for i in range(5):
			print ans[i]
		for i in range(5):
			print ans[len(ans)-1-i]

Submission status: Wrong Answer

Solution code:
def dfs(s,n):
        
    if n == s_l:
        ans.append(s)
        return 
    next_s = s[:n] + chr(ord(s[n]) + 1) + s[n+1:]

    if s.find(s[n]) != n or s[n] == 'a':
        dfs(s,n+1)
        dfs(next_s,n+1)
    else:
        if s[n] != 'z':
            dfs(next_s,n+1)

        


    
        
ans = []     
s_l = 0
while True:
    s = input()
    if s == "#":
        break
    s_l = len(s)


    dfs(s,0)
    
    ans.sort()

    print(len(ans))

    if len(ans) <= 10:
        for s in ans:
            print(s)
    else:
        for s in ans[:5]:
            print(s)
        
        for s in ans[len(ans) -5:]:
            print(s)
                
    ans = []

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

def dfs(n,tmp):
    global koho
    if n == -1:
        koho.append(tmp)
        return

    if inpS[n] == 'z':
        dfs(n-1,'z' + tmp)
    else:
        next = chr(ord(inpS[n])+1)
        dfs(n-1,next + tmp)
        dfs(n-1,inpS[n] + tmp)

while True:
    inpS = input()
    if inpS == '#':
        break
    else:
        koho = []
        dfs(len(inpS)-1,'')
        ans = []
        for S in koho:
            tmpl = list(S)
            for i in range(25):
                for j,s in enumerate(tmpl):
                    if ord(s) == i+98:
                        tmpl[j] = chr(i+97)
                        break
            tmpS = ''.join(tmpl)
            if inpS == tmpS:
                ans.append(S)

        ans.sort()
        L = len(ans)
        print(L)
        if L <= 10:
            for a in ans:
                print(a)
        else:
            for i in range(5):
                print(ans[i])
            for i in range(L-5,5):
                print(ans[i])

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    def f(s):
        d = collections.defaultdict(int)
        ac = {}
        ca = {}
        for i in range(26):
            t = int(2**i)
            c = chr(ord('a') + i)
            ac[t] = c
            ca[c] = t
        a = [ca[c] for c in s]
        z = ca['z']
        d[0] = 1
        for c in a:
            nd = collections.defaultdict(int)
            c2 = c * 2
            for k,v in d.items():
                if k & c or c == 1:
                    nd[k] += v
                if c != z and k & c2 == 0:
                    nd[k|c2] += v
            d = nd
        r = [sum(d.values())]

        ss = set([''])
        for t in s:
            ns = set()
            t2 = chr(ord(t) + 1)
            for si in ss:
                if t in si or t == 'a':
                    ns.add(si + t)
                if t != 'z' and t2 not in si:
                    ns.add(si + t2)
            ss = set(sorted(ns)[:5])
        rs = ss

        ss = set([''])
        for t in s:
            ns = set()
            t2 = chr(ord(t) + 1)
            for si in ss:
                if t in si or t == 'a':
                    ns.add(si + t)
                if t != 'z' and t2 not in si:
                    ns.add(si + t2)
            ss = set(sorted(ns, reverse=True)[:5])
        rs |= ss
        r.extend(sorted(rs))

        return r

    while True:
        s = S()
        if s == '#':
            break
        rr.extend(f(s))

    return '\n'.join(map(str, rr))



print(main())

Submission status: Accepted

Solution code:
ans = []
def search(s,c):
    if c == "a":
        ans.append(s)
        return

    for i in xrange(len(s)):
        if s[i] == c: return
    
        if s[i] == chr(ord(c)-1):
            t = list(s[:])
            t[i] = c
            t = "".join(t)
            
            search(t, chr(ord(c)-1))
    search(s, chr(ord(c)-1))
            
while 1:
    S = raw_input()
    if S == "#": break

    ans = []
    search(S,"z")
    
    ans = sorted(list(set(ans)))
    print len(ans)
    if len(ans) <= 10:
        for a in ans:
            print a
    else:
        for i in xrange(5):
            print ans[i]
        for i in xrange(5):
            print ans[len(ans)-5+i]

Submission status: Accepted

Solution code:
ans=[""]
ans.pop()
s=""
w=["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z","}"]
x=[0]
x.pop()
def uni(seq):
    seen = set()
    seen_add = seen.add
    return [ x for x in seq if x not in seen and not seen_add(x)]

def check(a):
	global s
	global w
	n=len(a)
	# print "before ",a
	for i in range(26):
		if i==0:
			continue
		a=a.replace(w[i],w[i-1],1);
	# print "after ",a
	if a==s[0:n]:
		return True
	else:
		return False

def foo(a,n):
	# print a
	global ans
	global x
	if n==len(a):
		if check(a):
			ans.append(a)
		return
	sz=len(a)
	t=a+s[sz]
	if check(t):
		foo(t,n)
	if w[x[sz]]=="z":
		return
	t=a+w[x[sz]+1]
	# print t
	if check(t):
		# print t
		foo(t,n)



while True:
	s = raw_input()
	if s=="#":
		break
	ans=[""]
	ans.pop()
	x=[0]
	x.pop()
	for i in range(len(s)):
		for j in range(26):
			if w[j]==s[i]:
				x.append(j)
	# print s
	foo("",len(s))
	# ans=uni(ans)
	ans.sort()
	if len(ans)<=10:
		print len(ans)
		for i in range(len(ans)):
			print ans[i]
	else:
		print len(ans)
		for i in range(5):
			print ans[i]
		for i in range(5):
			print ans[len(ans)-5+i]

Submission status: Accepted

Solution code:
from itertools import chain

alph = "abcdefghijklmnopqrstuvwxyz"
# s = input()

def solve1(s):
    cands = [s]
    for c in reversed(alph[:-1]):
        cands = chain.from_iterable(
            [candidates(s, c) for s in cands]
        )

    cands = list(cands)
    cands.sort()
    print(len(cands))
    if len(cands) > 10:
        for s in cands[:5]:
            print(s)
        for s in cands[-5:]:
            print(s)
    else:
        for s in cands:
            print(s)
            
            
def next_char(c):
    return chr(ord(c)+1)

def candidates(string, key):
    nex = next_char(key)
    flag = False
    for i, c  in enumerate(string):
        if c == nex:
            flag = True
            break

        if c != key:
            continue

        yield string[:i] + nex + string[i+1:]

    if not flag:
        yield string
            



while True:
    s = input()
    if s == "#":
        break
    solve1(s)

Submission status: Accepted

Solution code:

import sys
def input():
    return sys.stdin.readline()[:-1]
while True:
    S = input()
    if S=="#":
        break
    N = len(S)
    Sn = [ord(c)-97 for c in S]
    ans = []
    ansappend = ans.append
    zip_ = list(zip(range(N-1, -1, -1), Sn))
    i = 0
    #for i in range(1<<N):
    end = 1<<N
    Tst = [0] + [1]*25 + [0]
    while i < end:
        #tst = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0]
        tst = Tst.copy()
        ans_ = []
        for j, n in zip_:
            if i>>j & 1:
                n += 1
                if tst[n]:
                    tst[n]=0
                    ans_.append(n)
                else:
                    i += 1<<j
                    break
            else:
                if tst[n]==0:
                    ans_.append(n)
                else:
                    i += 1<<j
                    break
        else:
            ansappend(ans_)
            i+=1
    #ans.sort()
    print(len(ans))
    if len(ans)<=10:
        for ans_ in ans:
            print(*map(lambda x: chr(x+97), ans_), sep="")
    else:
        for ans_ in ans[:5]:
            print(*map(lambda x: chr(x+97), ans_), sep="")
        for ans_ in ans[-5:]:
            print(*map(lambda x: chr(x+97), ans_), sep="")

Submission status: Runtime Error

Solution code:
ans=[""]
ans.pop()
s=""
w=["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
x=[0]
x.pop()
def uni(seq):
    seen = set()
    seen_add = seen.add
    return [ x for x in seq if x not in seen and not seen_add(x)]

def check(a):
	global s
	global w
	n=len(a)
	# print "before ",a
	for i in range(26):
		if i==0:
			continue
		a=a.replace(w[i],w[i-1],1);
	# print "after ",a
	if a==s[0:n]:
		return True
	else:
		return False

def foo(a,n):
	# print a
	global ans
	global x
	if n==len(a):
		if check(a):
			ans.append(a)
		return
	sz=len(a)
	t=a+s[sz]
	if check(t):
		foo(t,n)
	t=a+w[x[sz]+1]
	# print t
	if check(t):
		# print t
		foo(t,n)



while True:
	s = raw_input()
	if s=="#":
		break
	ans=[""]
	ans.pop()
	x=[0]
	x.pop()
	for i in range(len(s)):
		for j in range(26):
			if w[j]==s[i]:
				x.append(j)
	# print s
	foo("",len(s))
	ans=uni(ans)
	if len(ans)<=10:
		print len(ans)
		for i in range(len(ans)):
			print ans[i]
	else:
		print len(ans)
		for i in range(5):
			print ans[i]
		for i in range(5):
			print ans[len(ans)-1-i]

Submission status: Runtime Error

Solution code:
import itertools
while 1:
    s = raw_input()
    if s == '#':
        break
    code = [ord(c)-97 for c in s]
    result = set()
    l = len(s)
    for p in itertools.product([0,1], repeat=l):
        used = set([0, 26])
        ok = 1
        for i in xrange(l):
            k = code[i] + p[i]
            if p[i] == (k in used):
                ok = 0
                break
            used.add(k)
        if ok:
            result.add("".join(chr(97 + code[i] + p[i]) for i in xrange(l)))
    print len(result)
    s_result = sorted(result)
    if len(result) <= 10:
        for el in sorted(result):
            print el
    else:
        for el in s_result[:5] + s_result[-5:]:
            print el

Submission status: Runtime Error

Solution code:
import itertools
from heapq import *
while 1:
    s = raw_input()
    if s == '#':
        break
    code = [ord(c)-97 for c in s]
    l = len(s)
    f_que = []; l_que = []
    ans = 0
    for p in itertools.product([0,1], repeat=l):
        used = set([0, 26])
        ok = 1
        for i in xrange(l):
            k = code[i] + p[i]
            if p[i] == (k in used):
                ok = 0
                break
            used.add(k)
        if ok:
            ans += 1
            ss = tuple(-(97 + code[i] + p[i]) for i in xrange(l))
            if len(f_que) < 10:
                heappush(f_que, ss)
            else:
                heappushpop(f_que, ss)
            ss = tuple(97 + code[i] + p[i] for i in xrange(l))
            if len(l_que) < 5:
                heappush(l_que, ss)
            else:
                heappushpop(l_que, ss)
    print ans
    if ans <= 10:
        res = ["".join(map(lambda x: chr(-x), heappop(f_que))) for i in xrange(ans)]
        if ans:
            print "\n".join(reversed(res))
    else:
        for i in xrange(5):
            heappop(f_que)
        res = ["".join(map(lambda x: chr(-x), heappop(f_que))) for i in xrange(5)]
        print "\n".join(reversed(res))
        res = ["".join(map(chr, heappop(l_que))) for i in xrange(5)]
        print "\n".join(res)