1078 - Adun Scad

Enunț

Considerăm un număr întreg N şi un şir de M cifre zecimale nenule. Să se determine dacă numărul N poate fi rezultatul unei expresii aritmetice simple (fără paranteze), formată exclusiv din cifrele şirului citit şi din operatorii aritmetici desemnaţi pentru operaţiile de adunare şi scădere (+, -).

Cerinţă

Scrieţi un program care citeşte numerele N şi M de pe prima linie a fişierului de intrare şi şirul de M cifre de pe linia următoare şi determină şi afişează expresia găsită sau valoarea 0 în cazul în care nu există soluţie.

Date de intrare

Fișierul de intrare adunscadin.txt conține pe prima linie numerele întregi N M, separate printr-un spaţiu, reprezentând valoarea ce trebuie obţinută la evaluarea expresiei şi numărul de cifre din şir. Linia a doua a fişierului de intrare conţine şirul celor M cifre nenule, separate prin câte un spaţiu.

Date de ieșire

Fișierul de ieșire adunscadout.txt va conține pe prima linie expresia determinată, în cazul în care există soluţie, sau valoarea 0 în cazul în care nu există soluţie.

Restricții și precizări

• -180 ≤ N ≤ 180
• 2 ≤ M ≤ 20
• în şirul citit cifrele se pot repeta
• toate cifrele din şir trebuie să apară şi în expresia aritmetică, în aceeaşi ordine în care au fost citite
• în expresia aritmetică, orice cifră trebuie să fie precedată de un operator; în cazul în care prima cifră este precedată de operatorul '+' acesta nu se pune în expresie
• în expresia aritmetică nu există spaţii
• expresia aritmetică se termină cu caracterul sfârşit de linie
• în cazul în care soluţia nu este unică se va afişa o soluţie corectă

Exemplu 1

adunscadin.txt

21 4

3 9 1 8

adunscadout.txt

3+9+1+8

Exemplu 2

adunscadin.txt

-1 4

1 2 3 5

adunscadout.txt

-1+2+3-5

Exemplu 3

adunscadin.txt

-7 7

1 1 1 1 1 1 1

adunscadout.txt

-1-1-1-1-1-1-1

Exemplu 4

adunscadin.txt

12 3

1 2 3

adunscadout.txt

0

Rezolvare

<syntaxhighlight lang="python"> def validare_date(N, M, cifre):

   if not (-180 <= N <= 180):
       return False
   if not (2 <= M <= 20):
       return False
   if len(cifre) != M:
       return False
   return True

def gaseste_expresie(N, cifre):

   M = len(cifre)

   for i in range(1 << (M - 1)):
       expresie = str(cifre[0])
       valoare = int(cifre[0])

       for j in range(M - 1):
           if (i >> j) & 1:
               expresie += '+' + str(cifre[j + 1])
               valoare += int(cifre[j + 1])
           else:
               expresie += '-' + str(cifre[j + 1])
               valoare -= int(cifre[j + 1])

       if valoare == N:
           return expresie

   return "0"

1. Citire date de intrare

with open("adunscadin.txt", "r") as file:

   N, M = map(int, file.readline().split())
   cifre = list(map(int, file.readline().split()))

1. Validare date

if not validare_date(N, M, cifre):

   print("Datele de intrare nu sunt valide.")
   exit()

1. Găsire expresie sau 0 în cazul în care nu există soluție

rezultat = gaseste_expresie(N, cifre)

1. Scriere rezultat în fișierul de ieșire

with open("adunscadout.txt", "w") as file:

   file.write(str(rezultat))

</syntaxhighlight>