Editing 3919 - Back ME

= Cerința =
Se citesc două numere naturale <code>n</code> și <code>m</code>. Afișați în ordine lexicografică toate cuvintele care sunt formate din <code>n</code> litere <code>E</code> și <code>m</code> litere <code>M</code> cu proprietatea că nu există mai mult de două litere <code>M</code> alăturate și nici mai mult de două litere <code>E</code> alăturate.

= Date de intrare =
Programul citește de la tastatură numerele <code>n</code> și <code>m</code>, separate prin spații.

= Date de ieșire =
Programul va afișa pe ecran pe linii separate cuvintele cerute.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>0 ≤ n ≤ 17</code>, <code>0 ≤ m ≤ 17</code>
* <code>0 ≤ n + m ≤ 28</code>
* Dacă nu există cuvinte care să respecte condițiile, atunci se va afișa <code>IMPOSIBIL</code>.

= Exemplul 1: =
Intrare
 3  3
Ieșire
 EEMEMM
 EEMMEM
 EMEEMM
 EMEMEM
 EMEMME
 EMMEEM
 EMMEME
 MEEMEM
 MEEMME
 MEMEEM
 MEMEME
 MEMMEE
 MMEEME
 MMEMEE

= Exemplul 2: =
Intrare
 18 29
Ieșire
 Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def afisare(v, st, e, m):
    for i in range(1, e + m + 1):
        print(v[st[i]], end='')
    print()

def valid(v, st, k, e, m):
    for i in range(1, k - 1):
        if v[st[i]] == 'E' and v[st[i + 1]] == 'E' and v[st[i + 2]] == 'E':
            return False
        if v[st[i]] == 'M' and v[st[i + 1]] == 'M' and v[st[i + 2]] == 'M':
            return False
    if k == e + m:
        E, M = 0, 0
        for i in range(1, k + 1):
            if v[st[i]] == 'E':
                E += 1
            else:
                M += 1
        if E != e or M != m:
            return False
    return True

def bck(v, st, k, e, m, g):
    for i in range(2):
        st[k] = i
        if valid(v, st, k, e, m):
            if k == e + m:
                g[0] = 1
                afisare(v, st, e, m)
            else:
                bck(v, st, k + 1, e, m, g)

def check_restrictions(n, m):
    if 0 <= n <= 17 and 0 <= m <= 17 and 0 <= n + m <= 28:
        return True
    else:
        print("Datele nu corespund restrictiilor impuse")
        return False

def main():
    e, m = map(int, input().split())
    
    if not check_restrictions(e, m):
        return
    
    v = [''] * 109
    st = [0] * 109
    g = [0]
    v[0], v[1] = 'E', 'M'
    bck(v, st, 1, e, m, g)
    if g[0] == 0:
        print("IMPOSIBIL")

if __name__ == "__main__":
    main()
</syntaxhighlight>