Page 16 - MATINF Nr. 3

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

ˆ
In acest caz, ˆın fis , ierul de ies , ire se va scrie un singur num˘ar - lungimea maxim˘a a unui sufix
ce poate fi eliminat astfel ˆıncˆat melodia rezultat˘a s˘a ˆıs , i p˘astreze gradul de armonie ≥ H.

Restrict , ii s , i preciz˘ari
5
• 3 ≤ N, H ≤ 10 , K ≤ 1000
• Pentru 40% din teste, 3 ≤ N, H ≤ 4000
• Se garanteaz˘a c˘a melodia init , ial˘a are gradul de armonie ≥ H
• Pentru rezolvarea corect˘a a cerint , ei 1 se acord˘a 40% din punctaj, iar pentru cerint , a 2 se
acord˘a 60% din punctaj

Exemple

music.in music.out Explicat , ie
1 3 p = 1
7 10 6 Nota cea mai ˆınalt˘a este SI 7.
DO 3 MI 1 RE 5 SI 7 MI 4 LA 2 Cele mai lungi subs , iruri cresc˘atoare din
SI 1 prolog sunt DO 3, RE 5, SI 7 s , i MI 1,
RE 5, SI 7, de lungime 3.
music.in music.out Explicat , ie
2 4 p = 2
7 10 6 Gradul init , ial de armonie = 3 (subs , irul
DO 3 MI 1 RE 5 SI 7 MI 4 LA 2 cresc˘ator) + 2 (subs , irul descresc˘ator) + 7
SI 1 (lungimea melodiei) = 12.
Dac˘a elimin˘am un sufix mai lung de 4,
gradul de armonie devine ≤ 5.

Timp maxim de execut , ie: 0.25 secunde/test.
Memorie total˘a disponibil˘a:16 MB.
Dimensiunea maxim˘a a sursei: 5 KB.

Solut , ie Pentru prima cerint , ˘a se determin˘a nota cea mai ˆınalt˘a s , i, utilizˆand metoda pro-
gram˘arii dinamice, se g˘ases , te lungimea maxim˘a a unui subs , ir cresc˘ator din prolog. Pentru
cerint , a a doua se construiesc, utilizˆand metoda program˘arii dinamice, un vector cu lungimile
maxime ale unor subs , iruri cresc˘atoare din prologul curent s , i un vector cu lungimile maxime ale
unor subs , iruri descresc˘atoare din intervalul [prima not˘a, nota cea mai joas˘a], pe baza c˘arora se
determin˘a gradul de armonie al melodiei part , iale (subs , irul format din primele i note), pˆan˘a
cˆand acest grad devine mai mare sau egal cu H.

Concursul de programare a robotilor LEGO
,

Problema – robotic˘a

La acest concurs a fost propus˘a urm˘atoarea problem˘a.
Durata deplas˘arii: maxim 2 minute.

Punct de plecare: p˘atrat verde, iar robotul orientat ˆın orice direct , ie, dar cu toate rot , ile
pe verde.

Activitate robot: Pentru dou˘a cuburi date, de culoare ros , u s , i galben, se cere s˘a se ˆımping˘a
cuburile ˆın zonele de culoare corespunz˘atoare (cubul galben ˆın orice zon˘a de culoare galben˘a, iar