Lista de probleme 493

Filtrare

Dificultate

Operații intrare/ieșire


Etichete

#3019 joc10

Trei copii au inventat un joc nou care se joaca în trei. Ei au desenat pe asfalt un triunghi echilateral ABC şi l-au împărţit în N*N triunghiuri echilaterale congruente. Pornind din vârful A al triunghiului ABC către latura opusă BC, au desenat cercuri identice, câte unul în fiecare vârf al triunghiurilor formate, iar în interiorul fiecărui cerc au scris câte un număr natural nenul. Să se determine: 1) punctajul maxim pmax pe care îl poate obţine un concurent la finalul jocului; 2)valoarea cercului iniţial vcerc al concurentului care va obţine punctajul maxim.

Olimpiada de Informatică, etapa sector, 2009, București, clasele 11-12

#3011 lastk

Se dă un șir a[1], a[2], …, a[n] de numere naturale și un număr natural k. Să se determine cele mai mari k numere din șir.

#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.