CCC '05 J4 - Cross Spiral - DMOJ: Modern Online Judge

CCC '05 J4 - Cross Spiral

View as PDF

Submit solution

All submissions

Best submissions

Points: 7 (partial)

Time limit: 1.0s

Memory limit: 256M

Problem type

Canadian Computing Competition: 2005 Stage 1, Junior #4

In an old house there is a room that is shaped like a cross. You can think of a cross as being an outlining rectangle with four smaller rectangles cut out of the corners. The floor of the room is completely covered with square tiles. Bridget is walking around the room, stepping from one tile to the next, spiraling towards the centre. Bridget always walks clockwise and stays as close to the edge of the room as possible without stepping on any tile twice. It is possible that she may be trapped and unable to move to an adjacent tile before reaching all the tiles in the room.

Assume that the upper left corner of the outlining rectangle is position $(1, 1)$ $(1, 1)$ , that is column $1$ $1$ and row $1$ $1$ . The walk always starts at column $X$ $X$ and row $1$ $1$ , where $X$ $X$ is the leftmost column of row $1$ $1$ in the cross. The tile at position $(X, 1)$ $(X, 1)$ cannot be revisited during the walk, however the first step is counted when Bridget moves to an adjacent tile.

$\text{[math]}$

Write a program that calculates Bridget's final column and row position in the room after the walk. The program must accept input for the dimensions of the cross: i.e. the width and height of the outlining rectangle, the width and height of the "cut out" rectangles, and the number of steps the person will take.

The maximum width and height of the outlining rectangle will be $20 \times 20$ $20 \times 20$ . The minimum width of the cross will be $1$ $1$ . The vertical and horizontal parts of the cross are not necessarily the same width.

Input Specification

Five integers, each on their own line. The first two represent the width and height of the outlining rectangle, while the next two represent the width and height of the "cut out" rectangles. The last integer specifies how many steps are taken.

In the diagram, the input for the dimensions of the cross is:

Copy

In other words, the outlining rectangle is $10$ $10$ units wide and $8$ $8$ units high. The "cut out" rectangles are $3$ $3$ units wide and $2$ $2$ units high.

Output Specification

Two integers, each on their own line, representing Bridget's final column and row position in the room after the walk.

Sample Input 1

Copy

Sample Output 1

Copy

7
7

Explanation for Sample Output 1

Same room as diagram above, taking $15$ $15$ steps, and ending up in column $7$ $7$ and row $7$ $7$ .

Sample Input 2

Copy

Sample Output 2

Copy

5
2

Explanation for Sample Output 2

$8$ $8$ columns by $7$ $7$ rows, with $2$ $2$ by $2$ $2$ squares removed from each corner. After $27$ $27$ steps, we end up at column $5$ $5$ , row $2$ $2$ .

Sample Input 3

Copy

Sample Output 3

Copy

7
4

Explanation for Sample Output 3

Same square as Sample Input 2, but after $40$ $40$ steps, we are at column $7$ $7$ , row $4$ $4$ .

Sample Input 4

Copy

Sample Output 4

Copy

3
1

Explanation for Sample Output 4

A $6$ $6$ by $6$ $6$ square, with the corners being pieces $1$ $1$ column wide and $2$ $2$ rows high. After one step, we end at column $3$ $3$ , row $1$ $1$ .

Comments

1

Evang commented on May 7, 2020, 2:19 a.m.

What happens when Bridget gets trapped? In the third input, Bridget gets trapped at one point.

5

X_Ray commented on Aug. 28, 2020, 7:17 p.m.

Print the square she gets trapped on.

1

Selena_Liu commented on Aug. 1, 2017, 11:10 p.m. ← edited →

I've got an import error. I'm importing numpy using python. What's the problem with it?

3

wleung_bvg commented on Aug. 2, 2017, 12:14 a.m.

I don't think the judge supports numpy

1

Selena_Liu commented on Aug. 2, 2017, 4:19 p.m.

Oh. why?

5

wleung_bvg commented on Aug. 2, 2017, 5:35 p.m.

It's not a part of the base Python language