№ 3074 (Уровень: Гроб)
(PRO100 ЕГЭ) Иван составляет слова из букв Г, О, Л.

1) Две одинаковые буквы не могут стоять рядом.

2) Буква Г может стоять только между буквами О и Л или Л и О. То есть, в начале слова и на конце буква Г стоять не может. ОГЛ, ЛГО - разрешены. ОГО, ЛГЛ - запрещены.



Сколько 20-буквенных слов может составить Иван?


def f(code, old):
    if len(code)==20:
        if code[-1]!='Г':
            print(code)
            return 1
        else:
            return 0
    d = []
    if code[-1]=='Л':
        d.append(f(code+'Г','Г'))
        d.append(f(code+'О','О'))
    if code[-1]=='О':
        d.append(f(code+'Г','Г'))
        d.append(f(code+'Л','Л'))
    if code[-1]=='Г':
        if code[-2]=='О': d.append(f(code+'Л','Л'))
        if code[-2]=='Л': d.append(f(code+'О','О'))
    return sum(d)
print(f('О','О')+f('Л','О'))