017 Combinari

[•dornescuvlad]

Eu am rulat sursa ta, si arata cum trebuie, probabil ai modificat ceva si ai uitat sa compilezi sau ... nu stiu 

nu mai tot repeta ba ce zic altii, se numeste POST HUNTING si se sanctioneaza cu ban

[•blasterz]

Permutarile sunt diferite de combinari, deci nu prea le poti gasi cu next_permutation si prev_permutation.

Se poate folosind next_permutation !

uite sursa :

http://infoarena.ro/job_detail/444889?action=view-source

[•andunhill]

Cred ca stiu de ce imi afiseaza asa. Eu mai am o problema cu back cu permutari si cred ca asta e cauza deoarece mie la back la permutari imi afiseaza ceva in genu. Dar nu sunt sigur.

[•barneystinson]

Permutarile sunt diferite de combinari, deci nu prea le poti gasi cu next_permutation si prev_permutation.

Se poate folosind next_permutation !

uite sursa :

http://infoarena.ro/job_detail/444889?action=view-source

salut, ms pt info, chiar nu ii dadeam de cap...

insa nu am inteles chiar tot.

pt exemplu n=4 k=3:

programu tau face asa:

un vector 0 0 0 1 ( i1=1,i2=2,i3=3,i4=4 nu am pus si primu 0 de indice 0 ca sa fie usor de vazut)
si face asa

0 0 0 1 printeaza de la 1 la 4 indicele termenului care nu e 0 aici fiind 1 2 3
0 0 1 0 printeaza 1 2 4
0 1 0 0 printeaza 1 3 4
1 0 0 0 iar aici am problema pt ca eu anticipam sa schimbe intre ei cei 2 de 0 din coada, desi ar fi fost o permutare identica ca a 3a si ar fi printat tot 1 3 4... de ce sare peste ea? stiu ca da rezultatul corect dar de ce face asa si cum? e prea tare next_permutation

[•ionutz32]

next_permutation tine cont doar de vectorul dat ca parametru, nu de a cata oara a fost apelat. Daca pentru sirul {0,1,0,0} nu ar schimba nimic pe motiv ca se interschimba 0-urile, programul ar intra in ciclu infinit pentru ca vectorul ar ramane mereu neschimbat.

next_permutation genereaza urmatoarea permutare distincta.

[•wefgef]

http://wordaligned.org/articles/next-permutation

Poti vedea cum e implementata functia in C++.

[•barneystinson]

ms frumos, nu prea stiam eu ce sunt permutarile. am cautat si acum inteleg. ms din nou

[•judgment7]

mda, deci dupa 2-3 ani, mai da cineva un comment aici, tineti minte "\n" face diferenta, e mai eficient decat endl se pare, pentru ca luam 80 puncte cu endl si 100 cu "\n"...mda

[•SpiderMan]

Da, dupa cum poti vedea explicat aici.

[•noobakaflo]

Am vazut ca nu s-a mai raspuns de 120 de zile ,dar am zis sa incerc..
Problema o rezolvai altfel,dar ma intreb de ce pentru sursa urmatoare iau 0 puncte.Am consultat atasamentele si,pentru cel putin primele 2 teste rezultatul e corect. Ce gresesc ? Fac aranjamente,singura diferenta e in functia valid().

Cod:

 
#include<fstream>
using namespace std;
fstream f("combinari.in",ios::in);
fstream g("combinari.out",ios::out);
int n,p,st[100];


void tipar()
{
	int i;
	for(i=0; i<p; i++)
		g<<st[i]<<" ";
	g<<"\n";
}

void init(int k)
{
	st[k]=0;
}

int succesor(int k)
{
	if(st[k]<n)
	{
		st[k]++;
		return 1;
	}
	else
		return 0;
}

int valid(int k)
{
	if(k>0)
        if(st[k-1]>st[k])
			return 0;
		
	return 1;
}

void back(int k)
{
	if(k==n)
		tipar();
	else
	{
		init(k);
		while(succesor(k))
			if(valid(k))
				back(k+1);
	}
}

int main()
{
	f>>n>>p;
	back(0);
	
	f.close(); g.close();
	return 0;
}

[•soriyn]

Cred ca problema ta este unde verificarea aia daca k==n. Gandeste-te ca atunci cand vor fi egale o sa afisezi fara sa mai generezi elementul de pe ultima pozitie. Incearca ceva de genu

Cod:

if(valid(k))
   if(k==n) tipar();
   else back(k+1);

[•noobakaflo]

^
Elementele vor fi de la 0 la n-1 in stiva,pornesc cu back(0),deci nu cred ca e de aici... Repet,la mine afiseaza ce trebuie... 

[•VisuianMihai]

Backul e cel mai bun? Nu e mai buna o combinatorica cu recurenta c[i ][j] = c[i-1][j] + c[i-1][j-1];
c[i ][j] = numarul de combinari i luate cate j
Pardon... ma refeream la numarul de combinari ...

[•superman_01]

O problema destul de interesanta care se bazeaza pe combinari este Pluricex.

[•metalkitten]

pentru un n=50, cam cat ar trebui sa fie timpul maxim de executie? sunt cam off-topic, dar am o tema care se bazeaza pe asta si n-ul maxim e 50...

[•harababurel]

In cel mai rau caz, ai de generat C(50, 25) = 126.410.606.437.752 configuratii (de ordinul 10¹⁴).
Pentru C(50, 7) = 99.884.400 ~= 100 de milioane de configuratii, procesorul meu are nevoie de 2.7 secunde, excluzand tiparirea (cu tiparire, mi se executa in 91 s).
Presupunand ca timpul de executie creste liniar in functie de numarul de operatii (nu-i chiar asa), ar trebui o limita de 3.417.036 secunde ~= 40 de zile.

[•metalkitten]

multumesc  vad eu ce fac