997 1-sir

[•DITzoneC]

Aici puteţi discuta despre problema 1-sir.

[•cesc]

Suma S trebuie citita intr-un vector?
-2^31 < S < 2^31
n-as putea calcula cate cifre are 2^31 

[•pauldb]

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.

[•cesc]

Cod:

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

[•MciprianM]

MaxS e prea mic sau N*N e prea mare?

[•cesc]

LE: ceva e ciudat

iata noul cod:

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?

[•cont_de_teste]

Imi puteti da un test mai maricel ? Multumesc

[•pauldb]

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.

[•cesc]

Atunci inseamna ca problema e la recurenta voastra
http://infoarena.ro/preoni-2007/runda-1/solutii
Care 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)]

[•MciprianM]

Mai citeste enuntul: "Rezultatul se afiseaza modulo ..."

[•pauldb]

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.

[•SpiderMan]

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.

[•pauldb]

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).

[•DonJoker]

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.