Page 15 - MATINF Nr. 3
P. 15

Concursul de Informatic˘a Programming Day                                                      15



            cˆate dou˘a ori pentru fiecare graf, pentru a depista primele dou˘a componente conexe. Astfel
            se determin˘a numerele de noduri ale acestor componente Nr 1 s , i, eventual, Nr 2 . Graful este
            2–neconex echilibrat dac˘a Nr 1 = n i /2 s , i Nr 2 = n i /2.

                La a doua cerint , ˘a, pentru fiecare graf se determin˘a un vector x = (x 1 , x 2 , . . . , x k ) cu numerele
            de noduri din fiecare component˘a conex˘a s , i, folosind metoda program˘arii dinamice, se verific˘a
            dac˘a exist˘a componente din x cu suma egal˘a cu n i /2, aceasta fiind condit , ia ca graful s˘a fie
            aproape 2–neconex echilibrat.

                Problema 2 – music
            Luca este un talentat cˆant˘aret , de pian. Mai nou, a ˆınceput s˘a s , i compun˘a melodii. O melodie
            este reprezentat˘a ca un s , ir de note muzicale (DO, RE, MI, FA, SOL, LA, SI). El foloses , te
            note din oricare dintre octavele 1 − K (adic˘a notele pe care le poate ad˘auga sunt – ˆın ordine
            cresc˘atoare: DO 1, RE 1, MI 1, FA 1, SOL 1, LA 1, SI 1, . . . , DO K, RE K, MI K, FA K,
            SOL K, LA K, SI K).
                Mai mult, Luca s , i-a creat chiar s , i propria metric˘a pentru calitatea unei melodii, bazat˘a pe un
            grad de armonie. Acesta se determin˘a astfel: se g˘ases , te cea mai ˆınalt˘a not˘a din melodie (dac˘a
            sunt mai multe astfel de note, se alege cea mai din dreapta) s , i se calculeaz˘a lungimea maxim˘a
            a unui subs , ir de note cresc˘atoare din intervalul [prima not˘a, nota cea mai ˆınalt˘a] (prologul
            melodiei). Apoi se g˘ases , te cea mai joas˘a not˘a din melodie (dac˘a sunt mai multe astfel de note,
            se alege cea mai din dreapta) s , i se calculeaz˘a lungimea maxim˘a a unui subs , ir descresc˘ator din
            intervalul [prima not˘a, nota cea mai joas˘a]. Gradul de armonie al melodiei va fi suma celor dou˘a
            lungimi + lungimea melodiei.
                                                                                           ˆ
                Luca s , i-a propus s˘a compun˘a o melodie cu gradul de armonie minim H. Ins˘a deoarece era
            prea entuziasmat, a ajuns s˘a creeze o melodie mult prea lung˘a (s , i nu vrea s˘a plictiseasc˘a pe
            nimeni cu o astfel de melodie). As , a c˘a ˆıs , i dores , te s˘a scurteze melodia compus˘a, prin eliminarea
            unui sufix al s˘au (zero sau mai multe note de la final).
                V˘a roag˘a s˘a ˆıl ajutat , i s˘a determine care este lungimea maxim˘a a unui sufix ce poate fi
            eliminat astfel ˆıncˆat melodia rezultat˘a s˘a aib˘a ˆınc˘a gradul de armonie minim H.

                Cerint , ˘a
                Cunoscˆand N (lungimea melodiei init , iale), H, precum s , i secvent , a de note care compun
            melodia init , ial˘a, se cere:
               1. lungimea maxim˘a a unui subs , ir de note cresc˘atoare din prologul melodiei init , iale;
               2. 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 cel put , in H.

                Date de intrare
                Fis , ierul de intrare music.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.

                Urmeaz˘a o linie cont , inˆand cele 3 numere N, K s , i H, separate prin cˆate un spat , iu. A treia
            linie cont , ine cele N note ce compun melodia init , ial˘a, separate prin cˆate un spat , iu.
                Date de ies , ire
                Dac˘a valoarea lui p este 1, se va rezolva numai punctul 1) din cerint , ˘a.
                ˆ
                In acest caz, ˆın fis , ierul de ies , ire music.out se va scrie un singur num˘ar, reprezentˆand
            lungimea maxim˘a a unui subs , ir de note cresc˘atoare din prologul melodiei init , iale.
                Dac˘a valoarea lui p este 2, se va rezolva numai punctul 2) din cerint , ˘a.
   10   11   12   13   14   15   16   17   18   19   20