•wefgef
|
|
« : Februarie 15, 2009, 13:35:25 » |
|
Aici puteti discuta despre problema Par.
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
•f.v.anton
Strain
Karma: 1
Deconectat
Mesaje: 35
|
|
« Răspunde #1 : 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.
|
|
|
Memorat
|
|
|
|
•bogdan2412
|
|
« Răspunde #2 : 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
|
|
|
Memorat
|
|
|
|
•f.v.anton
Strain
Karma: 1
Deconectat
Mesaje: 35
|
|
« Răspunde #3 : Februarie 15, 2009, 15:37:50 » |
|
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...
|
|
|
Memorat
|
|
|
|
•jupanubv92
Client obisnuit
Karma: 19
Deconectat
Mesaje: 74
|
|
« Răspunde #4 : 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. 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 .
|
|
« Ultima modificare: Februarie 15, 2009, 18:46:12 de către Popescu Marius »
|
Memorat
|
|
|
|
•astronomy
|
|
« Răspunde #5 : 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.
|
|
|
Memorat
|
|
|
|
•drag0s93
Strain
Karma: 0
Deconectat
Mesaje: 14
|
|
« Răspunde #6 : 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 ....
|
|
|
Memorat
|
|
|
|
•gabor_oliviu1991
|
|
« Răspunde #7 : Februarie 16, 2009, 23:35:44 » |
|
ai un caz particular... citeste bine ce trebuie sa afisezi
|
|
|
Memorat
|
|
|
|
•drag0s93
Strain
Karma: 0
Deconectat
Mesaje: 14
|
|
« Răspunde #8 : Februarie 16, 2009, 23:45:30 » |
|
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!
|
|
|
Memorat
|
|
|
|
•gabor_oliviu1991
|
|
« Răspunde #9 : Februarie 16, 2009, 23:50:01 » |
|
e corect, 2 e rezultatul... si cam care ar fi cazut ala particular?
|
|
|
Memorat
|
|
|
|
•drag0s93
Strain
Karma: 0
Deconectat
Mesaje: 14
|
|
« Răspunde #10 : Februarie 16, 2009, 23:55:04 » |
|
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 ...
|
|
|
Memorat
|
|
|
|
•drag0s93
Strain
Karma: 0
Deconectat
Mesaje: 14
|
|
« Răspunde #11 : Februarie 16, 2009, 23:58:10 » |
|
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 ....
|
|
|
Memorat
|
|
|
|
•gabor_oliviu1991
|
|
« Răspunde #12 : 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
|
|
|
Memorat
|
|
|
|
•f.v.anton
Strain
Karma: 1
Deconectat
Mesaje: 35
|
|
« Răspunde #13 : 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?
|
|
|
Memorat
|
|
|
|
•gabor_oliviu1991
|
|
« Răspunde #14 : 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
|
|
« Ultima modificare: Februarie 20, 2009, 13:42:27 de către gaboru corupt »
|
Memorat
|
|
|
|
•jupanubv92
Client obisnuit
Karma: 19
Deconectat
Mesaje: 74
|
|
« Răspunde #15 : Februarie 20, 2009, 18:18:23 » |
|
Anton vezi ca exemplul dat de Dragos este gresit. 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 .
|
|
« Ultima modificare: Februarie 20, 2009, 18:44:20 de către Popescu Marius »
|
Memorat
|
|
|
|
•f.v.anton
Strain
Karma: 1
Deconectat
Mesaje: 35
|
|
« Răspunde #16 : 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 )))
|
|
|
Memorat
|
|
|
|
•CrisstiHD
Strain
Karma: 0
Deconectat
Mesaje: 1
|
|
« Răspunde #17 : 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... 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.
|
|
« Ultima modificare: Martie 01, 2009, 15:37:22 de către Cristian Holdunu »
|
Memorat
|
|
|
|
•jupanubv92
Client obisnuit
Karma: 19
Deconectat
Mesaje: 74
|
|
« Răspunde #18 : Martie 01, 2009, 23:09:45 » |
|
Vezi daca te ajuta exemplele astea (cu raspunsul de la o sursa de 100 ) : ex 1 100 ))))))))))))))))((((((()()()(((())(((((((()))((()))))))))))(((((((())))(()))))(((((((((((((((((((((( raspuns 22
ex 2 100 )))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))) raspuns 50
ex 3 150 (((((((((((((((((((((()()()()()()()()()()())))))))))))))))))))))((((((((((((((((((((((((((((((((((((((((((())))))))))))))))))))))))))))))))))))))))))) raspuns 0
ex 4 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 : 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 .
|
|
« Ultima modificare: Martie 01, 2009, 23:35:11 de către Popescu Marius »
|
Memorat
|
|
|
|
•BuRN
Strain
Karma: 0
Deconectat
Mesaje: 2
|
|
« Răspunde #19 : 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
|
|
|
Memorat
|
|
|
|
•andrei-alpha
Client obisnuit
Karma: 103
Deconectat
Mesaje: 91
|
|
« Răspunde #20 : 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.
|
|
|
Memorat
|
|
|
|
|