Hide

Problem J
Telescope Targeting

/problems/mines23.telescopetargeting/file/statement/en/img-0001.jpg
Photograh taken by the James Webb space telescope, courtesy of NASA

The Wames Jebb space telescope has just reached orbit, unfolded its mirrors, and started taking photographs of the universe’s farthest reaches! Scientists from all over the world have submitted requests for photographs of various astronomical phenomena, from stars and planets to distant galaxies and nebula. For budget reasons, undergraduate students at Mines have been tasked with operating the telescope and taking these photos.

Each scientist submits a preliminary image of the area of the sky they would like to photograph, to act as a reference. When it is time to fulfill their request, the Wames Jebb telescope rotates so that the referenced area of sky is centered in the telescope’s field of view. You must write a program to compare the reference image to the current view of the telescope, and output the number of degrees the telescope must rotate.

For example, sample input $1$ shows that a scientist is searching for a solitary star. Because the star appears slightly to the lower-right of the current view, rotating the Wames Jebb $1$ degree further rightward and $1$ degree further downward will point the telescope directly at the star, centering the reference image in the view.

Input

Each input begins with a reference image of the rectangular region of sky a scientist would like the Wames Jebb telescope to photograph. The first line provides two integers $1 \leq W_ r \leq 50$ and $1 \leq H_ r \leq 50$: the width and height of the reference image in degrees. The next $H_ r$ lines of the input each contain $W_ r$ characters. Each character specifies which type of object appears in a square of the reference image roughly one degree wide and one degree tall:

#” (pound symbol)  

–   Empty space.

*” (star symbol)  

–   A star.

.” (period)  

–   A planet.

o” (lowercase letter O)  

–   A nebula.

@” (at symbol)  

–   A galaxy.

If the reference image contains an astronomical object $x$ degrees from its leftmost edge and $y$ degrees its topmost edge, the $x^{\text {th}}$ character in the $y^{\text {th}}$ line will be used to represent that object.

After the reference image, the input contains the Wames Jebb’s current view of the sky, in the same format. First there are two integers, $1 \leq W_ s \leq 50$ and $1 \leq H_ s \leq 50$, giving the width and height of the view in degrees. Then $H_ s$ lines of $W_ s$ characters each, showing what astronomical object is visible in each square degree of the sky.

Note that the currently visible rectangle of sky will always contain the full reference image exactly once, and that a fractional rotation will never be necessary to center the reference image in the view. As a consequence, the current view will always be larger than the reference, and both the differences $W_ s - W_ r$ and $H_ s - H_ r$ will be evenly divisible by two.

Output

The output should contain a single line with two integers: the number of degrees rightward the telescope should rotate and the number of degrees downward the telescope should rotate, so that the scientist’s image is brought into the center of the view. To rotate the telescope leftward or upward, specify rotation rightward or downward by a negative number of degrees.

Sample Input 1 Sample Output 1
3 3
###
#*#
###
5 5
#####
#####
#####
###*#
#####
1 1
Sample Input 2 Sample Output 2
4 4
#oo#
##*#
###@
#.##
10 6
##.#oo##*#
#@###*####
*#####@#*#
#*##.#####
#*#######*
####*##@##
0 -1

Please log in to submit a solution to this problem

Log in