Problem setter's tough life P82250


Statement
 

pdf   zip

thehtml

Professor Oak has written another problem for a competition (the OIcat). The statement reads:

“Consider an n × m board with obstacles. We must go from the upper-left cell to the lower-right cell, making horizontal and vertical moves, never leaving the board, and never going through an obstacle…”

Later:

”In the given test cases, both n and m will be between 1 and ‍100, and the number of paths of minimum length will belong to [1, 106]…”

What is required in that problem is irrelevant here. The issue is that now Prof. Oak must create those boards. Can you help him?

Input

Input consists of several cases, each with a natural p between 1 and 106.

Output

For each p, print first a line with n and m (both between 1 and 100), followed by n lines with m characters each: a ‘.’ indicates a free cell, and an ‘X’ indicates an obstacle. The board must have exactly p paths of minumum length. Since, in general, there will be more than one solution, print any of them. Print a line with 10 dashes at the end of each case. Follow strictly the format of the sample output.

Public test cases
  • Input

    1
    1
    3
    12
    7
    11628
    

    Output

    1 1
    .
    ----------
    7 9
    .X.......
    ...XXXXX.
    .X.XXX...
    .X.XXX.XX
    .X...X...
    .X.X...X.
    ...X.XXX.
    ----------
    5 10
    .XX.X...X.
    ......X...
    .XXXX...X.
    .X...XXXX.
    ...X......
    ----------
    2 11
    ...X......X
    X.....X....
    ----------
    6 6
    ......
    .XXX..
    ..XX..
    ..XXX.
    ..XXX.
    ......
    ----------
    6 15
    ...............
    ...............
    ...............
    ...............
    ...............
    ...............
    ----------
    
  • Information
    Author
    Félix Miravé and Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++