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

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


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

O parantezare corectă se obţine aplicând una dintre următoarele reguli:
• şirul vid este o parantezare corectă;
• dacă S este o parantezare corectă, atunci (S) este o parantezare corectă, iar cele două paranteze ( şi ) care încadrează şirul S sunt denumite paranteze pereche;
• dacă S1, S2, … , Sk sunt parantezări corecte atunci şirul S1S2...Sk obţinut prin concatenarea acestora este o parantezare corectă.
De exemplu şirurile (), ()(), (()) şi (()())() reprezintă parantezări corecte, în timp ce )(, ()()( şi (()()))) nu sunt parantezări corecte.
Fie S un şir care reprezintă o parantezare corectă. Pentru fiecare dintre parantezele pereche din şirul S asociem un cost egal cu diferenţa dintre poziţia pe care se află în S paranteza închisă şi poziţia parantezei deschise pereche. Poziţiile în şir le considerăm numerotate începând cu 1. Costul total al unei parantezări corecte îl reprezintă suma costurilor tuturor parantezelor pereche din aceasta.
De exemplu, şirul (()()) este format din trei paranteze pereche, situate pe poziţiile 2 şi 3, apoi 4 şi 5, respectiv 1 şi 6. Costul total al parantezării este 3-2 + 5-4 + 6-1 = 7.
Numim operaţie swap interschimbarea a două paranteze situate în şir pe poziţii alăturate. Această operaţie este validă doar dacă şirul nou obţinut este la rândul său o parantezare corectă şi dacă noua parantezare are costul total strict mai mic decât cea iniţială.

Cerinţă

Scrieţi un program care citeşte o succesiune de N caractere reprezentând o parantezare corectă şi determină:
a) Costul total asociat parantezării citite
b) Costul minim al unei parantezări obţinute prin efectuarea unei singure operaţii swap valide asupra parantezării citite.
c) Numărul de posibilităţi de a efectua o singură operaţie swap validă asupra parantezării iniţiale pentru a obţine costul determinat conform cerinţei b).

Date de intrare

Fişierul de intrare swap.in conţine pe prima linie numărul natural N şi pe a doua linie o succesiune de N caractere reprezentând o parantezare corectă.

Date de ieşire

Fişierul de ieşire swap.out va conţine pe prima linie un număr natural reprezentând costul parantezării citite. A doua linie va conţine un număr natural reprezentând costul minim determinat conform cerinţei b) sau valoarea -1 când nu se poate efectua nici o operaţie swap validă asupra parantezării citite. A treia linie a fişierului va conţine un număr natural reprezentând răspunsul la cerinţa c) sau 0 dacă numărul afişat conform cerinţei b) a fost -1.

Restricţii

2 ≤ N ≤ 90000
• Pe fiecare dintre cele 3 linii ale fişierului de ieşire trebuie să se afle un singur număr întreg. Dacă numărul de pe prima linie este corect, se acordă 20% din punctajul testului. Dacă numărul de pe a doua linie este corect, se acordă 20% din punctaj. Dacă numărul de pe a treia linie este corect, se acordă 60% din punctaj.

Exemple

swap.inswap.outExplicaţii
8 ()(())() 6 4 1 Pentru cerința a) costul parantezării este 2-1+6-3+5-4+8-7=6. Executând o operaţie swap între parantezele de pe poziţiile 4 și 5 se obține șirul ()()()() care are costul 4, aceasta fiind singura posibilitate de a obține acest cost.

autor: Prof. Dana Lica
propunător: Prof. Emanuela Cerchez
Colegiul Naţional ″Emil Racoviţă″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la ONIGIM 2013: cursa1, patrate7, secvp, latin, zmax, extraprime, greieri, onigim, divizori1, remi1, tetris3, amestec, sudoku1, eoliene
De acelaşi autor: compus, taste, arce, balbe, drept, scor, sume3, spair, bitslang, police, tree, reteta2, farfurii, caramele, apm, maraton, masina1, bomboane, soldati1, concurs1, puncte, pipe, camion, imax, litoral, dreptc, bal, prefix1, tablite, lanturi, loto, bila, popic, activ, game1, pitag, secv9, divk, taler, bdotcom, oak, ozn1, optim, puncte5, tetris3, monede2, ssk
Despre stiva: sl, teren, reactii, complex, auto, bile3, chimie2, vile, puncte1, masina3, matrice1, dir, stiva, munte2, perle, basm, predecesor, expresie1, telecab, expresie2, liste, intervale, jocs, expeval, copaci2, plus, azeval, unific, stiva1, ecp, charlie
Despre vector: trei, simetric, egal, ruleta, pod, uscat, afise, an, bunici, cursa, onu, tramvai, cadou, kpal, expresie, piticot, roci, petrol, grad, ruleta2, ecran, palma, concurs, holo, ab2, tren2, cifre, mgo, firma, anagrame, joc2, br, maxim, astre, numere2, baby, zapada, hd, startrek, vecini2, drept, teatru, tir, patrate2, nr, cifra, repeat, unu, criptare, ratb, placi, sume3, turist, matrice3, pavaj, sume, kafka, bacan, spair, grup, friends2, bitslang, fisc, scor2, cat, nr3, chimie2, zid, politics, submat, reteta2, rezervatie, creioane, felinare, 2numere, exp, scoici, patrate1, playlist, sqr, carte, oua, turn, ants, div3, jeton, politic, trecere, maraton, zaruri, suma1, mere1, agitatie, lacuri, secv, sotron, triunghi, carti1, spioni, kalah, excursia, matricea, maxq, oras, furnici, baschet, ingerasi, numar1, prieteni, aritma, cezar, bifo, pal, seceta, bare, soricel1, antena, avere, paianjen, bloc, schi, suma3, fractie, tunel, pepsi, prefix, tren3, avion, premii1, csir, top, bsir, secvente, cod4, cuburi3, limbaj, panouri, sant1, zumzi, sport1, baschet1, mere3, powerpuff, placare, sir4, volei1, tabel, ocr, numere7, lacusta, flori, pluton, elfi, mare, grupe1, maroco, cartonas, cabina, case, cod5, furnica, numere8, paritate, comoara1, exponent, control, exp1, joc13, popas, reactivi, siruri1, vanatoare, submult, text1, taxe1, visul, paranteze, puncte3, cub3, numere9, panglica, pietre, poartas, sume2, bal, secvsir, vot, prefix1, accesibil, palc, standard, bursa, meteo, jetoane, printesa, palindrom, joker, matriosca, loto, cuvant, cladiri1, secvente1, zar, tren4, asociativ, lego, medalii, figura, joc14, neuroni, char, dartz, turism1, calorii, xor1, paltrei, album, livada1, colorare, greutati, brazi, submatrix1, plaja, cd1, cifru3, permutare, miere, tetris1, conferinta, atelier, radical, bileprime, nx, atletism, sumb, minmax, sumacifre, jocprim, sircifre, cmmdcsecv, secvb, siruri3, cifru4, vase, carte1, grad1, litere, magic6, macheta, butoane, ec, stalpi2, fagure, goe, papusa, taburet, mesaj3, zar1, joc16, talent, joc18, cos, punctfix, risipa, liste, triburi, nr0, oneton, nor, nrpomi, paisprezece, anagramabil, zuma, joc20, dale, perechi2, consiliu, becuri2, codpatrat, adprod, qtri, reconst, arme, triunghi4, deal, ozn1, cifru5, flori1, elicop, roata, trifoi, maxbin, culori2, numar5, bile6, proiecte, alune, cuburi4, sstabil, intersectii, copaci2, 7segmente, amedie, drept2, divider, eliminare, matd3, prodnr, fraze, vectori1, compar, unific, galbeni, clepsidru, calcule, puncte6, maxp, cursa1, secvp, extraprime, onigim, divizori1, remi1, tetris3, amestec, eoliene, split, momente, secvente2, ausoara, aranjare2, vintage, binremove, sminus, subsets, interclasare, palindromuri, colina, doitrei, rebus1, tcif, munte3, triunghi6, schi1, rascoala, solitar, praslea, vot2, tema, sprime, sir2dif, aperm, unudoi, prajituri, tan, concurs4, ech, arc, dominant, ordine, tv1, nebuni, sort2dist, lightbot, iepuras1, castig
surse trimise | ajutor