Lista de probleme 7

Filtrare

Dificultate

Operații intrare/ieșire


Etichete

#1378 Flori2

Fetiţele din grupa mare de la grădiniţă culeg flori şi vor să împletească coroniţe pentru festivitatea de premiere. În grădină sunt mai multe tipuri de flori. Fiecare dintre cele n fetiţe culege un buchet având acelaşi număr de flori, însă nu neapărat de acelaşi tip. Pentru a împleti coroniţele fetiţele se împart în grupe. O fetiţă se poate ataşa unui grup numai dacă are cel puţin o floare de acelaşi tip cu cel puţin o altă fetiţă din grupul respectiv.

Cu ocazia sărbătoririi marii victorii de la ONI2017, cei 10 Bistrițeni au pornit la drum cu scopul de a-și întemeia o țară. După multe dezbateri, aceștia s-au hotărât să o numească Zoomba. Și au mers ei ce au mers, până au ajuns într-un ținut pustiu, iar atunci, marele Zoli a spus: “Și aici să fie întemeiată Zoomba!” (La început, Zoomba nu are niciun oraș). Iulia are sarcina de a construi orașele, iar Maria va construi drumurile ce vor conecta orașele. Astfel, se disting următoarele evenimente:

  • 1: Iulia construiește un nou oraș. Dacă ultimul oraș construit este orașul x, atunci noul oraș va fi x + 1 (Dacă nu există niciun oraș în acel moment, atunci noul oraș construit va fi 1).
  • 2 x y c: Maria propune construcția unui drum bidirecțional ce leagă orașul x de orașul y de cost c.
  • 3 x: Zoli se întreabă care este costul minim pentru a lega un număr maxim de orașe (folosind drumurile propuse de Maria) cu scopul construirii unui județ (un județ este o grupare de orașe în care se poate ajunge din orice oraș în orice alt oraș) ce conține orașul x.

Scrieți un program care procesează M evenimente de tipurile precizate mai sus, și afișează în fișierul de ieșire rezultatele evenimentelor de tipul 3.

Se consideră un graf neorientat cu n vârfuri și m muchii. Cele m muchii se elimină pe rând din graf. Pentru fiecare muchie eliminată trebuie să spuneți câte componente conexe are graful.

#1117 Volum

K.L. 2.0 și-a dorit o piscină pe un grid A cu N linii și M coloane. Cum K.L. 2.0 nu a fost foarte inspirat, el a uitat să își niveleze terenul înainte de a construi piscina, astfel încât fiecare celulă de coordonate (i, j) a gridului are o înalțime Ai,j (1 ≤ i ≤ N și 1 ≤ j ≤ M). La un moment dat începe o ploaie puternică, care umple piscina cu apă. După terminarea ploii, K.L. 2.0 se întreabă câtă apă are în piscină.

Dintr-o celulă apa se varsă în celulele vecine cu care are o latură comună şi care au înălţimea strict mai mică decât celula curentă. Apa de pe marginea piscinei se scurge în exterior.

Pentru N, M și gridul A date, să se determine volumul de apă care a rămas în piscină.

După o confruntare eroică, Trump a fost ales democratic președintele unei republici prospere, TrumpLandia. Natural, prima sa prioritate e să construiască o rețea de buncăre, pentru a veni în întâmpinarea unui atac al vecinilor imperaliști.
N buncăre au fost deja construite. Trump trebuie să aleagă între M posibile rute bidirecționale pentru a le conecta. Un plan de conectare este alcătuit dintr-un subset minim de astfel de legături, astfel încât din fiecare locație să se poată ajunge în orice altă locație. Costul unui plan este dat de suma distanțelor legăturilor.

Deoarece rutele sunt vulnerabile la bombardamente aeriene, Trump vă cere să estimați un plan de cost minim. În plus, Trump vă cere să calculați Q soluții de rezervă, pentru situația în care una dintre cele M legături este sigur inclusă în plan.

Info Oltenia 2017, Clasele XI-XII, echipaje

#2127 ninjago

După ce eroii ninja l-au învins pe Nadakhan, de ziua celor dispăruți Zane trebuia să păzească cele n păpuși din muzeu. Între aceste păpuși există m coridoare pe care se poate circula în ambele sensuri. Se garantează faptul că pe cele m coridoare Zane poate ajunge la fiecare dintre cele n păpuși. Skulkiu, având la dispoziție 5 tipuri de obstacole A, B, C, D, E, încearcă să-l oprească pe Zane punând pe fiecare coridor câte 4 obstacole. Zane poate distruge obstacolele de tip A, B, C și D, dar nu poate să distrugă obstacolele de tipul E. Pentru a distruge un obstacol de tipul A arma lui Zane are nevoie de 1 unitate de energie, pentru a distruge un obstacol de tipul B de 2 unități de energie, pentru a distruge un obstacol de tipul C de 3 unități de energie, iar pentru a distruge un obstacol de tipul D de 4 unități de energie. Datorită dispozitivului cu care Skulkiu amplasează obstacolele pe coridor, cele patru obstacole de pe acelaşi coridor au o adâncime din ce în ce mai mare, ceea ce implică faptul că pentru a distruge al doilea obstacol amplasat pe coridor este nevoie de 5 ori mai multă energie decât cea obișnuită, pentru a distruge cel de-al treilea obstacol amplasat pe coridor este nevoie de 25 ori mai multă energie decât cea obișnuită, iar pentru a distruge al patrulea obstacol amplasat pe acelaşi coridor este nevoie de 125 de ori mai multă energie decât cea obișnuită. Indiferent de sensul de parcurgere al coridorului de către Zane pentru a înlătura obstacolele, energia consumată este aceeaşi, aceasta depinzând doar de ordinea în care au fost amplasate obstacolele de către Skulkiu. Zane nu va înlătura obstacolele de pe toate coridoarele ci doar strictul necesar pentru a avea acces la fiecare păpușă. Zane dorește să-i lase pe ceilalți ninja să se antreneze așa că face în așa fel încât ajutorul pentru distrugerea obstacolelor de tip E să fie minim și apoi ca el să utilizeze un număr minim de unități de energie. Pentru coridoarele pe care se află obstacole de tip E Zane consumă energie doar pentru obstacolele de tip A, B, C şi D. Inițial Zane se află lângă păpușa 1.

Cerințe:

  1. Precizați la câte dintre cele n păpuși poate ajunge Zane înainte de a cere ajutorul celorlalți ninja.
  2. Precizați pentru eliberarea câtor coridoare trebuie să ceară ajutor extern pentru a reuși să ajungă la toate cele n păpuși și câte obstacole de tip E sunt în total pe aceste coridoare.
  3. Precizați care este numărul minim de unități de energie utilizate.

#3004 Links

Se dau N puncte din plan prin coordonatele lor.
Se mai dau Q perechi de puncte, diferite de cele date inițial.

Să se verifice, pentru fiecare pereche de puncte (A , B) dintre cele Q, dacă există traseu care pornește din A și ajunge în B, prin deplasări cu pași de lungime 1 spre Nord, Vest, Sud, Est și evitând orice punct dintre cele N date inițial.