Imprimă pagina - 997 1-sir

Titlul: 997 1-sir
Scris de: Adrian Diaconu din Ianuarie 21, 2007, 23:56:03

Aici puteţi discuta despre problema 1-sir (http://infoarena.ro/problema/1-sir).

Titlul: Răspuns: 997 1-sir
Scris de: C.Fabregas din 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 :indifferent:

Titlul: Răspuns: 997 1-sir
Scris de: Paul-Dan Baltescu din 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.

Titlul: Răspuns: 997 1-sir
Scris de: C.Fabregas din Mai 29, 2010, 15:51:25

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

Titlul: Răspuns: 997 1-sir
Scris de: MciprianM din Mai 29, 2010, 15:58:32

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

Titlul: Răspuns: 997 1-sir
Scris de: C.Fabregas din Mai 29, 2010, 16:03:08

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?

Titlul: Răspuns: 997 1-sir
Scris de: Cont Teste din Mai 29, 2010, 17:57:16

Imi puteti da un test mai maricel ? Multumesc

Titlul: Răspuns: 997 1-sir
Scris de: Paul-Dan Baltescu din Mai 29, 2010, 18:16:13

Citat din mesajul lui: C.Fabregas din Mai 29, 2010, 16:03:08

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.

Titlul: Răspuns: 997 1-sir
Scris de: C.Fabregas din Mai 29, 2010, 18:28:59

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)]~~~~

Titlul: Răspuns: 997 1-sir
Scris de: MciprianM din Mai 29, 2010, 19:50:36

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

Titlul: Răspuns: 997 1-sir
Scris de: Paul-Dan Baltescu din 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. :)

Titlul: Răspuns: 997 1-sir
Scris de: Simoiu Robert din Mai 29, 2010, 19:55:06

Nu cred ca aia era problema lui, cred ca si-a dat seama de ea. :thumbup:

[LE] Paul, am facut eu exact solutia lui, cu modulo si nu am avut succes. Se pare totusi ca era o greseala in implementare.

Titlul: Răspuns: 997 1-sir
Scris de: Paul-Dan Baltescu din 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).

Titlul: Răspuns: 997 1-sir
Scris de: Bogdan Costea din 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. :)

infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Adrian Diaconu din Ianuarie 21, 2007, 23:56:03