Porbleme OLI Bucuresti 2008

[•IronWing]

Salutare! Am participat la Olimpiada locala de informatica din Bucuresti si am obtinut 20 puncte: 10 la prima, 10 la a doua. Totusi am reusit sa ma calific. Sunt in clasa a XI-a. E prima oara cand trec de faza locala si imi e teama de OJI, pt ca problemele de la locala mi s-au parut grele.
Prin amabilitatea domnului profesor de informatica, am reusit sa obtin solutiile propuse de autori pentru probleme. Din pacate, mi se par grele, pt ca nu sunt comentate si nu le inteleg. De exemplu sunt niste locuri in care se folosesc operatii pe biti pe care nu le pricep.
Postez mai jos codul primei probleme Ion si Maria:

Cod:

/* Solutie O(m*2^m)
generam toate submultiimile de muchii si apoi determinam daca au fix k componente conexe
cu ajutorul un cautari in adancime in O(m)
o parcurgere in O(n^2) nu ar fi trebuit sa obtina 100p)
*/

#include<stdio.h>
#include<string.h>
#define maxn 16

long n,m,k,sel[maxn];
long v[maxn][maxn],t[maxn][maxn];

void df(long a,long val)
{
	sel[a] = 1;
	for( long i = 1; i <= v[a][0]; ++i)
	{
		if(sel[v[a][i]] == 0 && (t[a][i] & val) )
			df(v[a][i],val);
		
	}
}


long ver(long val)
{
	long nr = 0;
	memset(sel,0,sizeof(sel));
	
	for( long i = 1; i <= n ;++i)
	{
		if(sel[i] == 0)
		{
			nr++;
			df(i,val);
		}
	}
	return ( nr == k);
	
}

int main()
{
	long sol = 0;
	
	freopen("ion.in","r",stdin);
	freopen("ion.out","w",stdout);
	
	scanf("%ld %ld %ld",&n,&m,&k);
	
	for( long i = 1; i <= m; ++i)
	{
		long a,b;
		scanf("%ld %ld",&a,&b);
		v[a][++v[a][0]] = b;
		t[a][++t[a][0]] = 1<<(i-1);
		v[b][++v[b][0]] = a;
		t[b][++t[b][0]] = 1<<(i-1);
	}
	long max = (1 << m),val = 0;
	while( val != max)
	{
		sol+= ver(val);
		val++;
	}
		
	printf("%ld\n",sol);	
	
	return 0;
}

Si codul problemei a doua, Cuvinte:

Cod:

#include<stdio.h>
#include<string.h>

#define maxn 1001
#define rest 9967

long v[maxn], sol[maxn],n,d;

void mult( long *a,long *b)
{
	long c[maxn];
	memset(c,0,sizeof(c));
	
	for( long i = 0; i < d; ++i)
		for( long j = 0; j < d; ++j)
		{
			long x = i + j;
			if(x>=d) x-=d;
			c[x] = (c[x] + a[i] * b[j])% rest;
		}
	for( long i = 0; i < d; ++i)
	{
		a[i] = c[i];
	}
		
}


int main()
{
	freopen("cuvinte.in","r",stdin);
	freopen("cuvinte.out","w",stdout);
	
	scanf("%ld %ld",&n,&d);
	sol[0] = 1;
	for( long i = 0; i <= 25; ++i)
		v[(i%d)] += 1;
	long nr = 1;
	
	while(n)
	{
		if( n & nr)
		{
			mult(sol,v);
			n-=nr;
		}
		nr*=2;
		mult(v,v);
	}
	
	printf("%ld\n",sol[0]);
	
	
	
	return 0;
}

Poate ma ajutati sa le inteleg si eu va rog. Nu stiu ce face de exemplu o expresie de genul if(a & b)
Dat fiind faptul ca au fost rezultate si de 200 p, ma face sa cred ca sunt foarte slab, si ma simt prost deorece nu am cu cine sa discut. Textele problemelor nu le-am gasit pe internet, din pacate.
Va multumesc pentru ajutor!

[•Florian]

De unde as putea sa iau si eu problemele? Ma intereseaza cele de la a10a in mod special... Dar si celelalte....

[•IronWing]

Eu l-am rugat pe profesorul de informatica sa-mi dea solutiile si el a vorbit cu autorii problemelor. Cat despre probleme, subiectele nu le-am  gasit pe internet din pacate . 

[•peanutz]

a & b -> Transformi in baza 2 a si b, iei bitii comuni si vei avea

01011 &
10111 = 00011

[•Tabara]

Ca sa intelegi operatiile de baza pe biti te poti uita aici.

 

[•IronWing]

Va multumesc pentru sfaturi. Am inteles la ce sunt folosite operatiile pe baza de biti la prima problema.
Sunt folosite pentru a genera toate submultimile unei multimi:
Iata un algoritm pe care l-am facut eu care genereaza submultimile:

Cod:

#include <iostream.h>
#include <conio.h>
int a[300], b[300], n, i, j, m;
void main() {
clrscr();
cout<<"n: "; cin>>n;
for(i=1;i<=n;i++)
{  a[i]=i;
   b[i]=1<<(i-1);
}
m=1<<n;
for(i=0;i<m;i++)
 { for(j=1;j<=n;j++)
    if(i & b[j]) cout<<a[j]<<" ";
   cout<<endl;
 }
cout<<m;
getch();
}

Editat de admin: Poti folosi tag-ul code atunci cand postezi fractiuni de programe

[•pandaemon]

Pentru cine vrea prima cerinta de la OLI 2008 Bucuresti (11-12):

http://www.filebox.ro/download.php?key=f5e1213219e42992333e4f6bd1171233

[•lamez0r]

Daca ar putea cineva sa puna aici problemele de la oli din bucuresti. m-ar interesa cele de clasa a 10 in special. merci si bafta.

L.E: mda...la oli bihor s-au dat exact aceleasi probleme ca la oli bucuresti. daca le-ar fii pus cineva aici..