infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Andrei Grigorean din Februarie 15, 2009, 13:35:25


Titlul: 806 Par
Scris de: Andrei Grigorean din Februarie 15, 2009, 13:35:25
Aici puteti discuta despre problema Par (http://infoarena.ro/problema/par).

Titlul: Răspuns: 806 Par
Scris de: Flavius Anton din Februarie 15, 2009, 15:16:22
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.

Titlul: Răspuns: 806 Par
Scris de: Bogdan-Cristian Tataroiu din Februarie 15, 2009, 15:26:26
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 :)

Titlul: Răspuns: 806 Par
Scris de: Flavius Anton din Februarie 15, 2009, 15:37:50
1 sec

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

Titlul: Răspuns: 806 Par
Scris de: Popescu Marius din Februarie 15, 2009, 17:24:27
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  \:D/ , 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 .

Titlul: Răspuns: 806 Par
Scris de: Airinei Adrian din Februarie 15, 2009, 18:10:51
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.

Titlul: Răspuns: 806 Par
Scris de: Mandu Dragos din Februarie 16, 2009, 23:29:55
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 :P :D ....

Titlul: Răspuns: 806 Par
Scris de: gaboru corupt din Februarie 16, 2009, 23:35:44
ai un caz particular... citeste bine ce trebuie sa afisezi :ok:

Titlul: Răspuns: 806 Par
Scris de: Mandu Dragos din Februarie 16, 2009, 23:45:30
aha ....pai cazul cand trb sa afisez -1 il am ....in rest ce poate sa fie ....?   :-k ....metoda e la fel presupun....am si yo un ex :
20
()()))(()))()((())))(
mie imi da:2 (nu sunt sigur ca e bn :D )
voua cat va da ?
Ms!

Titlul: Răspuns: 806 Par
Scris de: gaboru corupt din Februarie 16, 2009, 23:50:01
e corect, 2 e rezultatul... si cam care ar fi cazut ala particular?

Titlul: Răspuns: 806 Par
Scris de: Mandu Dragos din Februarie 16, 2009, 23:55:04
Citat din mesajul lui: gaboru corupt din Februarie 16, 2009, 23:50:01
e corect, 2 e rezultatul... si cam care ar fi cazut ala particular?
nu cred ca ar mai exista unul  :-k .... 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 ...

Titlul: Răspuns: 806 Par
Scris de: Mandu Dragos din Februarie 16, 2009, 23:58:10
srry ... #-o 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 .... :D

Titlul: Răspuns: 806 Par
Scris de: gaboru corupt din Februarie 17, 2009, 00:02:00
asta vroiam sa zic, ca si eu picam testul 2 ca nu afisam -1. data viitoare fi mai atena :ok:

Titlul: Răspuns: 806 Par
Scris de: Flavius Anton din Februarie 20, 2009, 09:53:34
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?

Titlul: Răspuns: 806 Par
Scris de: gaboru corupt din Februarie 20, 2009, 13:09:43
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

Titlul: Răspuns: 806 Par
Scris de: Popescu Marius din Februarie 20, 2009, 18:18:23
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 .

Titlul: Răspuns: 806 Par
Scris de: Flavius Anton din Februarie 20, 2009, 22:05:52
^^ mda acum am observat ca sunt 21, eu le luasem cu copy paste. Anyway nu-i problema, am luat 100 :))))

Titlul: Răspuns: 806 Par
Scris de: Cristian Holdunu din Martie 01, 2009, 15:30:03
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.


Titlul: Răspuns: 806 Par
Scris de: Popescu Marius din Martie 01, 2009, 23:09:45
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 .

Titlul: Răspuns: 806 Par
Scris de: B Radu din Martie 08, 2009, 12:18:20
stie cineva datele de intrare pentru testul 8 ? obtin 90 puncte , testul 8 imi pica ... daca ar putea sa ma ajute cineva   ](*,)

Titlul: Răspuns: 806 Par
Scris de: Andrei-Bogdan Antonescu din Martie 08, 2009, 12:38:27
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.


Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines