Lista de probleme 526

Filtrare

Dificultate

Operații intrare/ieșire


Etichete

N oraşe sunt conectate între ele prin M autostrăzi bidirecţionale, fiecare autostradă (a, b) având un cost de tranzit c ataşat. Se doreşte revizuirea sistemului de taxare, însă sunt câteva aspecte ce trebuie luate în calcul şi necesită investigaţie, deoarece o parte dintre cele N oraşe sunt centre comerciale sau turistice importante.

Se doreşte să se afle răspunsul la o serie de Q întrebări de forma: (X, T) – câte dintre celelalte N-1 oraşe, au acces către oraşul X, cu o taxă totală de cel mult T către fiecare oraş?

#3061 oracol

Gustavo, după ce a realizat că posedă abilitatea de a vedea în viitor, a decis că a venit momentul să treacă la următorul nivel și să-și valorifice capacitățile extrasenzoriale. Pentru a câștiga prestigiu și a deveni mai cunoscut în rândurile magicienilor profesioniști, acesta a ales să debuteze la Olimpiada Națională de Informatică prin prezicerea datelor de intrare pentru anumite probleme propuse în concurs. Primul client al lui Gustavo, Alfredo, ar dori să afle într-un mod inedit conținutul unui fișier de intrare aferent unei probleme de concurs, în care sunt scrise elementele unui șir p de N numere întregi. Pentru a face lucrurile mai interesante, Gustavo îi percepe o taxă de C(i,j) bănuți pentru a-i divulga suma numerelor din șirul p cu indici în intervalul [i, j], anume pi + pi+1 + ... + pj. Dându-se valoarea lui N și toate valorile C(i,j) cu 1 ≤ i ≤ j ≤ N, determinați costul total minim pe care trebuie să-l plătească Alfredo pentru a afla toate elementele șirului p.

Se dă un șir v format din N elemente naturale nenule nu neapărat distincte. Asupra șirului putem aplica un singur tip de operație: interschimbarea a două elemente aflate pe poziții consecutive. Dându-se un număr natural K, se cere șirul minim lexicografic ce se poate obține prin aplicarea a cel mult K interschimbări de elemente de pe poziții consecutive.

#3049 scara2

Avem N persoane notate cu etichetele 1, 2, …, N, într-o ordine oarecare și o scară cu N trepte. Persoanele sunt așezate în șir indian, cu fața spre locul unde se află scara. Treptele scării sunt inițial neocupate. În mod repetat persoana aflată la acel moment la capătul din dreapta al șirului se poziționează pe scară pe prima treaptă neocupată, iar fiecare dintre persoanele aflate pe treptele inferioare coboară de pe scară și se repoziționează la capătul din dreapta al șirului, începând cu cea de la prima treaptă a scării. Acțiunea se oprește atunci când sunt ocupate toate treptele pe scară. Se cere să se afișeze etichetele persoanelor în ordinea în care acestea sunt așezate pe scară la final.

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