1811 - Aritma

Cerinţa

Shaka, regele zuluşilor, a dat ordin să se realizeze un sistem de comunicaţii bazat pe tobe (tamtam)care să acopere întreaga ţară. Pentru aceasta el a dispus instruirea celor ce vor urma să transmită mesajele. Problema intervenită este aceea că o parte din cursanţi nu pot face distincţie între sunete şi nu pot reda cu fidelitate succesiunea de sunete pe hârtie. S-a făcut următoarea convenţie de notare: un sunet lung va fi reprezentat prin +, unul scurt prin -, iar unul nedecis (receptorul nu e sigur de lungimea sunetului) prin *.

Spre finalul stagiului Shaka a mers să verifice nivelul de pregătire al cursanţilor. Pentru aceasta el a adunat n cursanţi pe care i-a pus să recepţioneze şi să noteze un mesaj format din m sunete. După transmiterea mesajului s-a constatat că mulţi dintre cursanţi au scris şiruri foarte diferite, ceea ce ducea la o alterare semnificativă a mesajului original, chiar dacă nici cel mai slab pregătit cursant nu a fost indecis la mai mult de jumătate din sunete. Supărat Shaka l-a chemat pe instructorul şef şi, ca să-l pedepsească, i-a cerut ca să determine câte mesaje distincte se pot forma din şirurile scrise de cursanţi.

Scrieţi un program care determină numărul de mesaje distincte rezultate.

Date de intrare

Fişierul aritma.in conţine pe prima sa linie numerele n şi m separate prin spaţiu, iar pe următoarele n linii şiruri de caractere de lungime m formate numai din simbolurile +, - sau *.

Date de ieșire

Pe prima linie a fişierului aritma.out se va scrie numărul de mesaje distincte.

Restricţii şi precizări

• 1 < n < 25
• 1 < m < 19

Exemplu

aritma.in

3 3
+-*
+*+
-*+

aritma.out

5

Explicație

Mesajele rezultate sunt: +--, +-+, +++, +-+, --+, -++. Primele două mesaje sunt rezultate din prima identificare, următoarele două sunt din a doua identificare şi ultimele două din ultimul şir; numai cinci sunt distincte.

Rezolvare

def distinct_messages(strings):
    def backtrack(index):
        if index == len(strings[0]):
            messages.add("".join(message))
            return

        # Dacă sunetul este cunoscut, îl adăugăm în mesaj
        if all(s[index] != '*' for s in strings):
            message.append(strings[0][index])
            backtrack(index + 1)
            message.pop()

        # Dacă sunetul este incert, încercăm toate posibilitățile
        elif any(s[index] == '*' for s in strings):
            for sound in ['+', '-', '*']:
                message.append(sound)
                backtrack(index + 1)
                message.pop()

    messages = set()
    message = []
    backtrack(0)
    return len(messages)

def main():
    # Citim datele de intrare
    with open("aritma.in", "r") as fin:
        n, m = map(int, fin.readline().split())
        strings = [fin.readline().strip() for _ in range(n)]

    # Determinăm numărul de mesaje distincte
    result = distinct_messages(strings)

    # Scriem rezultatul în fișierul de ieșire
    with open("aritma.out", "w") as fout:
        fout.write(str(result) + "\n")

if __name__ == "__main__":
    main()