Cod sursa(job #126123)

Utilizator DastasIonescu Vlad Dastas Data 21 ianuarie 2008 14:58:44
Problema Piese Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <iostream>

const int maxn = 501;

FILE *in = fopen("piese.in","r"), *out = fopen("piese.out","w");

int n, m;

int a[maxn][maxn];

int min(int x, int y)
{
    return x < y ? x : y;
}

int getpow(int x)
{
    int res = 1;

    while ( res <= x )
        res <<= 1;

    return res >> 1;
}

int main()
{
    fscanf(in, "%d %d", &n, &m);

    int cr = 1;

    for ( int i = 1; i <= n; ++i )
        for ( int j = 1; j <= m; ++j )
            if ( !a[i][j] )
            {
                // afla patratul maxim de latura putere a lui 2 care poate fi pus cu coltul stanga sus in a[i][j]
                // acesta va avea latura cea mai mica putere a lui 2 <= min(n-i, m-j) + 1;

                int lat = getpow( min(n-i, m-j) + 1 );

                for ( int k = i; k <= i + lat - 1; ++k )
                    for ( int p = j; p <= j + lat - 1; ++p )
                        a[k][p] = cr;

                ++cr;
            }

    fprintf(out, "%d\n", cr-1);
    for ( int i = 1; i <= n; ++i )
    {
        for ( int j = 1; j <= m; ++j )
            fprintf(out, "%d ", a[i][j]);
        fprintf(out, "\n");
    }

	return 0;
}