•DITzoneC
|
|
« : Ianuarie 21, 2007, 23:56:03 » |
|
Aici puteţi discuta despre problema 1-sir.
|
|
« Ultima modificare: Ianuarie 30, 2007, 20:49:32 de către Crestez Dan-Leonard »
|
Memorat
|
|
|
|
•cesc
Strain
Karma: -1
Deconectat
Mesaje: 10
|
|
« Răspunde #1 : Mai 29, 2010, 14:47:27 » |
|
Suma S trebuie citita intr-un vector? -2^31 < S < 2^31 n-as putea calcula cate cifre are 2^31
|
|
|
Memorat
|
|
|
|
•pauldb
|
|
« Răspunde #2 : Mai 29, 2010, 15:27:56 » |
|
Nu trebuie. Poti folosi calculatorul din dotarea sistemului de operare in situatii limita ca acestea.
Sunt onorat sa vad ca tot mai multi fotbalisti celebri apreciaza site-ul nostru.
|
|
|
Memorat
|
Am zis
|
|
|
•cesc
Strain
Karma: -1
Deconectat
Mesaje: 10
|
|
« Răspunde #3 : Mai 29, 2010, 15:51:25 » |
|
int N, S, D[max_N][max_S], i, j, k;
int main() { fin >> N >> S; D[0][0] = 1; for(i = 1; i <= N; i ++) { for(j = 0; j <= N*N; j ++) D[1][j] = D[0][j - i + 1] + D[0][j + i - 1]; for(k = 0; k <= N*N ; k ++) { D[0][k] = D[1][k]; D[1][k] = 0; } } fout << D[0][S]; return 0; }
ce ar putea fi gresit in rezolvarea asta? help me please
|
|
|
Memorat
|
|
|
|
•MciprianM
|
|
« Răspunde #4 : Mai 29, 2010, 15:58:32 » |
|
MaxS e prea mic sau N*N e prea mare?
|
|
« Ultima modificare: Mai 29, 2010, 16:45:22 de către Marginean Ciprian »
|
Memorat
|
|
|
|
•cesc
Strain
Karma: -1
Deconectat
Mesaje: 10
|
|
« Răspunde #5 : Mai 29, 2010, 16:03:08 » |
|
LE: ceva e ciudat iata noul cod: #include<iostream> #include<fstream> #define max_N 2 #define max_S 32640
using namespace std;
ifstream fin("1-sir.in"); ofstream fout("1-sir.out");
int N, S, D[max_N][max_S], i, j, k;
int main() { fin >> N >> S; D[0][0] = 1; for(i = 1; i <= N - 1; i ++) { for(j = 0; j <= N*(N-1)/2; j ++) D[1][j] = D[0][j + (i - 1)] + D[0][j - (i - 1)]; for(k = 0; k <= N*(N-1)/2 ; k ++) { D[0][k] = D[1][k]; D[1][k] = 0; } } fout << D[0][S]; return 0; }
Care e greseala la for`uri? IMI RASPUNDE SI MIE CINEVA? DINTRE ATATIA OLIMPICI BRILIANTI NU STIE NIMENI ? POATE CINEVA SA PREZINTE ALGORITMUL IN PSEUDOCOD MULTUMESC Nu posta consecutiv. Editeaza mesajele anterioare! Nu mai folosi caps lock in exces! eu folosesc aceeasi recurenta.. imi explica si mie cineva cum imi dau seama cum aranjez for`urile la dinamici in general?
|
|
« Ultima modificare: Mai 29, 2010, 18:15:58 de către C.Fabregas »
|
Memorat
|
|
|
|
•cont_de_teste
Strain
Karma: 1
Deconectat
Mesaje: 7
|
|
« Răspunde #6 : Mai 29, 2010, 17:57:16 » |
|
Imi puteti da un test mai maricel ? Multumesc
|
|
|
Memorat
|
|
|
|
•pauldb
|
|
« Răspunde #7 : Mai 29, 2010, 18:16:13 » |
|
IMI RASPUNDE SI MIE CINEVA? DINTRE ATATIA OLIMPICI BRILIANTI NU STIE NIMENI ? POATE CINEVA SA PREZINTE ALGORITMUL IN PSEUDOCOD MULTUMESC
Controleaza-ti limbajul. Nu o sa te ajute nimeni daca vorbesti asa. In plus, olimpicii brilianti mai fac si altceva decat sa stea pe forumul acesta toata ziua si sa-i ajute pe cei care nu se descurca sa faca probleme. Edit: For-urile la dinamici se pun in asa fel incat toate starile pe care le folosesti in recurenta sa fie deja calculate. In plus, la tine problema pare sa fie urmatoarea: la fiecare pas i pare ca presupui ca elementul curent din sir e i-1, dar nu e obligatoriu sa fie asa.
|
|
« Ultima modificare: Mai 29, 2010, 18:21:43 de către Paul-Dan Baltescu »
|
Memorat
|
Am zis
|
|
|
•cesc
Strain
Karma: -1
Deconectat
Mesaje: 10
|
|
« Răspunde #8 : Mai 29, 2010, 18:28:59 » |
|
Atunci inseamna ca problema e la recurenta voastra http://infoarena.ro/preoni-2007/runda-1/solutiiCare mie mi se pare buna, sau la implementarea mea? Dl. Baltescu puteti scrie dumneavoastra o implementare in pseudocod aici... sau ideea multumesc Daca notam cu D[N] numarul de 1 - siruri cu N termeni care au suma elementelor S, atunci se observa ca D[N] = D[N-1][S-(N-1)] + D[N-1][S+(N-1)]
|
|
« Ultima modificare: Mai 29, 2010, 18:46:53 de către C.Fabregas »
|
Memorat
|
|
|
|
•MciprianM
|
|
« Răspunde #9 : Mai 29, 2010, 19:50:36 » |
|
Mai citeste enuntul: "Rezultatul se afiseaza modulo ..."
|
|
|
Memorat
|
|
|
|
•pauldb
|
|
« Răspunde #10 : Mai 29, 2010, 19:54:21 » |
|
Nu citisem articolul cu solutii. E posibil sa fie corect ce faci tu, eu am rezolvat problema gandind oarecum diferit. O greseala de implementare pe care am vazut-o acum este ca tu nu calculezi rezultatul modulo 194767, asa cum este cerut. Edit: Se pare ca mi-a luat-o Ciprian pe dinainte.
|
|
|
Memorat
|
Am zis
|
|
|
•SpiderMan
|
|
« Răspunde #11 : Mai 29, 2010, 19:55:06 » |
|
Nu cred ca aia era problema lui, cred ca si-a dat seama de ea. [LE] Paul, am facut eu exact solutia lui, cu modulo si nu am avut succes. Se pare totusi ca era o greseala in implementare.
|
|
|
Memorat
|
|
|
|
•pauldb
|
|
« Răspunde #12 : Mai 29, 2010, 20:10:52 » |
|
Ma rog, eu am gandit problema astfel:
Suma maxima pe care o putem obtine dintr-un astfel de sir este N*(N-1) / 2. Cum noi vrem sa obtinem de fapt suma S, trebuie sa vedem in cate moduri putem produce modificari asupra sirului 0 1 2 3 ... N-1, astfel incat sirul obtinut sa aiba suma N*(N-1)/2 - S. Pentru acest sir suma diferentelor S[ i ] - S[ i - 1] = 1. Putem observa ca daca modificam termenul N din sir astfel incat S[ N ] - S[ N-1 ] = -1, atunci suma totala scade cu 2, daca modificam termenul N-1 astfel incat S[ N-1 ] - S[ N-2 ] = -1, atunci suma totala scade cu 4, ..., iar pe cazul general daca modificam termenul i astfel incat S[ i ] - S[ i-1 ] = -1 atunci suma totala scade cu 2*(N-i+1). Asadar, acum putem presupune ca avem valorile 2, 4, 6, ... 2*N si vrem sa vedem in cate moduri putem obtine suma S. Aceasta este o problema de programare dinamica clasica (problema ghiozdanului) si se reduce la a calcula C[ i ][ j ] = in cate moduri putem obtine suma j din primele i valori (2, 4, ... 2*i).
|
|
|
Memorat
|
Am zis
|
|
|
•DonJoker
Strain
Karma: 0
Deconectat
Mesaje: 1
|
|
« Răspunde #13 : Decembrie 02, 2014, 10:43:13 » |
|
Salut! Eu nu inteleg de ce este acesta relatia de recurenta: - in solutia oficiala din relatia de recurenta data eu inteleg ca se cauta numarul de siruri de N - 1 termeni cu sumele termenilor S-(N-1) sau S+(N-1) pentru a afla numarul de siruri formate din N elemente care sa aiba suma elementelor S. Eu din asta inteleg ca ultimul termen al unui astfel de sir este presupus a fi -(N-1) sau +(N-1), ceea ce nu e corect (putem avea si sirul 0-1-0, in care al 3-lea element e diferit de 2). Corectati-ma daca gresesc. Va rog sa ma lamuriti si pe mine.
|
|
|
Memorat
|
|
|
|
|