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:
/* 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:
#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!