Liceul Teoretic de Informatică „Grigore Moisil” Iaşi

CONCURS NAŢIONAL DE INFORMATICĂ Clasa a IX-a

Problema 2 - şir Autor: comisia Descrierea soluţiei (Vlad Andrei Tudose)

1. Soluţia care obţine 30 de puncte se bazează pe generarea succesivă a configuraţiilor de semne +/- până la determinarea unei configuraţii corecte. Complexitatea este O(2N*N).

2. Soluţia de 100 de puncte se bazează pe o rezolvare inductivă astfel: - presupunem că am determinat deja o secvenţă de semne pentru şirul ai+1,ai+2,...,aN astfel încât

valoarea Si+1 a expresiei obţinute să aibă proprietatea 0 ≤ Si+1 ≤ ai+1 - putem determina o secvenţă de semne pentru şirul ai,ai+1,...,aN astfel încât valoarea Si a expresiei

obţinute să aibă proprietatea 0 ≤ Si ≤ ai. Avem două cazuri: o Si+1≥ ai. În acest caz, scriem semnul – în faţa lui ai şi păstrăm semnele determinate la pasul

anterior pentru ai+1,ai+2,...,aN. Observăm că valoarea Si=-ai+Si+1 are proprietatea dorită (avem relaţia Si+1 ≤ ai+1≤ 2*ai din care, dacă scădem ai, se obţine Si+1 - ai ≤ ai deci Si≤ ai)

o Si+1< ai. În acest caz, scriem semnul + în faţa lui ai şi inversăm semnele determinate la pasul anterior pentru ai+1,ai+2,...,aN. Observăm că valoarea Si=ai-Si+1 are proprietatea dorită (avem relaţia Si+1< ai pe care, dacă o înmulţim cu -1 şi adunăm apoi ai, se obţine ai- Si+1> 0 deci Si> 0 ). Schimbarea semnelor trebuie implementată în timp constant. O variantă de implementare este construirea, odată cu soluţia, a unui vector swap de dimensiune N, cu semnificaţia swap[i]=1, dacă semnele valorilor ai+1,ai+2,...,aN trebuie schimbate şi 0 altfel.

Complexitatea este O(N).