Page 16 - MATINF Nr. 3
P. 16

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
   11   12   13   14   15   16   17   18   19   20   21