Cod sursa(job #243916)

Utilizator MariusMarius Stroe Marius Data 14 ianuarie 2009 11:18:42
Problema Piese Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

const char iname[] = "piese.in";
const char oname[] = "piese.out";

#define MAXN  505
#define FOR(i, a, b)  for (int i = (a); i < (b); ++ i)

int put[MAXN], Tabla[MAXN][MAXN];

void f(int x1, int y1, int x2, int y2, int& cntr)
{
    if (! (x1 <= x2 && y1 <= y2))  return ;
    int k = min(put[x2-x1+1], put[y2-y1+1]);
    cntr ++;
    FOR (i, x1, x1 + (1 << k)) FOR (j, y1, y1 + (1 << k))
        Tabla[i][j] = cntr;
    f(x1, y1 + (1 << k), x1 + (1 << k) - 1, y2, cntr);
    f(x1 + (1 << k), y1, x2, y2, cntr);
}

int main(void)
{
    ifstream in(iname);
    ofstream out(oname);
    int M, N;

    in >> M >> N;
    for (int i = 1; (1 << i) < MAXN; ++ i)
        put[1 << i] = i;
    for (int i = 3; i < MAXN; ++ i)
        if (put[i] == 0)  put[i] = put[i - 1];

    int res = 0;
    f(1, 1, M, N, res);
    out << res << "\n";
    FOR (i, 1, M + 1) {
        FOR (j, 1, N + 1)  out << Tabla[i][j] <<" ";
        out << "\n";
    }

    in.close(), out.close();
    return 0;
}