Lista de probleme 501

Filtrare

Dificultate

Operații intrare/ieșire


Etichete

#3010 bst

Un arbore binar de căutare (BST – Binary Search Tree) este un arbore binar cu proprietatea că valoarea memorată într-un nod este mai mare decât valoarea memorată în orice nod din subarborele său stâng și este mai mică decât valoarea memorată în orice nod din subarborele său drept. Dându-se un șir de n numere naturale, să se ordoneze crescător utilizând un BST.

Se dă un şir cu n elemente, numere naturale. Aflaţi câte secvenţe din şir au lungimea mai mare decât minimul elementelor din secvenţă.

#2972 rufe

Alex vrea să își usuce rufele pe balcon. El a spălat K tricouri și o șosetă. Uscătorul lui Alex are N niveluri, iar fiecare nivel are M locuri unde poate atârna câte un singur obiect de îmbrăcăminte. Alex usucă hainele într-un mod specific: începe prin a pune șoseta pe nivelul A, locul B, iar apoi aduce coșul de rufe cu cele K tricouri și le așază pe rând, mereu alegând o poziție liberă cât mai depărtată de locul unde a pus șoseta. Metrica pe care o găsește ca fiind cea mai potrivită când vine vorba de uscatul rufelor este distanța Manhattan, astfel încât distanța de la nivelul r1, locul c1 la nivelul r2, locul c2 are valoarea expresiei |r1 – r2| + |c1 - c2|. Aflați distanța dintre poziția unde a atârnat ultimul tricou și poziția unde se usucă șoseta.

#2971 tairos

Se dă un arbore cu N noduri, numerotate de la 1 la N. Arborele se va transforma astfel: la oricare etapă fiecare nod de gradul 1 diferit de rădăcină din arborele actual se înlocuiește cu un arbore identic cu cel dat inițial, iar la următoarea etapă procedeul se va relua pentru arborele obținut, formându-se astfel un arbore infinit. În imagini se prezintă un exemplu de arbore dat inițial, arborele obținut după prima etapă de prelungire a frunzelor și arborele obținut după două etape de prelungire a frunzelor. Să se determine câte noduri se află la distanță D de rădăcina arborelui infinit.

#2966 yinyang

Se dă o matrice A cu N linii și M coloane, cu valori cuprinse între 1 și N∙M inclusiv, nu neapărat distincte. O operație constă în selectarea a două linii sau două coloane consecutive și interschimbarea acestora (swap). O matrice yin-yang este o matrice în care A[ i ] [ j ] ≥ A[ i ][ j – 1], pentru orice pereche (i, j) cu 1 ≤ i ≤ N și 2 ≤ j ≤ M și A[ i ][ j ] ≥ A[ i – 1][ j ], pentru orice pereche (i, j) cu 2 ≤ i ≤ N și 1 ≤ j ≤ M.

Cerința

Să se determine numărul minim de operații necesare pentru a transforma matricea dată într-o matrice yin-yang.

Fie un graf neorientat cu N noduri și M muchii, care NU este conex. Să i se adauge grafului un număr minim de muchii, astfel încât acesta să devină conex. Fie extrai numărul de muchii nou-adăugate care sunt incidente cu nodul i, iar max_extra cea mai mare dintre valorile extra1, extra2,… , extraN. Mulțimea de muchii adăugate trebuie să respecte condiția ca valoarea max_extra să fie minimă.

#2937 ora

Gigel este la ora de informatică, iar profesorul i-a dat o sarcină: să sorteze numele celor n colegi ai săi după o regulă specială. Fiecărui nume i se asociază un număr care iniţial este 0 și crește cu 1 pentru fiecare pereche de vocale consecutive și scade cu 1 pentru fiecare pereche de consoane consecutive Dacă perechea este formată dintr-o vocală și o consoană, numărul nu se modifică.

Dându-se cele n nume ale colegilor, să se sorteze crescător după numerele asociate. La numere egale, se vor sorta alfabetic.

#2958 pavare2

Avem un coridor lung de lățime k și lungime n. Avem sarcina de a-l acoperi cu bucăți de gresii de dimensiuni 1 x k, 2 x k și 3 x k. Calculați în câte moduri distincte se poate acoperi coridorul cu cele 3 tipuri de gresii. Pentru că rezultatul este un număr mare, se cere restul împărțirii la 1.000.000.007.

Personajul acestei probleme este Lucian. Lucian locuiește în tara lui Verde Împărat, această tară având n orașe, numerotate de la 1 la n. Cum în orice poveste cu împărați există și o prințesă, și în problema noastră avem o prințesă, să o numim Maria. Maria este fiica lui Verde Împărat și în același timp prietena lui Lucian.

În tara lui Verde Împărat se apropie sărbătorile, iar ca să fie sigur de un nou mandat, împăratul a promis că va repara câteva drumuri, astfel încât să se poată ajunge din orice oraș, în oricare alt oraș, mergând doar pe drumuri care nu sunt stricate. Fiecare drum care este stricat are un cost de reparație , și având în vedere că se apropie sărbătorile, Împăratul ar vrea să repare drumurile optim, astfel încât să obțină un cost cât mai mic. Știind că Lucian vrea să-i ceară mâna Mariei, Împăratul i-a încredințat lui Lucian această sarcină, iar în cazul în care nu va putea să o îndeplinească îl va izgoni din tară. Lucian nu a fost prezent mai deloc la orele de algoritmică din liceu și vă cere vouă ajutorul pentru această problema complicată. Având la dispoziție lista drumurilor, precum și lista drumurilor stricate, voi trebuie să-i spuneți lui Lucian care este suma minimă pe care trebuie să o folosească pentru a se putea ajunge din orice oraș în oricare alt oraș.

Se dau două numere n și m. Aflați care este numărul minim și numărul maxim de noduri izolate într-un graf neorientat cu n noduri și m muchii în care nu există un muchie de la un nod la el însuși și între oricare două noduri diferite există cel mult o muchie.