Building a Symmetric Stair
Time limit3sMemory limit512 MB
Given n unit cubes, build a symmetric stair (Ferrers diagram symmetric across the diagonal) using all n cubes, or report it is impossible.
- Level
Medium5 of 10
- Topics
- Math, Implementation, Combinatorics, Greedy
- Solved
- No attempts yet
Problem
Little Barney just got a new set of toy cubes from his parents. The set contains identical cubes. Barney immediately started building various objects with these cubes.
The latest thing Barney built is a stair. A stair consists of one or more towers of cubes, where the heights of the towers are non-increasing from left to right. In the picture below, you can see three different shapes with 12 cubes each. The first two are stairs and the third one is not a stair.

Barney noticed that for some stairs you can turn your head 90 degrees to the right and you will see the same stair, but reversed! He calls such stairs symmetric. For example, the first stair above is symmetric, but the second one is not. Formally, a stair is symmetric if and only if reflecting the picture over the line gives the same stair, where the -axis is horizontal and oriented to the right, and the -axis is vertical and oriented upwards.

Barney wants to build a symmetric stair using all of his cubes. Show him how to do it!
Input
The single line of the input contains an integer , the number of cubes at Barney's disposal. ()
Output
If there is no symmetric stair with cubes, output a single integer .
Otherwise, in the first line, output one integer , the number of rows and columns in the picture of the stair. () Then output lines describing the stair. Each line must contain exactly characters, each of which is the lowercase English letter ‘o’ or ‘.’. Here ‘o’ describes a cell with a cube, and ‘.’ describes an empty cell. There must be exactly ‘o’ characters in total. The cell in the bottom left corner must contain a cube. If there is more than one solution, output any of them.