CCC '05 J4 - Cross Spiral

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
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), that is column 1 and row 1. The walk always starts at column X and row 1, where X is the leftmost column of row 1 in the cross. The tile at position (X, 1) cannot be revisited during the walk, however the first step is counted when Bridget moves to an adjacent tile.

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. The minimum width of the cross will be 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:

10
8
3
2

In other words, the outlining rectangle is 10 units wide and 8 units high. The "cut out" rectangles are 3 units wide and 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

10
8
3
2
15

Sample Output 1

7
7

Explanation for Sample Output 1

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

Sample Input 2

8
7
2
2
27

Sample Output 2

5
2

Explanation for Sample Output 2

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

Sample Input 3

8
7
2
2
40

Sample Output 3

7
4

Explanation for Sample Output 3

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

Sample Input 4

6
6
1
2
1

Sample Output 4

3
1

Explanation for Sample Output 4

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


Comments


  • 0
    evanzhao  commented on May 6, 2020, 10:19 p.m.

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


    • 2
      X_Ray  commented on Aug. 28, 2020, 3:17 p.m.

      Print the square she gets trapped on.


  • 1
    Selena_Liu  commented on Aug. 1, 2017, 7:10 p.m.

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


    • 0
      wleung_bvg  commented on Aug. 1, 2017, 8:14 p.m.

      I don't think the judge supports numpy


      • 1
        Selena_Liu  commented on Aug. 2, 2017, 12:19 p.m.

        Oh. why?


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

          It's not a part of the base Python language