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

<syntaxhighlight lang="python"> 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)

</syntaxhighlight>