대칭 계단 만들기

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

요약
큐브 n개가 주어질 때, 대각선에 대해 대칭인 계단 모양(Ferrers diagram)을 정확히 n개로 만들어 출력하거나 불가능하면 -1을 출력한다.
난이도

보통10점 중 5점

유형
수학, 구현, 조합론, 그리디
정답자
아직 제출이 없습니다

문제

어린 바니는 부모님께 정육면체 블록 세트를 새로 받았다. 세트에는 똑같은 정육면체 블록이 nn개 들어 있다. 바니는 곧바로 이 블록들로 여러 가지 물건을 만들기 시작했다.

바니가 가장 최근에 만든 것은 계단이다. 계단은 하나 이상의 탑으로 이루어지며, 탑의 높이는 왼쪽에서 오른쪽으로 갈수록 단조 비증가한다. 아래 그림에는 정육면체 12개로 만든 서로 다른 세 가지 모양이 있다. 처음 두 개는 계단이고, 세 번째는 계단이 아니다.

바니는 어떤 계단은 고개를 오른쪽으로 90도 돌려서 보면 똑같은 계단이 거꾸로 보인다는 것을 알아냈다. 바니는 이런 계단을 대칭이라고 부른다. 예를 들어 위의 첫 번째 계단은 대칭이지만 두 번째 계단은 아니다. 형식적으로, 계단이 대칭이라는 것은 그림을 직선 x=yx = y에 대하여 대칭이동했을 때 같은 계단이 되는 것과 필요충분조건이다. 여기서 xx축은 수평이고 오른쪽을 향하며, yy축은 수직이고 위쪽을 향한다.

바니는 자신이 가진 정육면체 nn개를 모두 사용해서 대칭 계단을 만들고 싶어 한다. 바니에게 만드는 방법을 알려주자!

입력

입력은 한 줄이며, 정수 nn이 주어진다. nn은 바니가 가진 정육면체의 개수이다. (1≤n≤1001 \le n \le 100)

출력

정육면체 nn개로 대칭 계단을 만들 수 없다면 정수 −1-1 하나를 출력한다.

그렇지 않다면 첫째 줄에 계단 그림의 행과 열의 개수 mm을 출력한다. (1≤m≤1001 \le m \le 100) 이어서 계단을 나타내는 mm개의 줄을 출력한다. 각 줄은 정확히 mm개의 문자로 이루어지며, 각 문자는 소문자 영어 알파벳 ‘o’ 또는 ‘.’이다. ‘o’는 정육면체가 있는 칸, ‘.’은 빈 칸을 나타낸다. ‘o’는 모두 합해서 정확히 nn개여야 한다. 왼쪽 아래 모서리 칸에는 정육면체가 있어야 한다. 답이 여러 개라면 그중 아무거나 출력한다.

예제2

  1. 예제 1

    입력
    3
    
    예상 출력
    3
    ...
    o..
    oo.
    
  2. 예제 2

    입력
    17
    
    예상 출력
    5
    o....
    ooo..
    oooo.
    oooo.
    ooooo