The rectangular printing sheet is divided into a grid of pixels. The grid consists of R rows and C columns.
A glyph is an image of a particular character when that character is printed.
In this problem we are considering only the glyph of character "A".
We think of the glyph as being drawn by four lines of equal and constant thickness.
Two lines are vertical and they share the same length. The remaining two lines are horizontal,
representing the top and the central bar of the glyph. See the schemes below.
A glyph is described by a tuple of four integers (H, W, T, B).
H is the height of the glyph in pixels.
W is the width of the glyph in pixels.
T is the thickness of the line by which the glyph is drawn.
B is the height of the bottom part of the glyph. It is equal to the number of rows occupied
by both legs of the glyph below the central horizontal bar of the glyph.
Two pixels, the pixel in the upper left corner and the pixel in the upper right corner of the glyph, are not part of the glyph.
This improves visual appearance of the whole glyph.
For example, a glyph described by tuple (13, 10, 3, 5) is schematically drawn in the left part in the scheme below.
W=10
+-----------------+ 1
| | 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8
+---------------------------------------+-
+----- X X X X X X X X --+ 0 | . . . . . . . . . . . . . . . . . . . |
| X X X X X X X X X X | T=3 1 | . . X X . . . X X . . . X X . . . . . |
| X X X X X X X X X X --+ 2 | . X . . X . X . . X . X . . X . . . . |
| X X X X X X 3 | . X X X X . X X X X . X X X X . . . . |
| X X X X X X 4 | . X . . X . X . . X . X . . X . . . . |
H=13 | X X X X X X X X X X --+ 5 | . X . . X . X . . X . X . . X . . . . |
| X X X X X X X X X X | T=3 6 | . . . . . . . . . . . . . . . . . . . |
| X X X X X X X X X X --+ 7 | . X X . X X . X X . . . . |
| +-- X X X X X X 8 | . X . . X . X . . X . X . . X . . . . |
| | X X X X X X 9 | . X X X X . X X X X . X X X X . . . . |
| B=5 | X X X X X X 10 | . X . . X . X . . X . X . . X . . . . |
| | X X X X X x 11 | . X . . X . X . . X . X . . X . . . . |
+----- +-- X X X X X X 12 | . . . . . . . . . . . . . . . . . . . |
13 | . . . . . . . . . . . . . . . . . . . |
| | | | 14 | . . . . . . . . . . . . . . . . . . . |
+---+ +---+ +---------------------------------------+
T=3 T=3
The printing area is to be tiled with identical glyphs.
The glyphs are organized into rows and columns. Two adjacent glyphs in one row are separated by a vertical gap which width is single pixel. Two adjacent rows of glyphs are separated by a horizontal gap which width is single pixel.
The glyphs are printed starting from the second row and from the second column of the sheet.
If any part of a printed glyph would appear in the last row or in the last column of the printing sheet, that glyph is not printed.
An example scheme of a sheet with 15 rows and 19 columns of pixels is shown in the right part in the scheme above. The sheet is tiled with glyphs described by tuple (5, 4, 1, 2). Note the empty rows and columns in the right part and in the bottom part of the sheet. (Horizontal spaces between adjacent pixels are added for better scheme readability.)
There are occasional impurities in the printing sheet. The impurities affect some pixels. If any part of the printed glyph would cover the impurity, that glyph is not printed. The Examples 1 and 3 below illustrate this rule.
Example 1(H, W, T, B) = (8, 7, 2, 2) Input sheet00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000002200000000 00000000000000000000000200000000 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 00000000002200000000000000000000 00000000002200000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000Output sheet 00000000000000000000000000000000 00111110001111100000000000000000 01111111011111110000002200000000 01100011011000110000000200000000 01100011011000110000000000000000 01111111011111110000000000000000 01111111011111110000000000000000 01100011011000110000000000000000 01100011011000110000000000000000 00000000000000000000000000000000 00111110000000000011111000000000 01111111000000000111111100000000 01100011002200000110001100000000 01100011002200000110001100000000 01111111000000000111111100000000 01111111000000000111111100000000 01100011000000000110001100000000 01100011000000000110001100000000 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 |
Example 2(H, W, T, B) = (4, 3, 1, 1) Input sheet000000000000000000000000000000 020202022202020222020202220202 002000202020002020200020202002 200000002000000020000000200002 202000202020002020200020202002 000000000000000000000000000000 000000000022222000000000000000 000000000022222000000000000000 000000000022222000000000000000 000000000000000000000000000000Output sheet 000000000000000000000000000000 021202122212021222120212221202 012101212121012121210121212102 211101112111011121110111211102 212101212121012121210121212102 000000000000000000000000000000 000000000022222000000000000000 000000000022222000000000000000 000000000022222000000000000000 000000000000000000000000000000 |
Example 3(H, W, T, B) = (9, 7, 3, 2) Input sheet20000000000000002 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000200000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 02000000000000000 20000000000000002Output sheet 20000000000000002 00111110001111100 01111111011111110 01111111011111110 01110111011101110 01111111011111110 01111111011111110 01111111011111110 01110111011101110 01110111011101110 00000000200000000 00000000001111100 00000000011111110 00000000011111110 00000000011101110 00000000011111110 00000000011111110 00000000011111110 00000000011101110 02000000011101110 20000000000000002 |
The task
Create file main.py containing function print_glyphs with 5 parameters: h, w, t, b, matrix (in this particular order). Parameters h, w, t, b describes the glyph and matrix represents the printing sheet which may contain impurities. Tile the sheet with glyphs described by the given tuple, and output the sheet.
Input
Matrix describing printing sheet is standard Python 2D matrix (list of lists). An empty pixel in printing sheet is described by value 0, a pixel with impurity is described by value 2. To guarantee that there is always the central "hole" above the horizontal bar in the glyph, and that the lowermost part of the horizontal bar is higher than the lowermost part of both vertical legs of the glyph following rules apply:1 ≤ T < min((H−1)/2, W/2); 1 ≤ B ≤ H−(2×T+1).
Output
Each pixel of the glyph is represented by value 1. An empty pixel is represented by value 0, a pixel with impurity is represented by value 2.
Evaluation
Your code will be evaluated on 8×2 test cases. Each of the 8 test cases (listed bellow) will grant you 0.75 points if both randomly generated tests pass.
| Test case | min_size (R/C) | max_size (R/C) | contains impurities | timeout |
|---|---|---|---|---|
| 1 | 8 | 10 | ❌ | 4 s |
| 2 | 16 | 20 | ✅ | 8 s |
| 3 | 32 | 40 | ❌ | 12 s |
| 4 | 64 | 80 | ✅ | 16 s |
| 5 | 128 | 160 | ❌ | 20 s |
| 6 | 256 | 320 | ✅ | 24 s |
| 7 | 512 | 640 | ❌ | 28 s |
| 8 | 987 | 1000 | ✅ | 32 s |