Word Squared

시간 제한1초메모리 제한512 MB

요약
1부터 n까지의 순열이 주어질 때, 각 행에 왼쪽에서 오른쪽으로, 각 열에 위에서 아래로 이 순열이 연속으로 나타나면서 크기가 가장 작은 정사각 행렬을 만든다.
난이도

보통10점 중 7점

유형
배열, 행렬, 조합론, 구현
정답자
아직 제출이 없습니다

문제

Given a permutation of numbers from 1 to n, find a square matrix conforming to the following rules:

  1. The matrix should include only numbers from the permutation;
  2. The given permutation should occur in every row of the matrix as a contiguous subsequence, read from left to right;
  3. The given permutation should occur in every column of the matrix as a contiguous subsequence, read from top to bottom;
  4. The matrix size is the smallest possible.

입력

The first line of input is a positive integer n ≤ 500.

The second line of input consists of n space-separated integers: the permutation itself.

출력

The first line of output should be an integer m: the size of the matrix. The next m lines should list m consecutive rows of the matrix. Each of these lines should contain m integers separated by spaces: the values in the corresponding row.

The size m should be minimum possible. If there are several possible answers, print any one of them.

힌트

Here is where the permutation occurs in the matrix from the example:

     

예제1

  1. 예제 1

    입력
    2
1 2
    예상 출력
    3
1 2 1
2 1 2
1 2 1