0147 - expresie1

La ora de matematică Georgică a învăţat să evalueze expresii aritmetice. Pentru a verifica acest lucru profesorul de informatică îi propune lui Georgică să evalueze expresii aritmetice de forma:

A o1 B o2 C

Unde A, B, C sunt operanzi, iar o1 şi o2 sunt operatori.

Valorile permise operanzilor pot fi numai termeni din şirul x1, x2, …, xn, iar operatorii pot fi numai caracterele + (adunare) şi * (înmulţire).

Profesorul îi pune la dispoziție lui Georgică o valoare numerică V şi îi cere să determine valorile operanzilor A, B şi C pentru care expresia are valoarea V.

Cerinţă

Scrieţi un program, care pentru V, n, x1, x2, …, xn şi o1, o2 date, determină indicii corespunzători termenilor din şirul x1, x2, …, xn ce corespund valorilor operanzilor A, B şi C pentru ca expresia dată să aibă valoarea V.

Date de intrare

Fişierul de intrare input.txt conţine pe prima linie numerele naturale V, n, x1, x2, …, xn separate între ele printr-un spaţiu şi pe linia a doua exact două caractere asociate operatorilor o1 şi o2.

Date de ieşire

Fişierul de ieşire output.txt va conţine, pe prima linie separate între ele exact trei indici ai şirului x1, x2, …, xn corespunzători termenilor folosiţi pentru A, B, C. Dacă nu există soluţie se va scrie în fişier cifra 0 de trei ori separată prin câte un spaţiu: 0 0 0.

Restricţii şi precizări

• 0 < n < 10001

Exemplul 1

input.txt:

100 5 40 13 2 11 20

+*

output.txt:

5 3 1

Explicație:

A = x5, B = x3, C = x1

Expresia devine 20 + 2 * 40 = 100

Exemplul 2

input.txt:

100 9999999999999 40 13 2 11 20

+*

Output:

Input-ul nu convine conditiilor

Rezolvare

def verificare(n):
    if not(1<=n<=10000):
        print("Input-ul nu convine conditiilor")
        exit()

def cit():
    global V, n, f, o1, o2
    with open("input.txt", "r") as fin:
        l=list(map(int, fin.readline().split()))
        V = l[0]
        n = l[1]
        verificare(n)
        f = [0] * 1005
        for i in range(1, n + 1):
            k = l[i+1]
            f[k] = i
        l=fin.readline()
        o1 = l[0]
        o2 = l[1]

def evalexp(A, B):
    global V, o1, o2
    if o1 == '+':
        if o2 == '+':
            t = V - (A + B)
        else:
            t = (V - A) / B
    else:
        if o2 == '+':
            t = V - A * B
        else:
            t = V / (A * B)
    if t > 0 and t == int(t):
        return int(t)
    return -1

def rezolva():
    global f
    for iA in range(1001):
        if f[iA] > 0:
            for iB in range(1001):
                if f[iB] > 0:
                    iC = evalexp(iA, iB)
                    if 0 <= iC < 1001 and f[iC] > 0:
                        with open("output.txt", "w") as fout:
                            fout.write(f"{f[iA]} {f[iB]} {f[iC]}")
                        return 1
    return 0

def main():
    cit()
    if rezolva() == 0:
        with open("output.txt", "w") as fout:
            fout.write("0 0 0")

if __name__ == "__main__":
    main()