Sir Descriere
1
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(2 N *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 a i+1 ,a i+2 ,...,a N astfel încât valoarea S i+1 a expresiei obţinute să aibă proprietatea 0 ≤ S i+1 ≤ a i+1 - putem determina o secvenţă de semne pentru şirul a i ,a i+1 ,...,a N astfel încât valoarea S i a expresiei obţinute să aibă proprietatea 0 ≤ S i ≤ a i . Avem două cazuri: o S i+1 ≥ a i . În acest caz, scriem semnul – în faţa lui a i şi păstrăm semnele determinate la pasul anterior pentru a i+1 ,a i+2 ,...,a N . Observăm că valoarea S i =-a i +S i+1 are proprietatea dorită (avem relaţia S i+1 ≤ a i+1 ≤ 2*a i din care, dacă scădem a i, se obţine S i+1 - a i ≤ a i deci S i ≤ a i ) o S i+1 < a i . În acest caz, scriem semnul + în faţa lui a i şi inversăm semnele determinate la pasul anterior pentru a i+1 ,a i+2 ,...,a N . Observăm că valoarea S i =a i -S i+1 are proprietatea dorită (avem relaţia S i+1 < a i pe care, dacă o înmulţim cu -1 şi adunăm apoi a i, se obţine a i - S i+1 > 0 deci S i > 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 a i+1 ,a i+2 ,...,a N trebuie schimbate şi 0 altfel. Complexitatea este O(N).
description
uyu
Transcript of Sir Descriere
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).
