Editing 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
<br>

== 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 ==
<syntaxhighlight lang="python" line>
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()

</syntaxhighlight>