Connection Status:
Competition Arena > EncloseArea

EncloseArea

SRM 776 · 2020-01-23 · by misof

SRM 776 · 2020-01-23 · by misof · Simple Math, String Manipulation
Class Name: EncloseArea
Return Type: String[]
Method Name: enclose
Arg Types: (int)
Problem Statement

Problem Statement

You can order a custom rectangular chessboard. Both the number of rows and the number of columns must be between 1 and 50, inclusive.

You have a sufficient supply of walls. Each wall exactly fits onto a diagonal of a cell of the chessboard. Your task is to place some of these walls onto some of the diagonals of your chessboard cells in such a way that:

  • The walls form a single continuous boundary of a region of the chessboard.
  • The area of that region is exactly A.

Return a String[] containing any valid solution. Use the character '.' for empty cells and '/' and '\' for cells that contain walls. Any valid solution will be accepted. If there is no solution, return an empty String[] instead.

Notes

  • The boundary of the region enclosed by the walls must not touch or intersect itself, and it may not branch anywhere. In other words, each endpoint of each wall must touch exactly one other wall, and there must be just one connected component of walls.
  • The returned String[] must describe a rectangular chessboard. I.e., all elements of the return value must have the same length.

Constraints

  • A will be between 1 and 2500, inclusive.
Examples
0)
12
Returns: {"........", "../\\....", "./..\\...", ".\\...\\..", "..\\../..", "...\\/...", "........", "........" }

Note that the backslashes in the example output are escaped, i.e., each backslash is shown as \\ Below we show a nicer formatting of the return value: ........ ../\.... ./..\... .\...\.. ..\../.. ...\/... ........ ........

1)
7
Returns: { }

It is not possible to enclose a region with area 7.

2)
2498
Returns: { }

It is also impossible to enclose a region with area 2498. Remember the constraints on the chessboard size.

3)
10
Returns: {"./\\..", "/./..", "\\.\\/\\", ".\\../", "..\\/." }

Below we show a nicer formatting of the return value: ./\.. /./.. \.\/\ .\../ ..\/.

4)
26
Returns: {"/\\/\\/\\", "\\..../", "/....\\", "\\..../", "/....\\", "\\/\\/\\/" }

Below we show a nicer formatting of the return value: /\/\/\ \..../ /....\ \..../ /....\ \/\/\/

Submissions are judged against all 78 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class EncloseArea with a public method vector<string> enclose(int A) · 78 test cases · 2 s / 256 MB per case

Submitting as anonymous