0152 - Sir

Enunț

GM are un şir de N numere naturale a1 , a2 ,…, aN , cu proprietatea ai ≤ ai+1 ≤ 2*ai pentru orice i, 1 ≤i < N. El doreşte să scrie în faţa fiecărei valori din şir un semn + sau - astfel încât valoarea S a expresiei obţinute să aibă proprietatea 0 ≤ S ≤ a1 .

Cerinţa

Scrieţi un program care să-l ajute pe GM să determine un mod de a scrie cele N semne.

Date de intrare

Pe prima linie a fişierului de intrare sir.in se află numărul natural N reprezentând numărul de valori din şir. Pe următoarea linie se află numerele a1 , a2 ,…, aN , separate prin câte un spaţiu.

Date de ieşire

Fişierul de ieşire sir.out va avea o singură linie ce va conţine un şir de N caractere + sau -. Al i-lea caracter va reprezenta semnul ce va fi scris în faţa valorii ai .

Restricţii şi precizări

• 1 ≤ N ≤ 100.000
• 1 ≤ ai ≤ 109
• Dacă există mai multe soluţii se va afişa oricare dintre ele
• Pentru un număr de teste în valoare de 30 de puncte, N ≤ 18

Exemplu

sirin.txt

3

2 3 5

sirout.txt

--+

Explicaţii

Se obţine expresia S=-2-3+5=0, care respectă proprietatea cerută (0 ≤ S ≤ 2).

Rezolvare

def validate_input(N, values):
    if not (1 <= N <= 100000 and (N <= 18 or 1 <= all(1 <= val <= 10**9 for val in values))):
        print("Eroare: Date de intrare nevalide.")
        return False
    return True

def solve_signs(N, values):
    signs = [''] * N
    signs[-1] = '+'

    for i in range(N - 2, -1, -1):
        if values[i] * 2 >= values[i + 1]:
            signs[i] = '-'
        else:
            signs[i] = '+'

    return ''.join(signs)

with open('sirin.txt', 'r') as file:
    N = int(file.readline().strip())
    values = list(map(int, file.readline().split()))


if not validate_input(N, values):
    exit()

result = solve_signs(N, values)

with open('sirout.txt', 'w') as file:
    file.write(result + '\n')

if __name__ == "__main__":
    solve_signs(N, values)