Lista de probleme 234

Daniel a descoperit un izvor cu apă cristalină și vrea ca această apă sa ajungă în orașul în care locuiește.

Daniel are și o hartă cu drumuri pe unde se pot crea râuri astfel încât apa de la izvor să ajungă la destinație. Acestea vor avea un debit limitat notat cu c pentru prevenirea inundațiilor.

În apropierea izvorului există și alte orașe pe unde râurile pot să treacă până să ajungă la destinație. Și acestea apar pe hartă, dar pentru că numele lor nu ajută, vor fi notate cu numere de la 2 până la n - 1. Numerele sunt unice și au o semnificație. Cu cât un număr este mai mic, cu atât altitudinea locației notate cu acel număr este mai mare și la fel și invers. De aceea izvorul va fi notat cu 1 pe hartă și destinația cu n, iar Daniel va folosi doar gravitația pentru transportarea apei.

Apa se va deplasa intr-o singură direcție. Un râu care are punctul de plecare i și destinația j, va exista doar dacă i < j. Daniel vrea să ajungă cat mai multă apă în oraș ca toți locuitorii să se bucure de aceasta, dar trebuie să aibă grijă sa nu apară inundații. Ajutați-l pe Daniel să împartă debitul fiecărui râu.

Determinați numărul de fețe ale unui graf neorientat, conex, planar.

Se dau un arbore cu N noduri și rădăcina în nodul 1 al cărui muchii au lungimi exprimate prin numere naturale nenule și Q query-uri de forma u v. Pentru fiecare query să se afle suma lungimilor tuturor drumurilor distincte de la un nod aflat în subarborele cu rădăcina în nodul u la un nod aflat în subarborele cu rădăcina în nodul v modulo \( {10}^{9} + 7 \)(lungimea unui drum este egală cu suma lungimilor tuturor muchiilor ce îl alcătuiesc).

Avem în cartier un arbore cu nodurile colorate și cu rădăcina nodul 1. Pentru fiecare nod i al arborelui să se afișeze câte culori distincte sunt în subarborele cu rădăcina în i.

Într-o țară oarecare sunt n orașe, numerotate de la 1 la n, între care există șosele unidirecționale. Președintele țării vrea să facă o vizită electorală prin mai multe orașe în felul următor: aterizează cu elicopterul în orașul p, merge până în orașul q folosind rețeaua de șosele existentă, de unde pleacă cu elicopterul. Din punct de vedere politic unele orașe sunt sigure (conduse de aliați politici ai președintelui), altele sunt nesigure (conduse de adversari), iar președintele dorește să parcurgă numai orașe sigure.

Consilierii președintelui i-au propus mai multe perechi de orașe p q care pot fi alese ca punct de plecare și de sosire pentru vizită. Președintele vă cere să verificați pentru fiecare pereche dată dacă există un drum care să treacă numai prin orașe sigure.

În timpul celui de-Al Doilea Război Mondial, armata aliată desfășoară o operațiune de amploare în regiunea nordică a Libiei pentru a sabota aprovizionarea cu petrol a aparatului militar nazist, operațiune cunoscută sub numele de cod “Furtună la Tobruk”, și a dobândi controlul decisiv asupra zonei strategice a Africii de Nord. Se cere determinarea profitului maximal global al misiunii aliate, analizând în prealabil configurația sistemului defensiv inamic și forța de asalt a trupelor aliaților și respectând o serie de restricții predeterminate.

Studii recente arată că într-adevăr există viață inteligentă pe Marte. Problema de acum este că omenirea se află în război cu Marțienii și cea mai bună strategie pentru noi este să atacăm primii. Pe Marte se află un sistem de cale ferată complex alcătuit din N orașe conectate de M căi ferate bidirecționale.

Omenirea a apelat la cel mai mare bombardier posibil, domnul RANDy, ca să distrugă căile ferate. Pentru că este un maniac, el mai are doar o bombă disponibilă, deci va putea ținti doar o cale ferată. RANDy va ținti doar căile ferate strategice. O cale ferată este strategică dacă și numai dacă există o pereche de orașe (x, y) astfel încât să putem ajunge de la x la y și după bombardarea acesteia, să nu mai poți ajunge de la x la y.

Marțienii încep să se prindă de planul nostru, așa că încep să construiască Q noi căi ferate. După fiecare cale ferată nou adăugată, RANDy vrea să știe câte căi ferate strategice există. El este în dubii, și vă cere ajutorul.

Înainte de a participa la Olimpiada Naționala de Informatică, Zoli s-a decis să se plimbe prin oraș. Orașul în care locuiește Zoli are forma unui arbore, fiecare nod reprezentând o locuință iar deplasarea între acestea se efectuează prin intermediul muchiilor.

Zoli dorește să determine lungimea maximă dintre oricare două locuințe din orașul său.

Se dă un graf orientat cu n noduri. Determinați, dacă există, un drum hamiltonian.

În imperiul maleficului Costel s-a instaurat anarhia. În imperiu sunt n orașe, numerotate de la 1 la n, unite prin m șosele unidirecționale, fiecare șosea fiind controlată de o bandă afiliată la unul dintre cele k sindicate banditești existente în imperiu, numerotate de la 1 la k. Pentru a călători prin pe șoselele din imperiu, orice călător trebuie să plătească taxe sindicatelor: plata taxei către un anumit sindicat îi permite călătorului să folosească nelimitat orice șosea controlată de o bandă afiliată acelui sindicat. Pentru toate sindicatele se plătește aceeași taxă.

Călătorul Gigel trebuie să ajungă din orașul p în orașul q. Determinați numărul minim de sindicate banditești cărora Gigel trebuie să le plătească taxe, pentru a putea realiza călătoria dorită.