24014번 - Word Search 서브태스크스페셜 저지다국어채점 준비 중

In honor of Google I/O 2017, we would like to make an I/O-themed word search grid. This will be a rectangular grid in which every cell contains one of the three characters I, /, or O. The people solving our word search will look for all instances of the string I/O that appear contiguously forwards or backwards in a row, column, or diagonal. For example, the following grid contains eight instances of I/O, representing all eight possible directions in which the string can appear:

OOOOO
O///O
O/I/O
O///O
OOOOO

To control the difficulty level of our word search, we would like the string to appear exactly N times in the grid. Moreover, we do not want the grid to be too large; it cannot have more than D rows or more than D columns.

Can you help us design a grid that meets these specifications?

The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of one line with two integers D and N, as described above.

For each test case, first output one line containing Case #x:. Then output R lines of exactly C characters each, representing the rectangular grid. Each of those characters must be either I, /, or O. You may choose any values of R and C as long as both are at least 1 and neither exceeds D. Your grid must contain exactly N instances of the string I/O, per the rules described in the statement.

If there are multiple valid answers, you may output any of them.

• 0 ≤ N ≤ 287.
• It is guaranteed that at least one valid grid exists for each test case.

• 1 ≤ T ≤ 25.
• D = 50.

• 1 ≤ T ≤ 100.
• D = 15.

The sample output displays one set of answers to the sample cases. Other answers may be possible. Note that these cases would only appear in the Small dataset.