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

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"

# 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()))

# Validare date
if not validare_date(N, M, cifre):
    print("Datele de intrare nu sunt valide.")
    exit()

# Găsire expresie sau 0 în cazul în care nu există soluție
rezultat = gaseste_expresie(N, cifre)

# Scriere rezultat în fișierul de ieșire
with open("adunscadout.txt", "w") as file:
    file.write(str(rezultat))