Mai intai trebuie sa te autentifici.

Cod sursa(job #126035)

Utilizator byndrsnAlina Ene byndrsn Data 21 ianuarie 2008 02:40:22
Problema Piese Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <iostream>
#include <fstream>
#include <cstring>
#define INFI 0x3f3f3f3f

using namespace std;

const int ptwo[] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512};

int M, N;
int din[513][513], kac[513][513], mat[513][513];
bool which[513][513];
ifstream fin;
ofstream fout;

int memo(int m, int n) {
	if (din[m][n] != INFI)
		return din[m][n];

	if (m == 0 || n == 0)
		return (din[m][n] = 0);

	int dx, dy, a, b;

	for (int k = 0; k < 10; ++ k) {
		if (ptwo[k] > m || ptwo[k] > n)
			break;

		dx = m - ptwo[k];
		dy = n - ptwo[k];

		assert(dx >= 0);
		assert(dy >= 0);

		a = 1 + memo(dx, n) + memo(ptwo[k], dy);
		b = 1 + memo(m, dy) + memo(dx, ptwo[k]);

		if (din[m][n] > a) {
			din[m][n] = a;
			kac[m][n] = k;
			which[m][n] = true;
		}

		if (din[m][n] > b) {
			din[m][n] = b;
			kac[m][n] = k;
			which[m][n] = false;
		}
	}

	return din[m][n];
}

int cnt = 0;

void fill(int m, int n, int sx, int sy) {
	if (m == 0 || n == 0)
		return;

	++ cnt;

	int k = kac[m][n];
	int dx = m - ptwo[k];
	int dy = n - ptwo[k];

	for (int i = 0; i < ptwo[k]; ++ i)
		for (int j = 0; j < ptwo[k]; ++ j)
			mat[sx + i][sy + j] = cnt;

	if (which[m][n]) {
		fill(dx, n, sx + ptwo[k], sy);
		fill(ptwo[k], dy, sx, sy + ptwo[k]);
	} else {
		fill(m, dy, sx, sy + ptwo[k]);
		fill(dx, ptwo[k], sx + ptwo[k], sy);
	}
}

int main(void) {
	fin.open("piese.in");
	fout.open("piese.out");

	memset(din, INFI, sizeof(din));

	fin >> M >> N;

	cnt = 0;
	memo(M, N);
	fill(M, N, 0, 0);

	fout << din[M][N] << endl;

	for (int i = 0; i < M; ++ i) {
		for (int j = 0; j < N; ++ j) {
			fout << mat[i][j];

			if (j == N - 1)
				fout << endl;
			else
				fout << " ";
		}
	}

	return 0;
}