Cod sursa(job #194030)

Utilizator nusmaibunkeleviprofesor cicalescu nusmaibunkelevi Data 7 iunie 2008 22:10:55
Problema Piese Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include<stdio.h>

#define NMAX 500
struct p2{unsigned int l,a;};

unsigned int min,a[NMAX*NMAX/2];
p2	v[20];
unsigned int b[NMAX][NMAX];

unsigned int cauta(unsigned int x){
unsigned int i=0,px=x*x;
while(px>=v[i].a) ++i;
return i-1;
}

unsigned int minim(unsigned int a,unsigned int b){
return a<=b?a:b;
}
unsigned int maxim(unsigned int a,unsigned int b){
return a>=b?a:b;
}

void umple(unsigned int l,unsigned int c,unsigned int dim){
int i,j;
for(i=l;i<=l+dim;++i)
	for(j=c;j<=c+dim;++j)
		b[i][j]=min;
}

void f(unsigned ll,unsigned cc,unsigned l,unsigned c){
unsigned int d1,d2,d3,d4,i,dim;
d1=minim(ll,cc);
i=cauta(d1);
d2=ll-v[i].l;
//d3=maxim(ll,cc);
d4=cc-v[i].l;
min++;a[min]=v[i].a;
dim=v[i].l;
umple(l,c,dim);
if(d2+d4){
	if(d2) f(d2,v[i].l,l+dim,c);
	if(d4) f(v[i].l,d4,l,c+dim);
	if(d2&&d4) f(d2,d4,l+dim,c+dim);
	}
}

int main(){
freopen("piese.in","r",stdin);
freopen("piese.out","w",stdout);
unsigned int m,n;
scanf("%u%u",&m,&n);
unsigned int i,j;
v[0].l=1;
v[0].a=1;
for(i=1;i<20;++i){
	v[i].l=2*v[i-1].l;
	v[i].a=v[i].l*v[i].l;
	}
f(m,n,0,0);
printf("%u\n",min);
//for(i=1;i<=min;++i) printf("%u ",a[i]);
//printf("\n");
for(i=0;i<m;++i){
	for(j=0;j<n;++j) printf("%d ",b[i][j]);
	printf("\n");
	}
return 0;
}