806 Par

[•wefgef]

Aici puteti discuta despre problema Par.

[•f.v.anton]

am vazut in solutia oficiala, ca se spuna ca o solutie buna este sa adaugi paranteze intr-o stiva (deschise) si cand vine una inchisa stergi una inchisa si una deschisa. La sfarsit vor ramane numai deschise, iar solutia este nr. acestora/2. Daca eu am numarat cate paranteza deschise, cate inchise si apoi am impartit diferenta la 2, ce e gresit? Sau care e diferenta intre solutia oficiala si asta? Sau macar aveti un contraxemplu ? Multumesc.

[•bogdan2412]

Un contraexemplu ar fi ceva de genul ())((), o sa afisezi 0 si trebuie 2. In solutia cu stiva, in momentul in care stiva e goala si vine un ), esti obligat sa o schimbi in (.

Am vazut in sursa ca ai diferenta a - b, incearca si diferenta in valoare absoluta. Un caz de genul ())). Sunt curios cate puncte iei

[•f.v.anton]

1 sec

  mama cum mai luam 20 de pct in plus ... Oricum mi-am dat seama, ca nu e chiar corecta rezolvarea . Am sa o fac si cu stiva, dar nu mai am chef acum, nu e greu de loc....ce fraier am fost...

[•jupanubv92]

O alta solutie care nu este prezentata in solutiile oficiale ar fi sa numeri cate paranteze deschise sunt si cate paranteze inchise , insa trebuie mai intai sa eliminam din numarul parantezeleor inchise si din cele deshise , parantezele care se inchid adica () . asta se poate face inca de la citire daca citesti caracter cu caracter . Cand intalnesti o pranteza inchisa te intrebi daca ai vreo paranteza deshisa ca sa poata face pereche cu ea si daca exista o astfel e paranteza numaul parantezelor deschise va scadea cu o unitate.

Cod:

for i 1 n 
if(x==')')   // unde x este a i a paranteza din sir
{if(nr_paranteze_deshise!=0)
      nr_paranteze_deschise--;
     else nrparanteze_inchise++;
}
   else nr_paranteze_deschise++;

Dupa ce ai afalt numarul parantezelor deschise si inchise tot ce trebuie sa faci e sa vezi daca numarul parantezelor inchise si deschise  este par sau impar.
  1 Daca sunt pare se va afisa nr_para_desch/2+nr_para_inchise/2
  2 Daca sunt impare se va afisa (nr_para_desch-1)/2+(nr_para_inchise-1)/2  + 2

Explicatia este simpla : daca ai ))(( ca sa le inchizi intorci prima paranteza si ultima , iar daca ai )))((( intorci prima paranteza , ultima si cele doua paranteze din mijloc .

De exemplu daca ai secventa  )))(()()())(((  numeri parantezele deschise si parantezele inchise care nu sunt pereche adica elimini perechile de paranteze si vei avea )))((( pentru ca (()()()) este corect parantezata . Numarul de paranteze deschise va fi 3 la fel ca numarul parantezelor inchise .Cum am spus mai sus ca secventa sa fie corect parantezata vei intoarce prima paranateza , a treia , a patra si ultima paranteza si vei avea ()()() si rezultatul final este  (3-1)/2+(3-1)/2 + 2  = 4 . 

Sper sa fie buna solutia mea eu am luat maxim. Am tinut sa o prezint deoarece nu era prezentata in solutia oficiala. Solutia asta nu foloseste nicio stiva  , ci doar cateva variabile .  Scz pentru acest post dar nu il sterg ca nu mai intelege lumea de ce a scris astromony postu de mai jos .

[•astronomy]

Solutia ta este echivalenta cu solutia oficiala  Stiva aceea despre care se vorbeste este la nivel conceptual, poti folosi desigur numai doua variabile cum faci si tu. Algoritmul tau functioneaza tot pe principiul stivei, nr_paranteze_deschise reprezinta numarul de paranteze deschise din stiva ce asteapta sa fie inchise, iar cand decrementezi variabila e ca si cum ai scoate o paranteza din stiva.

[•drag0s93]

salut ...am o intrebare .imi puteti da si mie testul 2 ca iau 90 si WA pe el.  ...si dc nu ...si un sfat ar fi de folos ....

[•gabor_oliviu1991]

ai un caz particular... citeste bine ce trebuie sa afisezi

[•drag0s93]

aha ....pai cazul cand trb sa afisez -1 il am ....in rest ce poate sa fie ....?    ....metoda e la fel presupun....am si yo un ex :
20
()()))(()))()((())))(
mie imi da:2 (nu sunt sigur ca e bn )
voua cat va da ?
Ms!

[•gabor_oliviu1991]

e corect, 2 e rezultatul... si cam care ar fi cazut ala particular?

[•drag0s93]

e corect, 2 e rezultatul... si cam care ar fi cazut ala particular?

nu cred ca ar mai exista unul  .... atunci cand parantezarea nu este corecta cred ca asta e sg caz particular (eu am zis ca dak n modulo 2 !=0 sa scrie direct -1  )..in rest cred ca algoritmul l e rezolva pe toate ...

[•drag0s93]

srry ... am uitat sa pun un return; si cred ca pe testul 2 era nevoit sa afiseze -1 si la mn  mai afisa si dak parantezarea ar fi fost corecta ....

[•gabor_oliviu1991]

asta vroiam sa zic, ca si eu picam testul 2 ca nu afisam -1. data viitoare fi mai atena

[•f.v.anton]

mie mi se pare ca ar cam fi 3 rezultatul, manual facand nu stiu cum obtineti 2. Ati putea scrie pasii de eliminare? Ca mie imi ramane la sfarsit sirul )))( care se transforma in ())( si apoi in ()() in total 3 operatii...unde gresesc?

[•gabor_oliviu1991]

pe ce exemplu? ca pe exemplul dat de tine asa e, sunt 3 pasi... ())( se elimina primele doua si raman )( la care sunt nevoie de doua intoarceri. deci 3 in total

[•jupanubv92]

Anton vezi ca exemplul dat de Dragos este gresit.

Cod:

20
()()))(()))()((())))(

Daca stai sa numeri parantezele lui o sa vezi ca sunt 21  si n-ul este 20 de aceea ii da lui 2 pentru ca nu ia in considerare ultima paranteza si fara ultima paranteza ai ()()))(()))()((()))) de unde ramane )))) unde intorci prima si a treia paranteza si devine ()() intorcand doua paranteze.

Ce zici tu acolo e bine numai ca din exemplul lui draogs daca ai numara parantezele o sa vezi ca  este 21 de unde trebuie sa afisezi -1 pentru ca nu poate fi niciodata parantezata corect .

[•f.v.anton]

^^ mda acum am observat ca sunt 21, eu le luasem cu copy paste. Anyway nu-i problema, am luat 100 )))

[•CrisstiHD]

fratilor eu innebunesc... dati-mi va rog alte teste inafara de exemplu sa vad daca merge:|

ce e gresit in implementarea asta? la mine in teste merge perfect in borland pascal, dar in free pascal nu afiseaza (acelasi cod). vreau si eu cateva lamuriri...

Cod:

program par;
var s:array[1..3000] of char;
	f1,f2:text;
	n,x,y,i,j:integer;
                 sol:real;


        BEGIN

        assign (f1,'par.in');
        assign (f2,'par.out');
        reset(f1); rewrite(f2);
        readln (f1,n);
        x:=0;y:=0;
        if (n mod 2=1) then write (f2,'-1')
        		else


                        BEGIN

                        	for i:=1 to n do  read (f1,s[i]);
                                for i:=1 to n do
                                	if s[i]='(' then x:=x+1	
                                        	    else y:=y+1;

                                for i:=1 to (n-1) do begin
                                	j:=i+1;
                                        while j<>n do
                                        	if s[j]=')' then j:=n
                                                   	    else j:=j+1;	
	                                if (s[i]='(') and (s[j]=')') then begin
                                        				x:=x-1;
                                                                        y:=y-1;
                                                                        s[j]:='0';
                                        				end;
                                        end;
                        if (x mod 2 = 0) and (y mod 2 = 0)then sol:=(x/2)+(y/2);
                        if (x mod 2 = 1) and (y mod 2 = 1)then sol:=(x-1)/2+(y-1)/2;
                        write (f2,trunc(sol));
                        end;
        close (f1); close(f2);
        end.	

[•jupanubv92]

Vezi daca te ajuta exemplele astea (cu raspunsul de la o sursa de 100 ) :
ex 1

Cod:

100
))))))))))))))))((((((()()()(((())(((((((()))((()))))))))))(((((((())))(()))))((((((((((((((((((((((
raspuns  22

ex 2

Cod:

100
))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))
raspuns 50

ex 3

Cod:

150
(((((((((((((((((((((()()()()()()()()()()())))))))))))))))))))))((((((((((((((((((((((((((((((((((((((((((()))))))))))))))))))))))))))))))))))))))))))
raspuns 0

ex 4

Cod:

5
(())(
raspuns -1

Si sfatul meu este sa incerci sa faci si solutia in O(n) e mult mai simpla si intra si in timp fara probleme

Si tu poti afla mult mai usor parantezele finale , in loc sa faci in n^2 poti sa faci liniar asa :

Cod:

  for(int i=1;i<=n;i++)
        if(c[i]==')')
         {
          if(x!=0)
            x--;
            else y++;
          }
        else x++;

Asa iti afli x-ul si y-ul cel mai usor fara sa te mai complici sa iti stergi din vectorul tau parantezele inchise .

[•BuRN]

stie cineva datele de intrare pentru testul 8 ? obtin 90 puncte , testul 8 imi pica ... daca ar putea sa ma ajute cineva   

[•andrei-alpha]

Ai incercat testele de forum si iti da bine ?
Daca e fa-ti un generator de teste sau descire cum ai facut .. Testele nu sunt publice.