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

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


Timp maxim de execuţie/test:
0.6 secunde
Memorie totală disponibilă/stivă:
16MB/1 MB

Cercetătorii britanici au descoperit un sistem de transport spaţial, creat de o civilizaţie foarte evoluată tehnic. Sistemul de transport are N staţii stelare (numerotate de la 1 la N). Poziţiile staţiilor pe harta stelară sunt identificate prin coordonatele lor carteziene (xi, yi, zi), 1≤i≤N.
Pentru a ajunge din staţia i în staţia j folosind sistemul de transport spaţial descoperit sunt necesare |xi-yj|+|yi-zj|+|zi-xj| secunde. Cercetătorii britanici au fost surprinşi să observe că timpul necesar pentru a călători de la staţia i la staţia i poate fi nenul, iar timpul necesar pentru a călători de la staţia i la staţia j poate să nu fie egal cu timpul necesar pentru a călători de la staţia j la staţia i.
Cercetătorii britanici îşi pun acum întrebarea "care sunt cele mai îndepărtate două staţii stelare?"  Mai exact, vor să determine două staţii a b pentru care timpul necesar de a ajunge
de la staţia a la staţia b este maxim.

Cerinţă

Scrieţi un program care să determine cele mai îndepărtate două staţii stelare (staţii pentru care timpul necesar pentru a călători de la prima staţie la cea de a doua este maxim).

Date de intrare

Fişierul de intrare stelar.in conţine pe prima linie număr natural N, reprezentând numărul de staţii stelare. Pe următoarele N linii sunt scrise câte 3 numere întregi separate prin spaţii x y z reprezentând în ordine coordonatele carteziene ale celor N staţii stelare.

Date de ieşire

Fişierul de ieşire stelar.out va conţine o singură linie pe care vor fi scrise două numere naturale distincte a b, cuprinse între 1 şi N, reprezentând două staţii stelare pentru care timpul de transport de la a la b este maxim. Staţiile afişate vor fi separate printr-un singur spaţiu. Dacă există mai multe soluţii, afişaţi soluţia cu a minim. Dacă există mai multe soluţii cu a minim, afişaţi soluţia cu b minim.

Restricţii

  • 2 ≤ N ≤ 300000
  • -100 000 ≤ xi, yi, zi ≤ 100000, pentru orice 1≤i≤N

Exemple

stelar.in stelar.out Explicaţii

3
2 5 3
3 2 1
4 1 3

2 3

Timpii necesari pentru transport sunt:
1 2: |2-2|+|5-1|+|3-3|=0+4+0=4
1 3: |2-1|+|5-3|+|3-4|=1+2+1=4
2 1: |3-5|+|2-3|+|1-2|=2+1+1=4
2 3: |3-1|+|2-3|+|1-4|=1+1+3=5
3 1: |4-5|+|1-3|+|3-2|=1+2+1=4
3 2: |4-2|+|1-1|+|3-3|=2+0+0=2

Cele mai îndepărtate două staţii sunt 2 3 (timpul de transport fiind 5).
prof. Marinel Şerban
Colegiul Naţional „Emil Racoviţă” Iaşi
marinel_serban@yahoo.com
propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la .campion 2010: greiere, divizori, kdist, pestera, partitie, sokoban, pitag, porumb, cheie, conferinta, chei, atelier, secv9, ny, radical, arbgraf, select, divk, bileprime, nx, reuniune, cazare, proiect, taler, atletism, echipa, ghinion, oldest, war, aliniere, sumb, cavaleri, joct, fluviu, camera616, aritm, stele, covor, subm, mess, secvnumber, cladire, ssmax, parcela, pion, subs, universitate, el, mahjong, rotund, sirmax, bdotcom, pack
De acelaşi autor: premii, finala, fractii, trei, manevre, nrcuv, an, vopsea, opmat, tramvai, bipal, kpal, sarpe, replace, factori, barca, perechi, grupe, cod, reactii, factura, decript, trenuri, holo, cifre, firma, tribile, mesaj, tricouri, pajura, monede, programs, fry, repeat, red, pavaj, bacan, nrbinar, invest, cutie2, loc, depou, nr3, zid, felinare, sir3, sqr, carte, labirint, stea, count, evaluare, super, schimb, zaruri, vectori, spirala, desen1, rima, ceas1, romane, sms, bac, excursia, joc7, furnici, munte1, cezar, marcare, excursie1, culmi, sume1, schi, nr4, fractie, cod3, medii, tren3, top, sant1, imagine, ocr, perfect, pluton, reforma, alee, ceas2, paritate, borcane, aranjare, comoara1, culmi1, reactivi, submult, sablon1, sir8, sume2, dansatori, smith, tom, matriosca, asociativ, control1, calorii, immortal, concat, mat, cubinvers, mine, divizori, cheie, joct, minmax, cladire, adunscad, razboi, ore, oras1, sumprod, prisme, operatii1, lgdrum, unupatru, chibrituri, extraprime, prieten, rebus1, grindina, opmult, betisoare, antitero, clase, pagini, ornament, ordine, spioni1
Despre tablou: cuburi1, zuzu, robinson, cuburi2, joc8, joc9, suma2, vizibil, masina3, cub2, lacusta, furnica, numere8, copaci1, ogorul, pesti, macheta, mxl, segmente, joc19, triunghi4, parc1, interclasare, rascoala, cifre5, monede2, betisoare, qvect, traseu3
surse trimise | ajutor