Cute Matrix
시간 제한1초메모리 제한1024 MB
1부터 N까지를 한 번씩 쓰는 순열 중 길이 3 이상의 등차 부분수열이 없는 배열을 모든 행과 열로 갖는 N×N 행렬이 존재하는지 판별하고 하나를 출력한다.
문제
어떤 양의 정수 에 대해, 다음의 조건을 모두 충족하는 길이 의 배열을 귀여운 배열이라고 하자.
- 이 배열에는 이상 이하의 모든 정수가 정확히 한 번씩 등장한다.
- 이 배열의 모든 길이 이상의 부분 수열은 등차수열이 아니다. 부분 수열의 원소는 이웃하지 않을 수 있다.
그리고, 어떤 크기의 행렬에 대해 모든 행과 열이 귀여운 배열이면 이 행렬을 귀여운 행렬이라고 하자.
이 주어졌을 때 귀여운 행렬이 존재하는지 여부를 판별하고, 존재한다면 그러한 행렬을 아무거나 하나 찾아 출력하시오.
입력
첫 번째 줄에 정수 의 값이 주어진다.
출력
귀여운 행렬이 존재한다면 첫 줄에 1을 출력하고, 그 다음 줄에 걸쳐 귀여운 행렬의 각 행의 개 값을 공백으로 구분하여 출력한다.
귀여운 행렬이 존재하지 않는다면 첫 줄에 0을 출력한다.