Cod sursa(job #498086)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 3 noiembrie 2010 23:18:14
Problema Piese Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include<cstdio>
const int N=1<<9;
int nr,n,m,d[N][N],p[N][N],a[N][N];
void read()
{
    freopen("piese.in","r",stdin);
    freopen("piese.out","w",stdout);
    scanf("%d%d",&n,&m);
}
int minim(int x,int y)
{
    return x<y?x:y;
}
void din()
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            int qq;
            if(i==j && j==2)
                qq++;
            int min=1<<20,pmin=0,lat=1;
            for(int k=0;lat<=i && lat<=j;k++)
            {
                int mc=minim(d[i][j-lat]+d[i-lat][lat],d[i-lat][j]+d[lat][j-lat])+1;
                min=minim(mc,min);
                if(min==mc)
                    pmin=lat;
                lat<<=1;
            }
            d[i][j]=min;
            p[i][j]=pmin;
        }
    printf("%d\n",d[n][m]);
}
void reconst(int px,int py,int x,int y,int lat)
{
    if(!lat)
        return;
    ++nr;
    for(int i=px-lat+1;i<=px;i++)
        for(int j=py-lat+1;j<=py;j++)
            a[i][j]=nr;
    if(d[x][y-lat]+d[x-lat][lat]+1==d[x][y])
    {
        reconst(px,py-lat,x,y-lat,p[x][y-lat]);
        reconst(px-lat,py,x-lat,lat,p[x-lat][lat]);
    }
    else
    {
        reconst(px-lat,py,x-lat,y,p[x-lat][y]);
        reconst(px,py-lat,lat,y-lat,p[lat][y-lat]);
    }
}
void afis(int a[N][N])
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
            printf("%d ",a[i][j]);
        printf("\n");
    }
}
int main()
{
    read();
    din();
    reconst(n,m,n,m,p[n][m]);
    afis(a);
    return 0;
}