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

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

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

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

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

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

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

#include "iostream" 
#include "cstring" 

using namespace std;

const int MAX_SIZE = 5;
const int MAX_STK = 60;

typedef unsigned long long ULL;

class CoverInit {
private:
    static int m_size;
    //Number of the stick on the top of the grid [row][col].
    static int m_up[MAX_SIZE][MAX_SIZE];

    static void initUp() {
        for (int i = 0; i < m_size; i++) {
            m_up[i][0] = i * (2 * m_size + 1);
            for (int j = 1; j < m_size; j++) {
                m_up[i][j] = m_up[i][j - 1] + 1;
            }
        }
    }

    static void initSqr(int firstStick, int size, ULL mask, ULL* cover) {
        int gap = 2 * m_size + 1;
        int num = firstStick;//The upper and the lower edges.
        for (int i = 0; i < size; i++) {
            cover[num] |= mask;
            cover[num + size * gap] |= mask;
            num++;
        }
        num = firstStick + m_size;//The left and the right edges.
        for (int i = 0; i < size; i++) {
            cover[num] |= mask;
            cover[num + size] |= mask;
            num += gap;
        }
    }

public:
    static void initCover(int size, ULL* cover, int stkCnt) {
        m_size = size;
        initUp();
        memset(cover, 0, stkCnt * sizeof(ULL));
        ULL mask = 1ULL;
        for (int sqrSize = 1; sqrSize <= m_size; sqrSize++) {
            for (int i = 0; i <= m_size - sqrSize; i++) {
                for (int j = 0; j <= m_size - sqrSize; j++) {
                    int up = m_up[i][j];
                    initSqr(up, sqrSize, mask, cover);
                    mask <<= 1;
                }
            }
        }
    }
};

int CoverInit::m_size;
int CoverInit::m_up[MAX_SIZE][MAX_SIZE];

class Solution {
private:
    ULL m_cover[MAX_STK];
    bool m_stick[MAX_STK];
    ULL m_universal;
    int m_sqrCnt;
    int m_stkCnt;
    int m_minStk;
    ULL m_remainCov[MAX_STK];

    void dfs(char stkCnt, char lastStk, ULL cover) {
        if (cover == m_universal) {
            m_minStk = stkCnt;
        }
        else {
            if (stkCnt < m_minStk
                && (m_remainCov[lastStk + 1] | cover) == m_universal
               ) {
                for (int i = lastStk + 1; i < m_stkCnt; i++) {
                    if ((m_cover[i] | cover) > cover) {
                        dfs(stkCnt + 1, i, cover | m_cover[i]);
                    }
                }
            }
        }
    }

    void init(int size) {
        m_stkCnt = 2 * size * (size + 1);

        CoverInit::initCover(size, m_cover, m_stkCnt);

        int sqrCnt = 0;
        for (int i = 1; i <= size; i++) {
            sqrCnt += i * i;
        }
        m_universal = 1ULL;
        for (int i = 1; i < sqrCnt; i++) {
            m_universal <<= 1;
            m_universal += 1ULL;
        }

        for (int i = 0 ; i < m_stkCnt; i++) {
            m_stick[i] = true;
        }
    }

    void modifyData() {
        for (int i = 0; i < m_stkCnt; i++) {
            if (!m_stick[i]) {
                m_universal &= ~m_cover[i];
            }
        }

        for (int i = 0; i < m_stkCnt; i++) {
            m_cover[i] &= m_universal;
        }
        for (int i = 0; i < m_stkCnt; i++) {
            if (m_stick[i]) {
                for (int j = 0; j < m_stkCnt; j++) {
                    if (j != i && m_stick[j]
                        && m_cover[j] == (m_cover[j] & m_cover[i])
                       ) {
                        m_stick[j] = false;
                    }
                }
            }
        }
        int cnt = 0;
        for (int i = 0; i < m_stkCnt; i++) {
            if (m_stick[i]) {
                m_cover[cnt] = m_cover[i];
                cnt++;
            }
        }
        m_stkCnt = cnt;

        m_remainCov[m_stkCnt - 1] = m_cover[m_stkCnt - 1];
        for (int i = m_stkCnt - 2; i >= 0; i--) {
            m_remainCov[i] = m_remainCov[i + 1] | m_cover[i];
        }
    }

public:
    void input() {
        int size;
        cin >> size;
        init(size);
        
        int rmCnt;
        cin >> rmCnt;
        for (int i = 0; i < rmCnt; i++) {
            int rm;
            cin >> rm;
            m_stick[rm - 1] = false;
        }
    }

    void search() {
        modifyData();
        m_minStk = m_stkCnt < 9? m_stkCnt: 9;
        dfs(0, -1, 0ULL);
        cout << m_minStk << endl;
    }
};

int main() {
    Solution solution;
    int caseCnt;
    cin >> caseCnt;
    for (int i = 0; i < caseCnt; i++) {
        solution.input();
        solution.search();
    }
    return 0;
}