Cod sursa(job #125310)

Utilizator radamiRadu Patulescu radami Data 20 ianuarie 2008 12:31:19
Problema Piese Scor 0
Compilator cpp Status done
Runda preONI 2008, Runda 3, Clasa a 9-a Marime 1.43 kb
#include <stdio.h>
#include <math.h>
#include <stdlib.h>

int n,m,max = 500*500;
int f[501][501],mat[501][501];

int min (int a,int b)
{
	if (a > b)
		return b;
	return a;
}

int gaseste_multiplu (int x1,int y1,int x2,int y2)
{
	int maxim = min (abs(x2-x1) + 1,abs(y2-y1) + 1);
	int st = 0,dr = 9;
	int putere = 5;
	int x = pow(2,putere);
	while (!(x <= maxim && x * 2 > maxim))
		{
			if (x > maxim)
				dr = (st + dr) / 2;
			else
				st = (st + dr) / 2 + 1;
			putere = (st + dr / 2);
			x = pow(2,putere);
		}
	return pow(2,putere);
}

void copy_mat()
{
	for (int i = 1;i <= n; i++)
		for (int j = 1;j <= m; j++)
			f[i][j] = mat[i][j];
	
}

void pune_piese (int x1,int y1,int x2,int y2,int liber,int p)
{
	if (liber == 0)
		{
			if (p < max)
			{
				max = p;
				copy_mat();
				return;
			}
		}
		else
		{
			int z = gaseste_multiplu(x1,y1,x2,y2);
			for (int i = x1;i <= x1+z-1; i++)
				for (int j = y1;j <= y1+z-1; j++)
					mat[i][j] = p;
			if (x1 + z <= m)
				pune_piese(x1+z,y1,x2,y2,liber - z*z,p+1);
			if (y1 + z <= n)
				pune_piese(x1,y1+z,x2,y2,liber - z*z,p+1);
		}
	
	
	
	
}


int main ()
{
	freopen("piese.in","r",stdin);
	freopen("piese.out","w",stdout);
	
	scanf("%d %d",&n,&m);
	
	pune_piese(1,1,n,m,n*m,1);
	
	printf("%d\n",max);
	for (int i = 1;i <= n; i++)
	{
		for (int j = 1;j <= m; j++)
			printf("%d ",f[i][j]);
		printf("\n");
	}
	
	return 0;
}