ditzone
Vizitator
|
|
« : Martie 30, 2006, 20:24:29 » |
|
Aici puteţi discuta despre problema Subsiruri.
|
|
|
Memorat
|
|
|
|
•lucicanu
Strain
Karma: 0
Deconectat
Mesaje: 5
|
|
« Răspunde #1 : Aprilie 02, 2006, 10:22:13 » |
|
Am si eu o intrebare intrebatoare: ce au testele 8 si 10? Programul merge perfect pe restul testelor, iar la 8 si 10 primesc "incorect sau fisier de iesire lipsa". Sunt convins ca algoritmul e corect, toate variabilele sunt long int, vectorii respecta restrictiile etc. Nu stiu ce sa-i fac... Daca poate cineva sa ma ajute as fi foarte recunoscator...
|
|
|
Memorat
|
|
|
|
•bogdan2412
|
|
« Răspunde #2 : Aprilie 02, 2006, 10:23:39 » |
|
Ai uitat sa faci modulo 9901 pe parcursul programului probabil... Nu ti s-a mai raspuns odata pe forumu vechi?
|
|
|
Memorat
|
|
|
|
nivan
Vizitator
|
|
« Răspunde #3 : Mai 11, 2006, 20:51:32 » |
|
Hmm... cum %&*$%%&^$ : TEST 1 ...[0.01s]... RUN ERROR - Invalid memory reference TEST 2 ...[0.01s]... RUN ERROR - Invalid memory reference TEST 3 ...[0.01s]... RUN ERROR - Invalid memory reference TEST 4 ...[0.01s]... RUN ERROR - Invalid memory reference TEST 5 ...[0.01s]... RUN ERROR - Invalid memory reference TEST 6 ...[0.01s]... RUN ERROR - Invalid memory reference TEST 7 ...[0.01s]... RUN ERROR - Invalid memory reference TEST 8 ...[0.01s]... RUN ERROR - Invalid memory reference TEST 9 ...[0.01s]... RUN ERROR - Invalid memory reference TEST 10 ...[0.01s]... RUN ERROR - Invalid memory reference Cand eu o compilez pe linux si merge! Destul de ciudat.
|
|
|
Memorat
|
|
|
|
u-92
Vizitator
|
|
« Răspunde #4 : Mai 11, 2006, 21:30:13 » |
|
o compilezi.. dar de rulat? baga mai multe teste si daca totul e ok si persista mesajul pune undeva codul sa vedem.. mi s-a mai intamplat si mie sa am ceva constante declarate la inceputul programului si sa nu compileze din cauza asta pe infoarena
|
|
|
Memorat
|
|
|
|
•cos_min
|
|
« Răspunde #5 : Februarie 02, 2008, 18:48:19 » |
|
Acest numar se va afisa modulo 9901. Este restrictie in enuntul pb, nu este o optimizare.
|
|
|
Memorat
|
vid...
|
|
|
•ciprianf
|
|
« Răspunde #6 : Februarie 20, 2008, 08:29:50 » |
|
Sunt incepator si.......nu prea stiu cum sa fac cu problema asta,adica nu stiu cum sa determin subsecventele alea....imi poate explica si mie cineva daca este amabil?
Later Edit: Am aflat ca trebuia facuta cu dinamica, am invatat dinamica, si ma rog, iau pe program doar 80 de pcte , WA la testele 8 si 10.....am vazut ca au mai fost discutii privind aceste 2 teste...este vre-un caz special ?Am pus si %9901
Later later edit: am rezolvat-o pana la urma....eu puneam initial doar la sfarsit %9901, si am corectat punanad peste tot %9901 cand adunam.... erau mai mult de 2 miliarde de posibilitati la un test? ca altfel daca nu iesea din long nu-mi explic de ce ar fi dat WA
|
|
« Ultima modificare: Februarie 21, 2008, 21:41:44 de către Farcasanu Ciprian »
|
Memorat
|
|
|
|
•DITzoneC
|
|
« Răspunde #7 : Februarie 23, 2008, 12:40:22 » |
|
Imagineaza-ti un test de genul Rezultatul pentru acest test este 2 n/2 care depaseste cu mult 2 miliarde.
|
|
|
Memorat
|
|
|
|
•Robytzza
|
|
« Răspunde #8 : Martie 17, 2008, 18:36:03 » |
|
se pot repeta 2 subsiruri?? ca prima oara practic cautam toate posibilitatiile si luam 80 cu 2 TLE si acuma nu le mai formez .. fac ceva in genu c[ i ] = c[j] daca b[ i ]<b[j]+1 si c[ i ]++ daca sunt egale iar numarul de subsiruri maxime le gasesc adunand la fiecare b[ i ] maxim c[ i ] la nr ce e gresit? Editat de admin: Ai grija cand pui chestii de genu [ i ] sa lasi spatii intre i si acolade, deoarce altfel iti face textul italic. oky ms
|
|
« Ultima modificare: Martie 18, 2008, 15:43:00 de către Ionescu Robert Marius »
|
Memorat
|
|
|
|
•DITzoneC
|
|
« Răspunde #9 : Martie 18, 2008, 21:27:39 » |
|
Acolo nu trebuie sa faci c[ i ] ++, trebuie sa ai c[ i ] += c[ j ](in cazul in care sunt egale) deoarece poti sa iei toate subsirurile care se termina in j nu doar unu din ele.
|
|
|
Memorat
|
|
|
|
•Robytzza
|
|
« Răspunde #10 : Martie 18, 2008, 21:53:25 » |
|
|
|
|
Memorat
|
|
|
|
•andrici_cezar
|
|
« Răspunde #11 : Noiembrie 21, 2008, 21:12:19 » |
|
nu inteleg deci incerc sa fac problema dar nu imi gaseste toate subsirurile imi gaseste doar trei cum ar trebuii sa le iau pe toate?
|
|
|
Memorat
|
|
|
|
•pauldb
|
|
« Răspunde #12 : Noiembrie 21, 2008, 23:56:23 » |
|
Foloseste cu incredere punctuatia. E bine sa scrii corect, daca vrei sa fii ajutat.
Daca inteleg eu bine ce intrebi, pentru a rezolva problema ai nevoie de programare dinamica.
|
|
|
Memorat
|
Am zis
|
|
|
•andrici_cezar
|
|
« Răspunde #13 : Noiembrie 22, 2008, 09:22:24 » |
|
bine! o sa o caut si o sa invat acesta cautare dinamica! , dar unde o gasesc?
|
|
|
Memorat
|
|
|
|
•pauldb
|
|
« Răspunde #14 : Noiembrie 22, 2008, 14:26:24 » |
|
Programare dinamica, nu cautare dinamica. Din cate am auzit, un inceput bun ar fi cartea doamnei Cerchez despre programare dinamica. Eu personal am invatat rezolvand cat mai multe probleme de acest gen. Uite un tutorial care s-ar putea sa-ti fie de folos (sau macar sa te lamuresti putin cum sta treaba).
|
|
|
Memorat
|
Am zis
|
|
|
•andrici_cezar
|
|
« Răspunde #15 : Noiembrie 22, 2008, 20:08:28 » |
|
Dami unul in romana ca eu nu prea inteleg engleza
|
|
|
Memorat
|
|
|
|
•cristiprg
Strain
Karma: -2
Deconectat
Mesaje: 23
|
|
« Răspunde #16 : Martie 23, 2009, 15:20:32 » |
|
numarul de subsiruri cum se afla ? un hint, ceva, pls
|
|
|
Memorat
|
|
|
|
•DraStiK
|
|
« Răspunde #17 : Martie 23, 2009, 15:42:51 » |
|
numarul de subsiruri cum se afla ? un hint, ceva, pls e tot programare dinamica: tii un vector v[ i ]=numarul de subsiruri de lungime maxima pana la pozitia i daca nu iti dai seama de relatie dami un pm
|
|
|
Memorat
|
|
|
|
•ssergiuss
Strain
Karma: 41
Deconectat
Mesaje: 24
|
|
« Răspunde #18 : Martie 27, 2009, 11:16:18 » |
|
Pic testele 8 si 9. Rezolv problema cu dinamica, dar nu'mi dau seama ce gresesc. As fii recunoscator celui ce mi'ar da ceva sugestii .
|
|
|
Memorat
|
|
|
|
•ctlin04
|
|
« Răspunde #19 : Iulie 11, 2011, 00:06:25 » |
|
dar care e relatia de recurenta pentru v?
|
|
|
Memorat
|
|
|
|
•maritim
|
|
« Răspunde #20 : Iulie 11, 2011, 11:07:33 » |
|
Presupunem ca Best[ i ] = 7 si descoperi ca Best[ i ] = 7 se poate forma de pe doua pozitii anterioare cu Best[ i ] = 6, dar acestea doua la randul lor se pot forma din 2 si 3 posibilitati si tot asa in continuare prin recurenta. Multa bafta !
|
|
|
Memorat
|
|
|
|
•ctlin04
|
|
« Răspunde #21 : Iulie 11, 2011, 22:38:44 » |
|
ms pentru hint (Lambru Andrei Cristian) aveam cam aceeasi idee numai ca nu mi se primea s-o implimentez, acum insa am mai analizat si pina la urma am luat 100 PS: pentru ce care au probleme cu testul 8 si 10, puneti peste tot unde lucrati cu vectorul in care tineti numarul de subsiruri mod 9901 si totul se primeste pe 100p...
|
|
|
Memorat
|
|
|
|
•ion_caliman
Strain
Karma: 1
Deconectat
Mesaje: 10
|
|
« Răspunde #22 : Iulie 15, 2011, 18:25:12 » |
|
Spuneti-mi va rog cineva ce nu fac corect in algoritmul meu, primesc WA si nu gasesc greseala #include <fstream> using namespace std; ifstream f("subsiruri.in"); ofstream g("subsiruri.out"); int v[2000],n,i,j,best[2000],nr[2000],lmax,num;
int main() { f >> n; for (i=1; i<=n; i++) f >> v[i]; for (i=1; i<=n; i++) { best[i]=1; nr[i]=1; for (j=1; j<i; j++) if (v[j]<v[i] && best[j]+1>best[i]) { best[i]=best[j]+1; if (best[i]>lmax) lmax=best[i]; nr[i]=nr[j]; } else if (v[j]<v[i] && best[j]+1==best[i]) nr[i]=(nr[i]+nr[j])%9901; } for (i=1; i<=n; i++) if (best[i]==lmax) num=(num+nr[i])%9901; g << lmax << '\n' << num; } Pe testele mele mergi bine
|
|
|
Memorat
|
|
|
|
•PlayLikeNeverB4
|
|
« Răspunde #23 : Iulie 15, 2011, 20:47:44 » |
|
Chiar daca ai luat 100, ar fi bine sa initializezi lmax cu 1, in caz ca lungimea maxima e 1.
|
|
|
Memorat
|
|
|
|
•VisuianMihai
|
|
« Răspunde #24 : Noiembrie 30, 2011, 19:57:35 » |
|
nu inteleg... cum imi dau seama daca trebuie %9901? dece tocmai 9901? care e logica?
|
|
|
Memorat
|
|
|
|
|