Imprimă pagina - Porbleme OLI Bucuresti 2008

Titlul: Porbleme OLI Bucuresti 2008
Scris de: Vlad Paunescu din Februarie 23, 2008, 19:03:01

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!

Titlul: Răspuns: Porbleme OLI Bucuresti 2008
Scris de: Florian Marcu din Februarie 23, 2008, 19:34:27

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

Titlul: Răspuns: Porbleme OLI Bucuresti 2008
Scris de: Vlad Paunescu din Februarie 23, 2008, 19:46:59

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 :(. ](*,)

Titlul: Răspuns: Porbleme OLI Bucuresti 2008
Scris de: Andrei Homorodean din Februarie 23, 2008, 19:55:17

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

01011 &
10111 = 00011

Titlul: Răspuns: Porbleme OLI Bucuresti 2008
Scris de: Tabara Mihai din Februarie 24, 2008, 01:22:25

Ca sa intelegi operatiile de baza pe biti te poti uita aici (http://en.wikipedia.org/wiki/Bit_operators).

:thumbup:

Titlul: Răspuns: Porbleme OLI Bucuresti 2008
Scris de: Vlad Paunescu din Februarie 25, 2008, 15:03:13

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

Titlul: Răspuns: Porbleme OLI Bucuresti 2008
Scris de: Andrei Popescu din Februarie 25, 2008, 18:56:55

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

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

Titlul: Răspuns: Porbleme OLI Bucuresti 2008
Scris de: Bogdan Bondor din Februarie 26, 2008, 22:42:49

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.. ](*,)

infoarena

Comunitate - feedback, proiecte si distractie => Off topic => Subiect creat de: Vlad Paunescu din Februarie 23, 2008, 19:03:01