Cod sursa(job #125721)

Utilizator ZeusCatalin Tiseanu Zeus Data 20 ianuarie 2008 17:00:25
Problema Piese Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.14 kb

#include <cstdio>

int dp[511][511], id;
short U[511][511];
char type[511][511];

void rec( int x, int y, int offX, int offY )
{
    if( x == 0 || y == 0 )
        return;
        
    ++id;
    
    printf("%d %d -> %d\n", x, y, U[x][y] );
    
    for( int i = x + offX - 1; i >= x + offX - U[x][y]; i-- )
         for( int j = y + offY - 1; j >= y + offY - U[x][y]; j-- )
              dp[i][j] = id;
              
    if( type[x][y] == 'L' )
         rec( x, y - U[x][y], offX, offY ),
         rec( x - U[x][y], U[x][y], offX, offY + ( y - U[x][y] ) );
         
    if( type[x][y] == 'U' )
         rec( U[x][y], y - U[x][y], offX + ( x - U[x][y] ), offY ),
         rec( x - U[x][y], y, offX, offY );      
}

int main()
{
    freopen("piese.in", "r", stdin);
    freopen("piese.out", "w", stdout);
    
    int N, M;
    
    scanf("%d %d", &N, &M);
    
    for( int i = 1; i <= N; i++ )
         for( int j = 1; j <= M; j++ )
              dp[i][j] = i * j,
              U[i][j] = 1,
              type[i][j] = 'L';
    
    for( int at = 2; at <= ( N <? M ); at *= 2 )
         for( int i = 1; i <= N; i++ ) if( at <= i )
              for( int j = 1; j <= M; j++ ) if( at <= j )
              {
                   if ( 1+dp[i][j-at]+dp[i-at][at] < dp[i][j] )
                   {
                       dp[i][j] = 1+dp[i][j-at]+dp[i-at][at];     
                       
                       U[i][j] = at;
                       type[i][j] = 'L'; 
                   }
                   
                   if (1+dp[at][j-at] + dp[i-at][j] < dp[i][j] )
                   {
                       dp[i][j] = 1+dp[at][j-at]+dp[i-at][j];               
                       
                       U[i][j] = at;
                       type[i][j] = 'U';
                   }
                   
              }
    
    printf("%d\n", dp[N][M] );          
    rec( N, M, 1, 1 );
    
    for( int i = 1; i <= N; i++ )
    {
         printf("%d", dp[i][1] );
         for( int j = 2; j <= M; j++ )
              printf(" %d", dp[i][j] );
         printf("\n");
    }
    
    
    return 0;    
}