Want to try solving this problem? You can submit your code online if you log in or register.
Time Limit: 3 seconds
Memory Limit: 32 Mb
You are part of a team of archaeologists who have just discovered a secret chamber inside the great pyramid of Giza. Unfortunately, this chamber is completely empty, except for 22 small cubic stones forming a circle on the ground in the middle of the chamber.
You notice that two of these cubes are broken, and after detailed observation, you realise that each of them has a hieroglyph carved in its central horizontal layer. A hidden message of great historical significance is waiting to be discovered. However, you can't break or even move the remaining 20 cubes to read the message, so you decide to use radiography, and take three X-ray pictures of each cube.
The results clearly show that, as you expected, a hieroglyph is carved in the middle horizontal layer of each cube, but since your X-ray pictures are taken from the sides of the cube and not from the top, you are unable to read the hidden hieroglyph directly. You need your computer to help you with this task.
The middle layer of each cube can be represented as an N x N grid of squares, which are either filled or empty. From your three pictures, you know the exact number of squares that are empty in each column, row and diagonal (the diagonals run in the top-left to bottom-right direction).
The grid squares are given (x, y) coordinates, so that the top-left square has coordinates (0, 0) and the bottom-right square has coordinates (N-1, N-1). The rows, columns and diagonals are each numbered 0,1,2,.... A square that has coordinates (x, y) is part of column x, line y, and diagonal x - y + (N - 1); thus the short diagonal in the bottom-left corner is diagonal 0, the long diagonal running from square (0, 0) to (N-1, N-1) is diagonal N - 1, and the short diagonal in the top-right corner is diagonal 2N - 2.
The diagram above shows an example hieroglyph with the results from the three X-rays, showing the number of empty squares in each column, row and diagonal.
Write a program that, given the number of empty squares in each column, row and diagonal of the grid, outputs a hieroglyph that matches the number of empty squares in each direction as closely as possible with the input.
Your program must read from standard input. The first line will contain the integer N, indicating the size of the N x N grid.
The second line will contain N space-separated integers. The ith of these integers gives the number of empty squares in the ith column of the grid, starting from the left.
The third line will contain N space-separated integers. The ith of these integers gives the number of empty squares in the ith row of the grid, starting from the top.
The fourth line will contain (2N - 1) space-separated integers. The ith of these integers gives the number of empty squares in the ith diagonal of the grid, starting from the bottom left.
Your program must write N lines to standard output, describing a possible hieroglyph. Each line must contain N characters describing a row of the grid, where the character `1' denotes a filled square, and `0' denotes an empty square. The output must not contain any spaces.
10 0 1 1 2 2 3 7 8 6 0 0 3 3 3 3 2 3 6 7 0 0 0 1 1 1 2 2 1 3 3 3 2 2 3 3 2 1 0 0
1111111111 1111110001 1111110001 1111110001 1111110001 1111110011 1111100011 1110000001 1000001001 1111111111
For a given input scenario, the sums of empty squares on each column, row and diagonal of your output grid will be compared to the input values. The error for each column, row and diagonal will be the absolute difference between the input value and the value obtained from your grid. The total error of your output will be the sum of these errors. Your score for this input scenario will then be :
Privacy
statement
© Australian Mathematics Trust 2001-2023
Page generated: 24 March 2023, 9:16pm AEDT