Page 12 - MATINF Nr.2

12 D.A. Popescu, C. B˘alc˘au, D. Constantin

Solut , ie

Pentru prima cerint , ˘a se parcurg elementele subtabloului cerut s , i se calculeaz˘a suma lor,
dup˘a care aceasta se afis , eaz˘a.

Pentru a doua cerint , ˘a, dac˘a not˘am cu a tabloul dat, se construies , te un nou tablou sum, ˆın
care sum[i][j] reprezint˘a suma elementelor subtabloului cu colt , ul din stˆanga-sus de coordonate
(1,1) s , i colt , ul din dreapta-jos de coordonate (i,j). Pentru acest lucru folosim formula:

sum[i][j] = a[i][j] + sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1].

Suma elementelor unui subtablou din tabloul a cu colt , ul din dreapta-jos de coordonate (i,j)
s , i de dimensiune k este egal˘a cu sum[i][j] - sum[i - k][j] - sum[i][j - k] + sum[i - k][j - k].

Pentru verificarea condit , iei de num˘ar prim vom construi ciurul lui Eratostene pˆan˘a la valoarea
2
9n (aceasta fiind valoarea maxim˘a a unei sume calculate pentru un subtablou).
Clasele a XI-a s , i a XII-a

Problema 1 – intellistring
Tim s , i-a creat propriul test de inteligent , ˘a. El a scris un program care ˆıi genereaz˘a init , ial un
string s, iar apoi ˆıi d˘a la intervale fixe de timp operat , ii de forma ”adaug˘a caracterul dat la
sfˆars , itul stringului t” sau ”s , terge caracterul de la sfˆars , itul stringului t”, unde t este un string
init , ial vid.

Pentru a trece testul, Tim trebuie s˘a decid˘a ˆıntr-un timp scurt (setat anterior de el), dup˘a
fiecare operat , ie dat˘a de program, dac˘a stringul t se reg˘ases , te ˆın stringul s sub forma unui subs , ir
(caracterele lui t trebuie s˘a se reg˘aseasc˘a ˆın s ˆın aceeas , i ordine ca ˆın t, nu neap˘arat pe pozit , ii
consecutive).

ˆ
Ins˘a programul lui Tim este incomplet. El nu a reus , it s˘a implementeze partea de verificare
a r˘aspunsurilor date de utilizator. De aceea, are nevoie de un mic ajutor. De asemenea, el
ar mai vrea s˘a s , tie s , i lungimea celui mai lung prefix al alfabetului englez (adic˘a al s , irului
”abcdefghijklmnopqrstuvwxyz”) care se g˘ases , te ca subs , ir ˆın t (dup˘a fiecare operat , ie).

Cerint , ˘a

Dˆandu-se stringul s, precum s , i o list˘a de operat , ii de forma ”push c” (adaug˘a caracterul c la
finalul lui t) sau ”pop” (s , terge ultimul caracter din t), unde t este init , ial vid, s˘a se determine:

1. lungimea celui mai lung prefix al alfabetului care se g˘ases , te ca subs , ir ˆın t dup˘a fiecare
operat , ie;
2. rezultatul ˆıntreb˘arii ”se reg˘ases , te t ˆın s sub forma unui subs , ir?” dup˘a fiecare operat , ie din
lista dat˘a.

Date de intrare

Fis , ierul de intrare intellistring.in cont , ine pe prima linie un num˘ar natural p. Pentru
toate testele de intrare, num˘arul p poate avea doar valoarea 1 sau 2. Pe a doua linie se afl˘a
stringul s. Pe a treia linie se afl˘a num˘arul de operat , ii n. Pe fiecare dintre urm˘atoarele n linii se
afl˘a cˆate o operat , ie de tipul ”push c” sau ”pop”, cu semnificat , ia de mai sus.
Date de ies , ire

Dac˘a valoarea lui p este 1, se va rezolva numai punctul 1) din cerint , ˘a.