.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » megascoala

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
 .campion
megascoala


Timp maxim de execuţie/test:
1.4 secunde
Memorie totala disponibilă/stivă:
2 MB/1 MB

Pe insula Tortuga sunt N localităţi (numerotate de la 1 la N). Guvernatorul insulei, fostul corsar Ion Vrabie, a hotărât să construiască două megaşcoli moderne, la care vor merge copiii din toate localităţile. Copiii din fiecare localitate urmează să meargă la cea mai apropiată dintre megaşcoli.
Guvernatorul doreşte să selecteze localităţile în care vor fi construite megaşcolile astfel, încât timpul necesar pentru a ajunge la megaşcoală din cea mai îndepărtată localitate să fie cât mai mic posibil.
Funcţionarii au întocmit o hartă a insulei, pe care sunt indicate localităţile şi segmentele de drumuri care unesc unele perechi de localităţi. Pentru fiecare segment de drum care uneşte două localităţi este cunoscut timpul necesar copiilor pentru a ajunge dintr-o localitate în cealaltă. Pentru oricare două localităţi de pe insulă există cel puţin o secvenţă de segmente de drum, care le uneşte.

Notă:

  • un segment de drum începe la ieşirea dintr-o localitate şi se termină la intrarea în alta. El nu trece prin localităţi intermediare.
  • Pentru a asigura securitatea copiilor, intersecţiile segmentelor de drum sunt denivelate – nu poţi trece de pe un segment de drum pe altul în afara localităţilor.
  • Timpul de deplasare în interiorul localităţii se neglijează (se consideră 0)
  • Timpul de deplasare pe o secvenţă de segmente de drum este egal cu suma timpilor de deplasare pe fiecare segment de drum, inclus în secvenţă.

Cerinţă

Fiind dată harta drumurilor între localităţile insulei, şi durata parcurgerii fiecărui segment de drum, să se scrie un program care să determine localităţile, în care se vor construi megaşcolile.

Date de intrare

Fişierul de intrare megascoala.in conţine pe prima linie numărul natural N. Pe fiecare dintre următoarele N linii se află câte N numere naturale separate prin spaţii, reprezentând elementele unui tablou A de dimensiune N x N.
Elementul A[i,j] al tabloului este:

  • A[i,j]≠0 : există segmentul de drum, între localităţile i şi j. Timpul de deplasare între localităţi este  A[i,j].
  • A[i,j]=0, i≠j: între localităţile i şi j nu există un segment de drum, care să le unească direct. Drumul din i spre j trece prin localităţi intermediare.
  • A[i,j]=0, i=j: conform notei b., în interiorul localităţii timpul de deplasare e 0.

Date de ieşire

Fişierul de ieşire megascoala.out va conţine pe prima linie trei numere, separate prin câte un spaţiu reprezentând localităţile în care vor fi amplasate megaşcolile ordonate crescător, respectiv timpul maxim necesar pentru a ajunge la şcoală. Dacă există mai multe posibilităţi de alegere a localităţilor, se va scrie perechea lexicografic minimă.

Restricţii

  • 2 ≤ N ≤ 100
  • 0 ≤ A[i,j] ≤ 32000

Exemple

megascoala.in megascoala.out Explicaţie
4
0 3 4 2
3 0 2 5
4 2 0 3
2 5 3 0

1 2 2

(1,2) – din localitatea 3 pleaca in 2 (timpul 2), din localitatea 4 – în 1 (timpul 2).  Maxim din (2,2)=2.
Acelaşi rezultat se obţine pentru (1,3), (2,4) şi (3,4), dar soluţiile sunt lexicografic mai mari.
Pentru perechile (1,4) (2,3) se obţine timpul minim 3.

prof. Sergiu Corlat
Liceul Orizont Chisinau
scorlat@gmail.com
propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la .campion 2011: ore, pegals, valet, xpn, efect, nrperm, b2k, sumdivprod, nr0, maxviz, oneton, oras1, ksecv, ripstick, antic, oak, nor, nrpomi, sumprod, paisprezece, cover1, prisme, gxor, progresii, anagramabil, zuma, nrpal, sdmin, lista, operatii1, codarb, codpatrat, adprod, puncte4, qtri, reconst, gsm, subsiruri, mijloc, trifoi, cubulete, romb, maxbin, albine2, probleme, triburi1, 2ndesc
De acelaşi autor: nice, fib, atac, mere, ff, patrate, astre, baby, zapada, pendul, unu, dragon, placi, druid, bete, comori, ploaia, lot, arcas, factk, robot1, kalah, cetati, palc, expo, porumb, universitate, safeu, capra, zuma, gsm
Despre graf: gropi, tgv, matrice2, miniasm, picnic, mere, circuit, soldati, arce, conflicte, desen, robot, furtuna, net, cuvinte, excursie, cadere, pioni, reinvent, kreg, flood, croco, johnie, matrice, arthur, kimberley, ro, sol, caravane, bete, honest, police, pcod, zmeu, auto2, grazing, datorii, trafic, sponsori, monede1, apm, bile1, caini, masina1, bomboane, turn1, shgraf, paintball, program1, tgraf, kgb, algola, felinar, joc6, tric, homeless, promo, turism, casute, joc10, prieteni1, traseu, zapezi, litoral, lover, trip, garaj, ziduri, tv, pact, echipe1, vitale, spion, trasee, bcolor, scara2, lant, ab3, soc, team, gard, rsp, graf, mexc, dep, albinuta1, atac2, cabane, drumuri, tj, grade, jungla, lanterna, magic5, coment, urgenta, fazan, lanturi, cfr, site, traseu1, trmv, graphgame, minuni, telefon, ubergraf, carray, pestera, chei, arbgraf, war, fluviu, drumuri1, entries, ubuntzei, pack, fotbal1, pamant, dag, razboi, benzina2, wg, neconex, asfalt1, kubus2, module, progresii, dfs, prieteni3, grafxy, dineu, vot1, biperm, drumuri2, nrgraf, cristal, cartite, copaci3, dragoni, nuclee
Despre drum minim: miniasm, robot, furtuna, excursie, arthur, bete, zmeu, trafic, masina1, bomboane, traseu, litoral, lover, trip, scara2, team, gard, pitici1, base3, coach, lanturi, trmv, pestera, fluviu, ubuntzei, razboi, benzina2, kubus2, dragoni
surse trimise | ajutor