Cod sursa(job #349879)

Utilizator Addy.Adrian Draghici Addy. Data 21 septembrie 2009 19:06:17
Problema Piese Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <stdio.h>
#define DIM 502

int S[DIM][DIM],A[DIM][DIM],v[]={0,1,2,4,8,16,32,64,128,256,512};
int n,m,i,j,p,q,k;

int min(int a, int b) {
	return a<b?a:b;
}

int search(int x) {
	int p,u,m,sol;
	p = 1;
	u = 10;
	while (p<=u) {
		m = (u-p)/2+p;
		if (x>=v[m]) {
			sol = m;
			p = m+1;
		}
		else
			u = m-1;
	}
	return v[sol];
}

int main() {
	
	FILE *f = fopen("piese.in","r");
	FILE *g = fopen("piese.out","w");
	
	fscanf(f,"%d%d",&n,&m);
	
	for (i=n; i>=1; i--)
		for (j=m; j>=1; j--)
			S[i][j] = min(min(S[i+1][j],S[i][j+1]),S[i+1][j+1])+1;
	
	for (i=1; i<=n; i++)
		for (j=1; j<=m; j++)
			if (!A[i][j]) {
				k++;
				for (p=i; p<=i+search(S[i][j])-1; p++)
					for (q=j; q<=j+search(S[i][j])-1; q++)
						A[p][q] = k;
			}
	
	fprintf(g,"%d\n",k);
	
	for (i=1; i<=n; i++) {
		for (j=1; j<=m; j++)
			fprintf(g,"%d ",A[i][j]);
		fprintf(g,"\n");
	}
	
	fclose(f);
	fclose(g);

	return 0;
}