This is the fifty fifth part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra We have already seen Max flow and last time we used it to ensure…
This is the fifty second part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra In part 2 we saw how to calculate unsigned magnitude decomposition for non-negative integer…
This is the forty ninth part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra Today we solve the task B from Deadline24 2018 edition.
Beetlejumpers are known throughout the Universum for their concern for the infrastructure and industrial
facilities of their worlds. The exceptional quality of solutions provided throughout the worlds is
due to the high-quality materials, as much as. . . to the extraordinary skills of Beetle-architects.
To become one of the famous Beetle-architects one has a long way to go. One of the first challenges
on this career path is the work on the less elegant, but no less important projects – such as planning
the sewage system layout.
Competence examination for 2nd degree Beetle-prearchitect includes, among others, the following
problem: Connect entrance connections with exit connections in a given area with the dimensions X * Y .
It is a typical examination problem, so there are numerous conditions simulating the real work:
- there is not much vertical space, so the pipes must not cross,
- due to optimization requirements the whole space must be covered with pipes,
- due to safety standards concerning pressure, each connection must be used only once.
Naturally, the area the examinee is working on is precisely defined, i.e., pipes cannot protrude beyond
An area with dimensions X * Y and the number of the necessary connections – N are known. Also
known is the set of start points with their corresponding end points (N pairs of coordinates).
The problem is to generate pipeline descriptions: each description must begin at one of start points
and finish at a corresponding end point. Each field of a given area must be used exactly once and all
pipelines must fit within the borders of the area.
Test sets are given in flow*.in files.
The first line of the test set includes one integer T denoting the number
of tests. Description of each test contains the definition of the area and connections
belonging to it.
The first line of the test description includes two natural numbers X
and Y that denote the dimensions of the area to be covered with pipes. The second
line includes a natural number N – the number of pipelines (connections)
to be built.
Each of the following N lines contains four natural numbers separated
by spaces – information concerning the pairs of connection points. The first
two numbers in each of those lines (x_s^i, y_s^i ) denote the pipeline start point coordinates.
The following two numbers in each of those lines (x_e^i, y_e^i ) are the endpoint coordinates of the same pipeline.
Each test has at least one correct solution.
1 <= T <= 10
5 <= X; Y <= 100
1 <= N <= 600
1 <= x_s^i, ; x_e^i <= X
1 <= y_s^i ; y_e^i <= Y
1 <= i <= N
As an answer to each test provide definitions of pipeline routes. Test answers must be provided in
the same sequence as in the input data file.
The first line of the test answer should contain N – the number of pipelines. The following N lines
should include sequences of characters Ck. Each character Ck can take one of the following values (the pair
(i; j) was adopted as current coordinates):
- ’N’ – for the move to j - 1 line (up),
- ’E’ – for the move to i + 1 field in the same line (to the right),
- ’S’ – for the move to j + 1 line (down),
- ’W’ – for the move to i - 1 field in the same line (to the left).
Each sequence corresponds to one pipeline and describes consecutive steps of moving around a given
area, beginning at start point and finishing at its corresponding end point (if a pipeline covers the area
of F fields, its description should consist of F - 1 characters). Pipelines should be presented in the same
sequence as their start and end points were provided in the input data file.
For input data:
1 1 3 3
1 2 1 3
1 1 1 7
2 1 2 7
3 1 3 7
4 1 4 7
One of possible solutions is:
Idea is: for…