Connection Status:
Competition Arena > RobotHerbDiv2

RobotHerbDiv2

SRM 570 · 2012-12-13 · by snuke

SRM 570 · 2012-12-13 · by snuke · Simulation
Class Name: RobotHerbDiv2
Return Type: int
Method Name: getdist
Arg Types: (int, vector<int>)
Problem Statement

Problem Statement

Robot Herb is playing on an infinite square grid. At any moment, Herb stands on one of the squares and he faces one of the four cardinal directions. In his memory, Herb has a program. The program is a sequence of commands. For each i, the i-th of these commands has the following form:

  • First move forward a[i] tiles.
  • Then turn 90 degrees to the right, a[i] times in a row.

Herb has decided to run the program T times. You are given the int T and the int[] a that describes Herb's program. Let A be the initial position of Herb and B be his position after the program was executed T times. Return the Manhattan distance between tiles A and B.

Notes

  • Let's introduce a Cartesian coordinate system on the grid so that each cardinal direction is parallel to one of the axes. The Manhattan distance between two tiles with centers at points (x1, y1) and (x2, y2) is defined as |x1-x2| + |y1-y2|.

Constraints

  • T will be between 1 and 100, inclusive.
  • a will contain between 1 and 50 elements, inclusive.
  • Each element of a will be between 1 and 400,000, inclusive.
Examples
0)
1
{1,2,3}
Returns: 2

Suppose that initially Herb stands on the tile with center at (0, 0) and faces the positive y direction. The program will get executed as follows: tile direction After 1st command: (0, 1) positive x After 2nd command: (2, 1) negative x After 3rd command: (-1, 1) negative y The manhattan distance between the initial and the final positions is |-1| + |1| = 2.

1)
100
{1}
Returns: 0
2)
5
{1,1,2}
Returns: 10
3)
100
{400000}
Returns: 40000000
4)
100
{100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000}
Returns: 500000000

Submissions are judged against all 73 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class RobotHerbDiv2 with a public method int getdist(int T, vector<int> a) · 73 test cases · 2 s / 256 MB per case

Submitting as anonymous