7/17/2019 OJI_2015_1112_descr_P1_2sah

http://slidepdf.com/reader/full/oji20151112descrp12sah 1/4

Ministerul Educaţiei i Cercetării tiin ificeș Ș țOlimpiada de Informatică – etapa judeţeană-liceu Clasa XI-XII 

7 martie 2015

ro!lema 1  2sa" – solu ieț

rof# $drian anaete – Cole%iul &a ionalț '$# (# )aurian ' *otoșani

 Notăm f i , j  cantitatea de fân din pătratul de pe linia i i coloana j.ș

Avem f i , j=f i−1,  j−1+ f i−1, j+ f i−1,  j+1  pentru orice i , j  cu 1≤ i ≤ n+1 , 1≤ j ≤ 2n+1

Pentru prima cerin ă evident că orice cantitate nenulă de pe o linie va fi adunată la exact 3 cantită i de peț ț

linia următoare. Mai precis cantitatea f i , j de pe linia i  se adună la cantită ileț  f i+1, j−1   , f i+1, j

iș  f i+1, j+1 . Astfel deducem ca suma pe o linie este triplă fa ă de suma liniei anterioare. Deoarece sumeleț

formeaza o progresie geometrică de ra ie 3 cu primul termen ! adică suma pe prima linie este " o# inemț ț

că solu ia esteț   3k −1

. Pentru a o# ine maximul de punctaj la această cerin ă tre#uie calculată aceastăț ț

valoare folosind ridicarea la putere $n timp logaritmic.

Pentru a doua cerin ă o#servăm că traseul calului con ine pozi iileț ț ț  (1, k ) , (2, k +2 ) , (3, k +4 ) ,   ... ,

( i , k +2 i−2 )  ... unde k +2 i−2≤2n+1 adică i ≤ 2n+3−k 

2(≤n+1 )  

%xprimănd cantită ile din fiecare pozitie cu formula de recuren ă se o#servă că aceasta cantitate seț ț

descompune exact in cantită ile pe care le&ar consuma caii care pleaca de pe prima linie de pe coloaneleț

k +1,k +2   iș  k +3  mai precis notând  F k   solutia căutată vom avea formula de recuren ă'ț

 F k = F k +1+ F k +2+ F k +3

Pentru un calcul mai simplu vom considera  j=n+1 – k    o# inănd sirulț  T  j=Sk    ir care respectăș

rela ia de recuren ăț ț

T  j=T  j−1+T  j−2

+T  j−3

cu termenii ini ialiț

T 0=T 

1=1,T 

2=2

Acest ir mai este cunoscut i su# denumirea de ir (ri#onacci iar pentru calculul termenilor săi se potș ș șaplica te)nici similare calculului pentru teremnii irului *i#onacci ! sau mai general pentru oricare iruriș ș

definite prin formule de recuren ă liniara".ț

Pentru punctaj par ial se poate folosi generarea termenilor folosind liniar formula de recuren ă. Pentruț ț

 punctaj maxim tre#uie aplicată o metoda cu timp de execu ie logaritmic. +#servăm ca din formula deț

recuren ă se poate deduce că !in termeni de opera ii cu matrice" avem'ț ț

(0 1 0

0 0 1

1 1 1) ∙(

  T  jT  j+1

T  j+2

)=(T  j+1

T  j+2

T  j+3

)Deci folosind matricea

7/17/2019 OJI_2015_1112_descr_P1_2sah

http://slidepdf.com/reader/full/oji20151112descrp12sah 2/4

Ministerul Educaţiei i Cercetării tiin ificeș Ș țOlimpiada de Informatică – etapa judeţeană-liceu Clasa XI-XII 

7 martie 2015

 A=(0 1 0

0 0 1

1 1 1)

Avem

(  T  jT  j+1

T  j+2

)= A j

∙(T 

0

T 1

T 1

)ar matricea  A

 j

 se va calcula folosind ridicarea la putere $n timp logaritmic.

D%M+N-(A(/% MA(%MA(0% P%N(1 0%/% D+12 *+M1/%'

enumerotând liniile cu numere de la 0  la n  vom i coloanele de la de laș  – n  la n   i notândș

 potrivit noii numerotări cu V i j

 cantitatea de fân de pe linia i i coloanaș  j  ta#la arată astfel'

AvemV k +1

−k −1=V k −k =1

V k +1

k +1=V k k =1

V k +1

−k  =V k −k +V k 

−k +1=k +1

V k +1

k  =V k k −1+V k 

k =k +1

V k +1

 j =V k  j−1+V k 

 j+V k  j+1

, (∀ )−k < j<k 

V k 

 j=0 , (∀ ) j<−k sau j>k 

0%N A .Ț

V 00

V 1−1

V 10

V 11

V 2−

V 2−1

V 20

V 21

V 

V 3−

V 3−

V 3−1

V 30

V 31

V V 33

⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯

V i−i⋯   V i

−V i

−V i

−1V i

0V i

1V i   V i

3⋯   V i

i

⋯ ⋯ ⋯ ⋯ ⋯   ⋯ ⋯   ⋯ ⋯ ⋯ ⋯ ⋯   ⋯

V n−n

V n−i

V n−

V n−

V n−1

V n0

V n−

V 1

V n2⋯   V n

i ...   V nn

7/17/2019 OJI_2015_1112_descr_P1_2sah

http://slidepdf.com/reader/full/oji20151112descrp12sah 3/4

Ministerul Educaţiei i Cercetării tiin ificeș Ș țOlimpiada de Informatică – etapa judeţeană-liceu Clasa XI-XII 

7 martie 2015

-e notează Sk   suma valorilor nenule de pe linia k   potrivit nota iei introduse. Avem'ț

Sk +1=

 ∑ j=−k −1

k +1

V k +1

 j =V k +1

−k −1+V k +1

−k  +

 ∑ j=−k +1

−k +1

V k +1

 j +V k +1

k  +V k +1

k +1=¿

¿V k 

−k +V k 

−k +V k 

−k +1+  ∑ j=−k +1

−k +1

(V k 

 j−1+V k 

 j+V k 

 j+1 )+V k 

k −1+V k 

k +V k 

k =¿

¿V k 

−k +V k 

−k +V k 

−k +1+  ∑ j=−k +1

k −1

V k 

 j−1+  ∑ j=−k +1

k −1

V k 

 j+  ∑ j=−k +1

k −1

V k 

 j+1+V k 

k −1+V k 

k +V k 

k =¿

¿(V k 

−k +V k 

−k +1+  ∑ j=−k +1

k −1

V k 

 j−1)+(V k 

−k +  ∑ j=−k +1

k −1

V k 

 j+V k 

k )+(  ∑ j=−k +1

k −1

V k 

 j+1+V k 

k −1+V k 

k )=¿

¿(V k 

−k +V k 

−k +1+  ∑ j=−k +2

k 

V k 

 j)+(V k 

−k +  ∑ j=−k +1

k −1

V k 

 j+V k 

k )+(∑ j=−k 

k −2

V k 

 j+V k 

k −1+V k 

k )=¿

¿∑ j=−k 

k 

V k 

 j+∑ j=−k 

k 

V k 

 j+∑ j=−k 

k 

V k 

 j=¿

¿3∑ j=−k 

k 

V k 

 j=3Sk 

DeciSk +1

=3 Sk 

 adică avem o progresia aritnetică . DarS0=V 0

0=1

 de unde se o# ineț  Sk =3

k 

.

Datorită renumerotarii liniilor răspunsul corect la prima cerin ă esteț   Sk −1=3k −1

.

0%N A .Ț

*olosind aceeasi renumerotare a liniilor i coloanelor o#servăm că ta#la pentruș  n=1  este inclusă $n

ta#la pentru n=2  care la rândul ei este inclusă pentru ta#la pentru n=3   i a a mai departe. 4nș ș

general ta#la pentru n= j−1 este inclusă $n ta#la pentru n= j .

-e o#servă că fiecare pozi ie de pe prima linie i de pe o colanăț ș  k ≤ n+1  este de fapt prima pozi ie dinț

ta#la pentru ta#la corespunzătoare lui m=n+2−k  . *olosind renumerotarea liniilor i coloanelor ș

traseul calului pleaca din prima pozi ie a ta#leiț  (0 ,−m)   i va avea ca ultimă pozi ie care con ine fânș ț ț

exact ultima pozitie din aceasta ta#la , mai precis pozi iaț   (m ,m ) . 0u alte cuvinte cantitatea de fân

mâncată de cal va fi'

T m=∑i=0

m

V i2 i−m

Avem !folosind formulele de mai sus pentru V i j

"

7/17/2019 OJI_2015_1112_descr_P1_2sah

http://slidepdf.com/reader/full/oji20151112descrp12sah 4/4

Ministerul Educaţiei i Cercetării tiin ificeș Ș țOlimpiada de Informatică – etapa judeţeană-liceu Clasa XI-XII 

7 martie 2015

T m=V 0

−m+∑i=1

m−2

V i2 i−m+V m−1

m−2+V mm=¿

¿0+∑i=1

m−2

(V i−1

2i−m−1

+V i−1

2 i−m

+V i−1

2 i−m+1

)+(m−1 )+1

(i → i+1)¿

¿∑i=0

m−3

(V i2 i−m+1+V i

2 i−m+2+V i2 i−m+3 )+m=¿

¿∑i=0

m−3

V i2 i−m+1+∑

i=0

m−3

V i2 i−m+2+∑

i=0

m−3

V i2 i−m+3+m=¿

¿ (T m−1−V m−2

m−3

−V m−1

m−1

)+(T m−2−V m−2

m−2

)+T m−3+m

¿T m−1+T m−2

+T m−3−(m−2 )−1−1+m=¿

¿T m−1+T m−2

+T m−3

4n desenul de mai jos se descrie succint modul $n care !reducând ta#la si renumerotând coloane "

cantitatea consumată de calul A&!coresunzător ta#lei m " este egală cu suma cantită ilor consumate deț

caii 5,0 i D !corespunzători ta#lelorș   m−1, m−2, m−3 ¿ .

A 5 0 D 6

A 5 0 D 6 6 6

A 65 60 6D 6 6

6 6 6A 65 60 6D 6

6 6 6 6 6 6A 65 60 6D

6 6 6 6 6 6 6 6 6A 65 606 6 6 6 6 6 6 6 6 6 6 6A 65

6 6 6 6 6 6 6 6 6 6 6 6 6 6 6A