AjM: Pagină nouă: == 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 +,...

2024-06-03T17:03:34Z

Pagină nouă: == 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 +,...

New page

== 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>

1811 - Aritma - Revision history