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

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


Timp maxim de execuţie / test:
0.1s
Memorie totala disponibilă / stivă:
15MB / 1MB

Serviciile secrete din Ţara Crivăţului au o reţea foarte bine pusă la punct. Reţeaua este formată din N centre, numerotate de la 1 la N. Între centre există drumuri ce pot fi parcurse în ambele sensuri, de lungimi cunoscute. Un drum uneşte două centre. Utilizând drumurile existente, între oricare două centre există legătură (directă sau trecând prin alte centre). Distanţa dintre două centre este lungimea totală minimă a drumurilor parcurse pentru a ajunge de la un centru la celălalt.
Şeful Teo a hotărât împărţirea tuturor centrelor în două departamente, de spionaj şi de contraspionaj. O împărţire este considerată optimală dacă maximul distanţelor dintre oricare două centre din cadrul aceluiaşi departament este minim.
Dacă există mai multe soluţii cu acelaşi maxim, se alege soluţia pentru care diferenţa (în valoare absolută) dintre numărul de centre din departamentul spionaj şi numărul de centre din departamentul contraspionaj este minimă. Dacă şi în acest caz există mai multe soluţii, este preferată prima în ordine lexicografică.

Cerinţă

Dându-se descrierea reţelei, să se scrie un program care să găsească o împărţire optimală a centrelor în două departamente.

Date de intrare

Fişierul de intrare spion.in conţine pe prima linie numerele naturale N şi M reprezentând numărul de centre şi respectiv numărul de drumuri dintre ele. Pe fiecare dintre următoarele M linii vor fi scrise câte trei numere naturale; mai exact, pe linia i+1 sunt scrise numerele ai bi ci cu semnificaţia “există un drum între centrul ai şi centrul bi de lungime ci”. Numerele scrise pe aceeaşi linie în fişierul de intrare sunt separate prin câte un spaţiu.

Date de ieşire

Fişierul de ieşire spion.out va conţine două linii. Pe prima linie va fi scris un număr natural care reprezintă maximul distanţelor dintre două centre din acelaşi departament. Pe cea de a doua linie vor fi scrise N caractere. Caracterul i va fi litera C dacă centrul i va fi în departamentul contraspionaj sau litera S dacă centrul i va fi în departamentul spionaj în împărţirea optimală determinată.

Restricţii

2 < N < 101
0 < ai, bi ≤ N
0 < M, ci < 16001

Spunem că împărţirea (x1, x2, ..., xN) precedă din punct de vedere lexicografic împărţirea (y1, y2, ..., yN) dacă există k astfel încât xi=yi, pentru orice i<k şi xk<yk; litera C < litera S.
Se vor acorda punctaje parţiale după cum urmează:
– pentru distanţa maximă determinată corect: 20% din punctajul testului respectiv
– dacă soluţia este corectă (din punctul de vedere al distanţei maxime şi al diferenţei absolute minime), dar nu este prima în ordine lexicografică: 60%
– pentru obţinerea primei soluţii corecte în ordine lexicografică: 100%.

Exemple

spion.inspion.outExplicaţii
5 4 1 2 1 2 3 1 3 4 1 2 5 7 3 CCCCS Maximul distanţelor dintre oricare două centre din cadrul aceluiaşi departament este 3.
Diferenţa în valoare absolută dintre numărul de centre din departamentul spionaj şi cel de contraspionaj este 3.
Soluţia este prima în ordine lexicografică.
O altă soluţie ar fi SSSC, dar aceasta este mai mare lexicografic.
5 5 1 3 1 3 2 1 2 5 7 3 4 7 2 4 1 3 CCCCS Maximul distanţelor dintre oricare două centre din cadrul aceluiaşi departament este 3.
Diferenţa în valoare absolută dintre numărul de centre din departamentul spionaj şi cel de contraspionaj este 3.

propunător: Prof. Marinel Şerban
Liceul de Informatică “Grigore Moisil”
marinel_serban@yahoo.com
Articole recomandate
Probleme recomandate
De la ONI 2005: baschet, ingerasi, numar1, prieteni, robinson, aritma, cezar, cuburi2, joc8, bifo, joc9, pal, romeo, seceta, antena, avere, joc11, paianjen, suma2, vizibil, masina3, csir, lsort, patrat, ziduri, anticip, bsir, evantai, galax, texan
Despre programare dinamică: vedete, fbr, tgv, zeratul, rv, comun, retea, circuit, sumdif, copaci, drum, text, palind, joc, vikingi, rafturi, balaur, plimbare, party, pc, pioni, seif, iepuri, numere3, perm, ture, bilete, prop, ro, reduceri, cuburi, invest, cutie2, stalpi, nr2, judete, strict, auto2, tree, jobs, leaves, pstring, program, datorii, senzori, farfurii, joc1, barbie, ambigram, rlcs, cub1, bio, chimie1, otilia, pasune, remi, sir23, tren1, joc5, pachete, echipe, comb, agitatie, ivv, peste, pitici, pipe, shgraf, tabara1, stop, randuri, zidar, log, sant, produs, subsir, cover, bcast, emax, dist, mesaj1, imax, avere, asmax, raft, suma2, joc12, fni, nr4, join, transport, masina3, lsort, microvirus, fat, cafea, echipe1, anticip, bsir, diamant, petrom, evantai, acolor, evo, bombo, lacusta, lant, team, pitici1, numere8, dep, stiva, subgeom, pviz, tir1, cabane, piramida1, mosia, cuvinte1, gaina, materom, sortari, turnuri, trans, politie, codul, dansatori, nkbiti, kperms, treegame, siruri2, 123, jucarii, bradut, joc15, expozitie, text3, ic, echilibru, distsir, kmax, stalpi1, gaz, triunghi2, v2d, cuiburi, mine, orientare, activ, secvbiti, kcons, pokemon, ubergraf, left, acerc, autostrazi, kdist, select, cazare, fluviu, telecomanda, parcela, pion, subs, suma4, sirmax, bdotcom, viena, sablon2, telecab, ikebana, radare, hacker, obstacole, robotel, centrala, verigi, cds, wg, minusk, radioactiv, enigma, jb, efect, maxviz, ripstick, progresii, maxtri, combcuv, blis, subsiruri, mijloc, probleme, unuzero, palindrom1, minerale, speed, zmax, spider, cntgcd, interclasare, bus, pariuri, riglef, fractii2, fall, arbsum, conuri, arbvalmax, procente, metrou
Despre matrice: vopsea, harta, opmat, sarpe, light, magic2, tetris, origami, concurs, iepuras, tribile, criptmat, cutie, patrate, 3d, pajura, perspic, vecini2, livada, matrice3, kafka, erdos, grup, scor2, reteta2, rezervatie, scoici, tablou, game, stea, submatrix, cifru, jokes, oua, trecere, na, dotnet, renju, ghici, mere1, agitatie, lacuri, sotron, desen1, camion, ceas1, fibo, parc, excursia, matricea, zidar, joc6, log, concurs2, cladiri, dist, centru, robinson, cuburi2, joc8, joc9, romeo, adevar, soricel2, avere, joc11, vizibil, sah1, blockout, masina3, lsort, anticip, matrice1, evantai, pereti, zumzi, roboti, placare, tabel, ocr, numere7, lacusta, becuri, sir5, flori, cartele, furnica, pavare, poarta, rj, peri, poligon2, sablon1, gradina, matrice4, poartas, balcon, submdisj, v, matrx, figura, neuroni, raze, roboti1, bila, iepurasi, colorare, mat, submatrix1, simetric1, plaja, xor2, guess, albine1, joct, alfabetar, stele, tablou1, alpinist, cladire, cri, grupe2, el, mahjong, sir9, acces, tort1, joc17, mesaj3, zar1, xy, poteci, avioane, broscute, safeu, acoperire1, radioactiv, robot4, lcdr, jb, slide, maxtri, dame, triunghi4, elicop, compresie, mijloc, cubulete, romb, medalion, bile6, zigzag, puncte5, intersectii, matd3, matrixdel, speed, seif1, traseu2, incadrare, betasah, zona, latin, zmax, amestec, sudoku1, gradina1, spider, zone, bemo, rombul, interclasare, rebus1, tabla, arrows, pseudobil, patrat1, rascoala, harta2, relatii, lasere, defrag, matcnt, ssdj, cript, ssk, teren1, fence, cifre6
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, 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, megascoala, grafxy, dineu, vot1, biperm, drumuri2, nrgraf, cristal, cartite, copaci3, dragoni, nuclee
Despre căutare binară: gropi, pod, uscat, checkin, copaci, aven, br, furtuna, livada, numar, matrice, sume, bacan, toys, chimie2, trafic, ants, multiplu, ghici, sirag1, tabara, puncte1, centru, harta1, salvare, poze, dist1, patrate5, resturi, lanterna, sea2, vot, standard, cantor, medalii, binperm, mobil, stalpi1, expo, miere, conferinta, subs, pack, obstacole, dag, acoperire, verigi, bradut2, triburi, intervale, mijloc, patru, eliminare, vectori1, calcule, secvp, dreapta, colina, ssk, robotics, cabana
Despre conexitate: arce, flood, matrice, shgraf, trip, pact, echipe1, vitale, bcolor, mexc, dep, fazan, cfr, chei, teme, entries, pamant, neconex, module, drumuri2, cristal, nuclee
surse trimise | ajutor