•DITzoneC
|
|
« : Martie 04, 2007, 14:07:46 » |
|
Aici puteţi discuta despre problema Buline.
|
|
|
Memorat
|
|
|
|
•k_ounu_eddy
|
|
« Răspunde #1 : Martie 04, 2007, 16:02:12 » |
|
Problema asta e asemanatoare cu secventa.Deosebirea e ca nu se da k.
|
|
|
Memorat
|
|
|
|
•bogdan2412
|
|
« Răspunde #2 : Martie 04, 2007, 17:06:14 » |
|
Nu e nevoie de deque-uri aici, spre deosebire de secventa.
|
|
|
Memorat
|
|
|
|
•mocke
Strain
Karma: 0
Deconectat
Mesaje: 19
|
|
« Răspunde #3 : Martie 05, 2007, 23:15:21 » |
|
Ai putea sa faci si deque intradevar (eu asa am facut ). Dublezi sirul, defapt mai adaugi primele N - 1 elemente la coada, faci sume partiale si astfel poti calcula secventa de suma maxima de lungime <= N (care reprezinta si raspunsul problemei).
|
|
|
Memorat
|
oricine greseste...nu oricine invatza
|
|
|
•k_ounu_eddy
|
|
« Răspunde #4 : Martie 06, 2007, 00:49:02 » |
|
Cum adica sume partiale?
|
|
|
Memorat
|
|
|
|
•Tabara
|
|
« Răspunde #5 : Martie 06, 2007, 08:10:58 » |
|
Cum adica sume partiale?
Adica daca ai un sir de valori. sum[i] = sum[i-1] + a[i].
Se calculeaza asa sum[0] = 0; for ( i = 1 i <= n; ++i ) sum[i] = sum[i-1] + a[i];// a retine valorile sirului
( suma valorilor pana la pozitia i inclusiv ).Sumele partiale te ajuta sa afli care e spre exemplu suma intre doua valori [i,j] astfel
|
|
« Ultima modificare: Martie 06, 2007, 08:15:03 de către Tabara Mihai »
|
Memorat
|
|
|
|
•k_ounu_eddy
|
|
« Răspunde #6 : Martie 06, 2007, 09:21:53 » |
|
Si apoi dupa ce calculezi toate sumele,retii maximul si il afisezi nu? Dar mai am o intrebare:conteaza si elemntul de start nu?Adica ar trebui sa incepi cu cel pozitiv,nu?
|
|
|
Memorat
|
|
|
|
•Tabara
|
|
« Răspunde #7 : Martie 06, 2007, 09:33:54 » |
|
Si apoi dupa ce calculezi toate sumele,retii maximul si il afisezi nu?
Si maximul ala ce ar trebui sa reprezinte ? Dar mai am o intrebare:conteaza si elemntul de start nu?Adica ar trebui sa incepi cu cel pozitiv,nu?
Te referi la secventa de suma maxima sau la sumele partiale ?
|
|
|
Memorat
|
|
|
|
•k_ounu_eddy
|
|
« Răspunde #8 : Martie 06, 2007, 10:13:13 » |
|
Pai maximul sumei(nu asta trebuia sa afisezi)? Te referi la secventa de suma maxima sau la sumele partiale ? Ma refer la suma maxima(la problema buline).Nu conteaza elementul de start.Spre exemplu daca ai numerele: -1 2 3 4 5. s[1]=-1,s[2]=1,s[3]=4,s[4]=8,s[5]=13.In cazul asta maximul este 13.Dar daca incepeam cu elementul 2,aveam: s[1]=2,s[2]=5,s[3]=9,s[4]=14.Acum suma este 14,mai mare ca 13(din ex anterior).
|
|
|
Memorat
|
|
|
|
•Tabara
|
|
« Răspunde #9 : Martie 06, 2007, 10:37:24 » |
|
Pai maximul sumei(nu asta trebuia sa afisezi)? Te referi la secventa de suma maxima sau la sumele partiale ? Ma refer la suma maxima(la problema buline).Nu conteaza elementul de start.Spre exemplu daca ai numerele: -1 2 3 4 5. s[1]=-1,s[2]=1,s[3]=4,s[4]=8,s[5]=13.In cazul asta maximul este 13.Dar daca incepeam cu elementul 2,aveam: s[1]=2,s[2]=5,s[3]=9,s[4]=14.Acum suma este 14,mai mare ca 13(din ex anterior). Poi tu zici bine, insa nu cred ca merge faza cu sumele partial pur si simplu calculate si afisat maximul.Trebuie sa calculezi secventa de suma maxima, care poate incepe oriunde in sir. Dar ce spui tu e corect, numai ca nu asta e solutia problemei. Si eu la "buline" lucrez acuma dar nu imi dau seama ce naiba gresesc. Imi da "Suma Gresita" si am facut ca in solutie. Still working on that!
|
|
|
Memorat
|
|
|
|
•k_ounu_eddy
|
|
« Răspunde #10 : Martie 06, 2007, 10:47:38 » |
|
Pai tu cum ai facut Barca Crisitian Mihai?
|
|
|
Memorat
|
|
|
|
•mocke
Strain
Karma: 0
Deconectat
Mesaje: 19
|
|
« Răspunde #11 : Martie 06, 2007, 14:08:15 » |
|
Pei dupa ce am pus in coada primele N - 1 elem si am facut sume partiale...in deque o sa-mi bag suma partiala minima la un pas astfel incat secventa sa nu-mi depaseasca N elemente...si la fiecare pas i aleg si smax = MAX(S[ i ] - St[s1], smax) (unde St este deque-ul meu iar s1 primul pivot, pozitia sumei partiale minime, iar S este vectorul de sume partiale). In ce priveste constructia deque-ului ar trebui sa incerci pe o foaie sa vezi cum sta treaba. Ca sfat ti-as zice sa lucrezi problema Secventa...
|
|
« Ultima modificare: Martie 06, 2007, 14:15:14 de către Barca Cristian Mihai »
|
Memorat
|
oricine greseste...nu oricine invatza
|
|
|
•k_ounu_eddy
|
|
« Răspunde #12 : Martie 06, 2007, 22:06:07 » |
|
Chiar la asta lucram
|
|
|
Memorat
|
|
|
|
•Florian
|
|
« Răspunde #13 : Martie 11, 2007, 20:24:03 » |
|
Am gasit aproximativ aceeasi rezolvare k Barca Cristian Mihai.....da` iau 0 puncte o sa mai incerc:weightlift:
|
|
|
Memorat
|
|
|
|
•raduzer
Client obisnuit
Karma: 62
Deconectat
Mesaje: 71
|
|
« Răspunde #14 : Martie 20, 2007, 16:50:00 » |
|
nu inteleg de ce iau numai 80 de puncte am facut cu sume partiale de la 1 la n (in vectorul s) si inca un vector (t) care are pe pozitia i maximul dintre sumele partiale pana la i, apoi am facut maximul dintre t[i-1]+s[n]-s[i-1] cu i=1,n , dar nu merge decat pe 8 teste
|
|
|
Memorat
|
|
|
|
•gabitzish1
|
|
« Răspunde #15 : Martie 29, 2007, 17:27:49 » |
|
eu iau doar primele 3 teste apoi imi da SIGSEV.. care e problema?? imi explica cineva si mie?
|
|
|
Memorat
|
|
|
|
•marcelcodrea
|
|
« Răspunde #16 : Martie 29, 2007, 17:37:56 » |
|
http://infoarena.ro/documentatie/evaluator11(SIGSEGV): Segmentation fault. Asta in 99% din cazuri inseamna ca ai probleme cu accesul la memorie. Ai iesit din limitele unui vector, ai facut stack overflow, etc.
|
|
|
Memorat
|
|
|
|
•Florian
|
|
« Răspunde #17 : Februarie 09, 2008, 14:19:53 » |
|
nu inteleg de ce iau numai 80 de puncte am facut cu sume partiale de la 1 la n (in vectorul s) si inca un vector (t) care are pe pozitia i maximul dintre sumele partiale pana la i, apoi am facut maximul dintre t[i-1]+s[n]-s[i-1] cu i=1,n , dar nu merge decat pe 8 teste La fel patesc si eu. Iau WA pe testele 8 si 9. Poate cineva sa imi spuna ce as putea gresi? Pe testele mele imi da corect.
|
|
|
Memorat
|
|
|
|
•Mishu91
|
|
« Răspunde #18 : Aprilie 25, 2008, 21:12:56 » |
|
Si eu patesc tot asa LE : Mi-am gasit greseala... acu iau si io 100
|
|
« Ultima modificare: Aprilie 25, 2008, 21:40:30 de către Andrei Misarca »
|
Memorat
|
|
|
|
•Addy.
Strain
Karma: -4
Deconectat
Mesaje: 30
|
|
« Răspunde #19 : Martie 02, 2009, 19:29:22 » |
|
cred ca este o greseala in exemplu, la ordinea in care sunt asezate biletele.. sau nu am inteles eu bine.
|
|
|
Memorat
|
|
|
|
•Florian
|
|
« Răspunde #20 : Martie 02, 2009, 19:33:32 » |
|
Nu ai inteles tu bine. [ Ti-as explica, daca ai spune cum 'intelegi' tu. ]
|
|
|
Memorat
|
|
|
|
•Addy.
Strain
Karma: -4
Deconectat
Mesaje: 30
|
|
« Răspunde #21 : Martie 02, 2009, 20:23:18 » |
|
a, scuze. ma derutase numerotarea de la explicatie, credeam ca reprezinta numarul de buline
|
|
|
Memorat
|
|
|
|
•ssergiuss
Strain
Karma: 41
Deconectat
Mesaje: 24
|
|
« Răspunde #22 : Martie 23, 2009, 20:52:35 » |
|
Exista vreun caz particular? Nu stiu de ce pic testele 8 si 9. Imi da suma gresita. Chiar nu stiu ce am putut gresi . Daca imi poate da cineva vreun test mai dubios i'as fii recunoscator.
|
|
|
Memorat
|
|
|
|
•Florian
|
|
« Răspunde #23 : Martie 23, 2009, 21:18:21 » |
|
Eu picam testele 8 si 9, daca atunci cand faceam subsecventa de suma maxima, in for, puneam "if(a[ i ] <= 0 ) " in loc de " if(sc<=0) ". [ if-ul ala care reseteaza suma curenta, daca aceasta este negativa]. Vezi, poate faci si tu aceeasi greseala.
|
|
|
Memorat
|
|
|
|
•ssergiuss
Strain
Karma: 41
Deconectat
Mesaje: 24
|
|
« Răspunde #24 : Martie 26, 2009, 08:52:47 » |
|
Mersi oricum, dar eu fac cu sume partiale . [later edit] A rezolvat cineva problema calculand secventa de suma minima?
|
|
« Ultima modificare: Martie 27, 2009, 23:15:49 de către Ungur Sergiu Ioan »
|
Memorat
|
|
|
|
|