Cod sursa(job #1695000)

Utilizator tziplea_stefanTiplea Stefan tziplea_stefan Data 26 aprilie 2016 13:56:51
Problema Piese Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <fstream>
#define VAL 505

using namespace std;

ifstream fin("piese.in");
ofstream fout("piese.out");

int N, M, i, j, K;
int v[VAL][VAL], mn;
bool ok[VAL];

void give_val(int val, int l1, int c1, int l2, int c2)
{
    int i, j;
    for (i=l1; i<=l2; i++)
      for (j=c1; j<=c2; j++)
        v[i][j]=val;
}

void construct(int l1, int c1, int l2, int c2)
{
    if (l1<=l2 && c1<=c2)
    {
        int lm, cm;
        lm=(l1+l2) / 2;
        cm=(c1+c2) / 2;
        if (lm-l1+1==cm-c1+1 && ok[lm-l1+1]==true)
        {
            mn++;
            give_val(mn, l1, c1, lm, cm);
        }
        else
          construct(l1, c1, lm, cm);
        if (lm-l1+1==c2-cm && ok[lm-l1+1]==true)
        {
            mn++;
            give_val(mn, l1, cm+1, lm, c2);
        }
        else
          construct(l1, cm+1, lm, c2);
        if (l2-lm==cm-c1+1 && ok[l2-lm]==true)
        {
            mn++;
            give_val(mn, lm+1, c1, l2, cm);
        }
        else
          construct(lm+1, c1, l2, cm);
        if (l2-lm==c2-cm && ok[l2-lm]==true)
        {
            mn++;
            give_val(mn, lm+1, cm+1, l2, c2);
        }
        else
          construct(lm+1, cm+1, l2, c2);
    }
}

int main()
{
    fin >> N >> M;
    while ((1 << K)<max(N, M))
    {
        ok[(1 << K)]=true;
        K++;
    }
    construct(1, 1, N, M);
    fout << mn << '\n';
    for (i=1; i<=N; i++)
    {
        for (j=1; j<=M; j++)
          fout << v[i][j] << " ";
        fout << '\n';
    }
    fin.close();
    fout.close();
    return 0;
}