Cod sursa(job #130257)

Utilizator Adriana_SAdriana Sperlea Adriana_S Data 31 ianuarie 2008 18:11:39
Problema Piese Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <stdio.h>

const int N_MAX = 512;

int a[N_MAX][N_MAX], what[N_MAX][N_MAX];

int main()
{
	freopen("piese.in", "r", stdin);
#ifndef _SCREEN_
	freopen("piese.out", "w", stdout);
#endif

	int N, M;
	scanf("%d %d\n", &M, &N);

	int i, j, cate, k;
	for (i = 1; i <= M; i ++) {
		for (j = 1; j <= N; j ++) {

			a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + 1;
			what[i][j] = 1;
			for (k = 2; k <= i && k <= j; k <<= 1) {
				cate = a[i - k][j] + a[i][j - k] - a[i - k][j - k] + 1;
				if (cate < a[i][j]) {
					a[i][j] = cate;
					what[i][j] = k;
				}
			}
		}
	}

	int nrp = 1, l;
	for (i = M; i >= 1; i --) {
		for (j = N; j >= 1; j --) {

			if (what[i][j] > 0) {
			
				for (k = i - what[i][j] + 1; k <= i; k ++) {
					for (l = j - what[i][j] + 1; l <= j; l ++) {
						what[k][l] = -nrp;
					}
				}
				nrp ++;
			}
		}
	}

	printf("%d\n", a[M][N]);
	for (i = 1; i <= M; i ++) {
		for (j = 1; j <= N; j ++) {
			printf("%d ", - what[i][j]);
		}
		printf("\n");
	}

	return 0;
}