Mai intai trebuie sa te autentifici.
Cod sursa(job #126035)
Utilizator | 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;
}