Page 15 - MATINF Nr. 3

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.