Отримання знань

   Входные данные

   Выходные данные

   Пример входных данных

   Пример выходных данных

   Анализ условия и обсуждение идеи решения

   Пример решения на C++:

#include "iostream" 
#include "string.h" 
#include "stdlib.h" 
using namespace std;
const int maxn=100;
int ed;
int n,h;
int num;
int size[11];
int dir[2*maxn+1][2*maxn+1],done[2*maxn+1][2*maxn+1];
short ok[maxn][maxn][11];
struct vy{
          int left,right;
         }verge[11];
int com(const void *a,const void *b)
{
  return *(int *)a-*(int *)b;
}
void init()
{
  memset(size,0,sizeof(size));
  memset(dir,0,sizeof(dir));
  memset(done,0,sizeof(done));
  memset(verge,0,sizeof(verge));
  ed=0;  
  cin >> n;
  int t;
  cin >> t;
  num=0;
  int i;
  for (i=1; i <= t; i++)
   {
    int k;
    cin >> k;
    int j;
    for(j=1; j <= num && size[j]!=k; j++);
    if (j > num) {
                num++;
                size[num]=k;
               }
   }
  size[0]=0;
  qsort(size,num+1,sizeof(size[0]),com);
}
void printout()
{
  if (ed) cout << "YES" << endl;
      else cout << "NO" << endl;
}
void chose()
{
  int i,j;
  for (i=1; i <= h; i++)
   {
    for (j=verge[i].left+1; j <= verge[i].right; j++)
     {
      dir[i][j]=-dir[i][j-1];
      done[i][j]=0;
     }
    done[i][verge[i].left]=0;
   }
  for (i=1; i <= h; i++)
   {
    for (j=verge[i].left; j <= verge[i].right; j++)
     {
      int k;
      for (k=1; k <= num; k++)
       {
        if (dir[i][j]==1) {
                           ok[i][j][k]=1;
                           int x=j,y=j;
                           int lm;
                           for (lm=1; lm <= size[k]; lm++)
                            {
                             if (x < verge[i+lm-1].left || y > verge[i+lm-1].right || i+lm-1 > h)
                                 {ok[i][j][k]=0;
                                  break;}
                             x--;
                             y++;
                            }
                          }
        if (dir[i][j]==-1){
                           ok[i][j][k]=1;
                           int x=j,y=j+size[k]*2-2;
                           int lm;
                           for (lm=1; lm <= size[k]; lm++)
                            {
                             if (x < verge[i+lm-1].left || y > verge[i+lm-1].right || i+lm-1 > h)
                                {ok[i][j][k]=0;break;}
                             x++;
                             y--;
                            }
                           }
       }
     }
   }
}
void make_tri()
{
  h=n;
  int i,j;
  for (i=1; i <= h; i++)
   {
    verge[i].left=maxn-i+1;
    verge[i].right=maxn+i-1;
    dir[i][verge[i].left]=1;
   }
  chose();
}
void make_lin()
{
  h=n;
  int i,j;
  for (i=1; i <= h; i++)
   {
    verge[i].left=maxn-n-i+1;
    verge[i].right=maxn+n-i;
    dir[i][verge[i].left]=1;
   }
  chose();
}
void make_ti()
{
  h=n;
  int i,j;
  for (i=1; i <= h; i++)
   {
    verge[i].left=maxn-n-i+1;
    verge[i].right=maxn+n+i-1;
    dir[i][verge[i].left]=1;
   }
  chose();
}
void make_liu()
{
  h=2*n;
  int i,j;
  for (i=1; i <= n; i++)
   {
    verge[i].left=maxn-n-i+1;
    verge[i].right=maxn+n+i-1;
    dir[i][verge[i].left]=1;
   }
  for (i=n+1; i <= h; i++)
   {
    verge[i].left=verge[2*n-i+1].left;
    verge[i].right=verge[2*n-i+1].right;
    dir[i][verge[i].left]=-1;
   }
  chose();
}
void dfs(int x,int y)
{
  if (ed) return;
  if (y > verge[x].right) {
                         if (x >= h) {ed=1;return;}
                         dfs(x+1,verge[x+1].left);
                         return;
                        }
  if (done[x][y]) {dfs(x,y+1);return;}
  int k;
  for (k=1; k <= num; k++)
   {
    if (!ok[x][y][k]) break;
    if (ed) break;
    int bi=size[k],bj=verge[x+size[k]-1].right+1;
    if (dir[x][y]==1)
     {
      int i,j;
      int able=1;
      int l,r;
      l=y;
      r=y;
      for (i=1; i <= size[k]; i++)
       {
        for (j=l; j <= r; j++)
         {
          if (done[i+x-1][j]) {
                           able=0;
                           bi=i;
                           bj=j;
                           break;
                          }
                 else     done[i+x-1][j]=1;         
         }
   if (!able) break;
        l--;
        r++;
       }
      if (able) dfs(x,y+1);
      l=r=y;
      for (i=1; i <= bi; i++)
       {
        for (j=l; j <= r; j++)
         {
          if (i==bi && j==bj) break;
          done[x+i-1][j]=0;
         }
        l--;
        r++;
       }
     }
    else
    {
    int i,j;
    int able=1;
    int l=y,r=y+2*size[k]-2;
    for (i=1; i <= size[k]; i++)
     {
      for (j=l; j <= r; j++)
       {
          if (done[i+x-1][j]) {
                           able=0;
                           bi=i;
                           bj=j;
            break;
                          }
              else        done[i+x-1][j]=1;
       }
      if (!able) break;
      l++;
      r--;
     }
    if (able) dfs(x,y+1);
    l=y;
    r=y+2*size[k]-2;
    for (i=1; i <= bi; i++)
     {
      for (j=l; j <= r; j++)
       {
        if (i==bi && j==bj) break;
        done[i+x-1][j]=0;
       }
      l++;
      r--;
     }
   }
  }
}
void work()
{
  ed=0;
  if (!ed) {
            make_tri();
            dfs(1,verge[1].left);
           }
  if (!ed) {
            make_lin();
            dfs(1,verge[1].left);
           }
  if (!ed) {
            make_ti();
            dfs(1,verge[1].left);
           }
  if (!ed) {
            make_liu();
            dfs(1,verge[1].left);
           }
}
int main()
{
  int cases;
  cin >> cases;
  while (cases--)
   {
    init();
    work();
    printout();
   }
  return 0;
}