1078 - Adun Scad

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 adunscad.in 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 adunscad.out 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

adunscad.in

21 4

3 9 1 8

adunscad.out

3+9+1+8

Exemplu 2

adunscad.in

-1 4

1 2 3 5

adunscad.out

-1+2+3-5

Exemplu 3

adunscad.in

-7 7

1 1 1 1 1 1 1

adunscad.out

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

Exemplu 4

adunscad.in

12 3

1 2 3

adunscad.out

0

Rezolvare

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("adunscad.in", "r") as file:

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

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

# 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("adunscad.out", "w") as file:

    file.write(str(rezultat))