•fluffy
|
|
« : Aprilie 01, 2004, 00:33:41 » |
|
Aici puteţi discuta despre problema Secventa 2.
|
|
|
Memorat
|
|
|
|
•Twister
Strain
Karma: 0
Deconectat
Mesaje: 45
|
|
« Răspunde #1 : Ianuarie 26, 2005, 22:42:05 » |
|
Mircea te rog mult de tot poti sa postezi si tu macar primul test, ma chinui la problema asta si de-mi sar capacele, te rog frumos.
|
|
|
Memorat
|
|
|
|
•domino
|
|
« Răspunde #2 : Ianuarie 26, 2005, 22:59:02 » |
|
Mircea te rog mult de tot poti sa postezi si tu macar primul test, ma chinui la problema asta si de-mi sar capacele, te rog frumos. Input: 13 13 -24468 -3302 -23557 -1899 -4410 -650 -6467 -9733 -16334 -15731 -7225 -2730 -11983
Output:
|
|
|
Memorat
|
|
|
|
•Twister
Strain
Karma: 0
Deconectat
Mesaje: 45
|
|
« Răspunde #3 : Ianuarie 27, 2005, 11:02:56 » |
|
Multumesc frumos, acum stiu ce-am gresit...
|
|
|
Memorat
|
|
|
|
•dany3dx
Strain
Karma: 0
Deconectat
Mesaje: 14
|
|
« Răspunde #4 : Martie 08, 2005, 11:38:30 » |
|
nu reusesc nici cum sa gasesc un algoritm care sa se incadreze in 0.18s!!! Some help... please ... anyone
|
|
|
Memorat
|
|
|
|
•Twister
Strain
Karma: 0
Deconectat
Mesaje: 45
|
|
« Răspunde #5 : Martie 08, 2005, 12:36:33 » |
|
eu am gasit o rezolvare in O(n).; care a mers pe teste... chestia e ca tu parcugi vectorul ca pentru o suma maximala, cu conditia din enunt
|
|
|
Memorat
|
|
|
|
•rss1987
Strain
Karma: -6
Deconectat
Mesaje: 19
|
|
« Răspunde #6 : Martie 09, 2005, 09:35:13 » |
|
eu am gasit o rezolvare in O(n).; care a mers pe teste... chestia e ca tu parcugi vectorul ca pentru o suma maximala, cu conditia din enunt Chiar daca o scoti in O(n) e posibil sa-ti iasa din timp. Poti folosi "vraja marii la malu' marii" adica sa-ti pui un bufer la fisierul de intrare. Cam 1 MB iti este de ajuns sa elimine neplacerile cauzate de o citire greoaie. Functia e "setvbuf", si iti poate folosi la multe probleme in care timpul e critic.
|
|
|
Memorat
|
RSS
|
|
|
•Twister
Strain
Karma: 0
Deconectat
Mesaje: 45
|
|
« Răspunde #7 : Martie 09, 2005, 21:16:35 » |
|
multumesc frumos pentru sfat
|
|
|
Memorat
|
|
|
|
•dany3dx
Strain
Karma: 0
Deconectat
Mesaje: 14
|
|
« Răspunde #8 : Martie 10, 2005, 16:43:03 » |
|
Input: Code: 13 13 -24468 -3302 -23557 -1899 -4410 -650 -6467 -9733 -16334 -15731 -7225 -2730 -11983
Output: Code:
1 13 -128489 interesant ca mie pe testu asta imi da (acasa) 0 0 0 si totusi iau o suta de puncte... nu-s bine alese testele. stiu si pe altii carora nu le-ar merge testele pt care suma maximala ar da negativa...... dati un test cu n>k si cu toate numerele din vector negative si veti avea surprize la reevaluare(daca conteaza pentru cineva)
|
|
|
Memorat
|
|
|
|
•domino
|
|
« Răspunde #9 : Martie 10, 2005, 20:16:08 » |
|
Input: Code: 13 13 -24468 -3302 -23557 -1899 -4410 -650 -6467 -9733 -16334 -15731 -7225 -2730 -11983
Output: Code:
1 13 -128489 interesant ca mie pe testu asta imi da (acasa) 0 0 0 si totusi iau o suta de puncte... nu-s bine alese testele. stiu si pe altii carora nu le-ar merge testele pt care suma maximala ar da negativa...... dati un test cu n>k si cu toate numerele din vector negative si veti avea surprize la reevaluare(daca conteaza pentru cineva) Tu ai intrebat de limita de 0.18s care e la problema "Secventa" nu la "Secventa 2" unde ai postat... testul de mai sus este printre testele de la problema Secventa 2 (cel putin daca nu le-a schimbat nimeni ).. deci, tu pentru ce postezi? Daca e vorba de problema "Secventa", cum banuiesc, voi muta toate post-urile unde trebuie.. si incearca sa nu mai postezi aiurea
|
|
|
Memorat
|
|
|
|
•dany3dx
Strain
Karma: 0
Deconectat
Mesaje: 14
|
|
« Răspunde #10 : Martie 10, 2005, 20:39:53 » |
|
postul cu limita l-am pus unde nu trebe. =; ... sorry dar ce de-al 2-lea e bine pus! Chiar am trimis un algoritm incomplet care totusi a luat 100p
|
|
|
Memorat
|
|
|
|
•Twister
Strain
Karma: 0
Deconectat
Mesaje: 45
|
|
« Răspunde #11 : Martie 10, 2005, 20:45:38 » |
|
Input: Code: 13 13 -24468 -3302 -23557 -1899 -4410 -650 -6467 -9733 -16334 -15731 -7225 -2730 -11983
Output: Code:
1 13 -128489 interesant ca mie pe testu asta imi da (acasa) 0 0 0 si totusi iau o suta de puncte... nu-s bine alese testele. stiu si pe altii carora nu le-ar merge testele pt care suma maximala ar da negativa...... dati un test cu n>k si cu toate numerele din vector negative si veti avea surprize la reevaluare(daca conteaza pentru cineva) Poate ca daca ai pune la cea mai mica suma pe care o consideri -maxlongint nu ti-ar mai da 0 0 0, asa ca alta data sa-ti construiesti un algoritmmai bine facut, [ sau sa te uiti mai bine pe cod], inainte sa postezi pe forum...
|
|
|
Memorat
|
|
|
|
•cavendish
Strain
Karma: 2
Deconectat
Mesaje: 43
|
|
« Răspunde #12 : Martie 10, 2005, 20:48:21 » |
|
dany3dx, foarte bine ca ai gasit un caz particular pt problema. Dar asta nu-nseamna ca nu-s bine alese testele. Poate vor tine cont de postu tau si vor modifica un test, adaugand cazul asta particular. Poate ca nu. Dar in mod sigur nu se va reevalua problema pt toti cei care au trimis solutii la ea [cel putin nu cred ]. cat despre algoritmi "incompleti" care iau 100 pcte. Nu-i asa grav!
|
|
|
Memorat
|
|
|
|
•dany3dx
Strain
Karma: 0
Deconectat
Mesaje: 14
|
|
« Răspunde #13 : Martie 10, 2005, 20:58:02 » |
|
nu incape in numarul de teste care le numesti particulare... dar ai oarecum dreptate.. nu-i asa grav
|
|
|
Memorat
|
|
|
|
•domino
|
|
« Răspunde #14 : Martie 10, 2005, 21:39:33 » |
|
postul cu limita l-am pus unde nu trebe. =; ... sorry dar ce de-al 2-lea e bine pus! Chiar am trimis un algoritm incomplet care totusi a luat 100p Zici ca ai trimis la Secventa 2 sursa care a luat 100p si da 0 0 0 pe testul ala cu 13 13 ? Dubios, fiindca testul ala stiu sigur ca l-am folosit cel putin in concurs, nu tin minte sa fi avut loc vreo modificare a testelor, o sa verific...
|
|
|
Memorat
|
|
|
|
•teplesnescdenutevezi
Strain
Karma: 0
Deconectat
Mesaje: 18
|
|
« Răspunde #15 : Martie 19, 2005, 20:00:18 » |
|
nu este nici o problema cu testul , decat ca este format numai din valori negative iar voi probabil ati initializat maximul cu 0.incercati sa puneti maximul=-1250000000 la inceput.
|
|
|
Memorat
|
|
|
|
•Binary_Fire
Client obisnuit
Karma: 82
Deconectat
Mesaje: 87
|
|
« Răspunde #16 : Ianuarie 13, 2006, 20:47:43 » |
|
Am incercat sa fac si eu problema si iau 70p. si nu stiu unde am gresit. Maximul l-am pus de -1250000001. Vectorul il parcurg in suma maximala,cu conditia din enunt: for (i=k;i<n;i++) { if ( v[i-1] > ( v[i-1] - a[poz] ) ) v[i]=v[i-1]+a[i]; else {v[i]=v[i-1]-a[poz]+a[i]; poz++;poz1=poz;} if (v[i]>max) {max=v[i];poz2=i;pozf1=poz1;} }
v[k-1] are suma primelor k-1 elemente. Care ii problema?
|
|
|
Memorat
|
|
|
|
u-92
Vizitator
|
|
« Răspunde #17 : Ianuarie 13, 2006, 22:27:34 » |
|
nustiu ce sa zic de codul ala mai bine ai spune care e ideea ta de rezolvare
|
|
|
Memorat
|
|
|
|
•Binary_Fire
Client obisnuit
Karma: 82
Deconectat
Mesaje: 87
|
|
« Răspunde #18 : Ianuarie 15, 2006, 18:33:27 » |
|
Suma maxima ia valoarea primelor k-1(k-ul este lungimea minima a secventei) elemente al sirului de numere si o pun in v[k-1]. Acum merg de la k la n. Eu acum consider asa dak suma v[i-1] este mai mica decat v[i-1]-a[poz] adik daca iau din suma elementul din stanga secventei(poz este init cu 0) si voi avea o suma mai mare atunci ma voi scapa de aceste element si voi aduga la v suma v-a[poz]+a si incrementez poz.Acum dak v este mai mare decat suma maxima atunci max=v si actualizez pozitia 1 si pozitia 2 a secventei. Deci ce zici de idee?
|
|
|
Memorat
|
|
|
|
u-92
Vizitator
|
|
« Răspunde #19 : Ianuarie 15, 2006, 19:15:37 » |
|
nustiu ce sa zic.. probabil nu e corect daca nu prinzi toate testele.. eu am facut altfel
|
|
|
Memorat
|
|
|
|
•Binary_Fire
Client obisnuit
Karma: 82
Deconectat
Mesaje: 87
|
|
« Răspunde #20 : Ianuarie 15, 2006, 19:23:16 » |
|
Probabil ca da,nu mi-ai putea da un indiciu mic?
|
|
|
Memorat
|
|
|
|
•dobre
|
|
« Răspunde #21 : Ianuarie 15, 2006, 19:37:03 » |
|
Cred k este pe ideea corecta...Dar mi se pare ca te-ai complicat prea mult...Eu fac suma elementelor de la 1->k, 1->k+1 ,..., 1->n.Memorezi suma maxima si pe ce pozitie a fost, si iti da capatul din dreapta. Dupaceia faci acelas procedeu ca cel de sus numai ca faci sumele de la d->d-k, d->d-k-1, ... d->1. Si ai gasit cele 2 capete. EX: v-sirul de elemnte 8 3 -3 1 -1 3 1 -2 8 -5 poz : 1 2 3 4 5 6 7 8 v : -3 1 -1 3 1 -2 8 -5 sum1 : -3 -2 -3 0 1 -1 7 2 ai suma maxim pe pozitia 7 apoi faci suma de la 7 inspre 1 poz : 1 2 3 4 5 6 7 8 v : -3 1 -1 3 1 -2 8 -5 sum2 : 7 10 9 10 7 6 8 0
ai suma maxima pe pozitiile 2 si 4 Deci ai solutiile 2 7 10 4 7 10Sper k ai inteles
|
|
|
Memorat
|
|
|
|
•Binary_Fire
Client obisnuit
Karma: 82
Deconectat
Mesaje: 87
|
|
« Răspunde #22 : Ianuarie 17, 2006, 22:40:47 » |
|
Thanks! Acum iau 100p pe problema. Totusi is curios la ce teste a picat solutia mea .
|
|
|
Memorat
|
|
|
|
•wefgef
|
|
« Răspunde #23 : Ianuarie 18, 2006, 19:39:32 » |
|
dobre, ptr urmatoarea intrare: cat iti da? rasp corect e 5 6 9. mie mi se pare ca prog tau afiseaza 1 3 6 cred ca ar fi bine sa se faca alte teste si sa se recorecteze problema.
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
•dobre
|
|
« Răspunde #24 : Ianuarie 21, 2006, 14:37:50 » |
|
Sa stii ca ai dreptate ... Dar nu pot sa inteleg cum de am luat 100p pe ea si totusi care ar fi solutia corecta ... Bine ca ai sesizat altfel in concursuri de mai intalneam probleme de genu tot asa le abordam.
|
|
|
Memorat
|
|
|
|
|