CandyShop
SRM 508 · 2010-11-01 · by gojira_tc
Problem Statement
The city Manao lives in can be represented as an infinite two-dimensional plane with a Cartesian coordinate system. From point (x, y), Manao can move to any of the points (x - 1, y), (x, y - 1), (x + 1, y), or (x, y + 1). In order to perform each of these 4 moves, he needs to walk 1 unit of length. Manao recalls that the candy shop was located at a point with integer coordinates. Also, he remembers that the i-th time he visited the candy shop, he went there from point (X[i], Y[i]) and walked at most R[i] units of length.
Since Manao's visits to the shop span a long period of time, he may have misremembered some details. If no intersection complies with his reminiscence, return 0. Otherwise return the number of different intersections where Manao's candy shop could be, assuming Manao remembers everything correctly.
Constraints
- X will contain between 1 and 50 elements, inclusive.
- Y will contain the same number of elements as X.
- R will contain the same number of elements as X.
- Each element of X will be between -100 and 100, inclusive.
- Each element of Y will be between -100 and 100, inclusive.
- Each element of R will be between 1 and 100, inclusive.
{0}
{0}
{1}
Returns: 5
Manao walked at most 1 unit of distance. Therefore, the shop could be at (0,0) if Manao didn't walk at all and at (1,0), (0,1), (-1,0) or (0,-1) if he walked.
{0}
{0}
{2}
Returns: 13
8 new locations are introduced if Manao walks another unit of distance.
{2,3}
{1,-1}
{2,2}
Returns: 4
The possible places for the shop are intersections (2,0), (2,-1), (3,0) and (3,1).
{2,3,5}
{1,-1,0}
{2,2,3}
Returns: 3
This is the same situation as in the previous example, but Manao has been to the shop once more. After this visit, (2,-1) is also ruled out from the possibilities list.
{-100,-100,-100,0,0,0,100,100,100}
{-100,0,100,-100,0,100,-100,0,100}
{1,1,1,1,1,1,1,1,1}
Returns: 0
Manao is surely mistaken in his reminiscence.
Submissions are judged against all 116 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class CandyShop with a public method int countProbablePlaces(vector<int> X, vector<int> Y, vector<int> R) · 116 test cases · 2 s / 256 MB per case