Connection Status:
Competition Arena > LazyCat

LazyCat

TCCC07 Sponsor 3 · 2007-07-30 · by Mike Mirzayanov

TCCC07 Sponsor 3 · 2007-07-30 · by Mike Mirzayanov · Greedy
Class Name: LazyCat
Return Type: int
Method Name: maxMiceCount
Arg Types: (vector<int>, vector<int>, int, vector<int>)
Problem Statement

Problem Statement

Tom the lazy cat wants to catch some mice that live near him, but he is too lazy to ever move away from his favorite chair. Fortunately, he has several hats which can be thrown to catch mice. If there is an uncaught mouse no further than d feet from Tom, he can throw one of his hats and catch that mouse (throwing a hat takes no time). Tom is a very clever cat, so he never misses, but he must have a rest after each throw and he cannot use the same hat more than once.

At time 0, the i-th mouse is pos[i] feet away from Tom, and is running away from Tom at the speed of speed[i] feet per second. So, after k seconds, the i-th mouse will be (pos[i] + k * speed[i]) feet away from Tom. Tom is given n hats, numbered 0 through n-1, and he may throw them in any order. He must wait rest[i] seconds after throwing hat number i (he cannot throw any more hats during this time). You are given an int d, the maximum distance a hat can be thrown (this distance is the same for all hats). Return the maximal number of mice he'll be able to catch.

Constraints

  • pos will contain between 1 and 50 elements, inclusive.
  • speed will contain the same number of elements as pos.
  • d will be between 0 and 1000, inclusive.
  • rest will contain between 1 and 50 elements, inclusive.
  • Each element of pos, speed, and rest will be between 1 and 1000, inclusive.
Examples
0)
{4, 1, 2}
{1, 1, 1}
3
{3, 2, 1}
Returns: 2

Tom can't catch mouse 0 because it is situated farther than d = 3 feet.

1)
{5, 5, 5}
{1, 1, 1}
5
{1, 1, 1}
Returns: 1

Tom can only catch one mouse. After his rest, the other two will be too far away.

2)
{13, 5, 8}
{10, 10, 10}
15
{1, 1, 1}
Returns: 2

He can catch mouse 2, which is 8 feet away at time 0, and after his rest, he can catch mouse 1, which will be 15 feet away at time 1.

3)
{1000}
{1000}
100
{1000}
Returns: 0
4)
{1,1,1,1,1}
{1,1,1,1,1}
3
{1,1,1,1,1,1,1,1,1,1}
Returns: 3

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

Coding Area

Language: C++17 · define a public class LazyCat with a public method int maxMiceCount(vector<int> pos, vector<int> speed, int d, vector<int> rest) · 240 test cases · 2 s / 256 MB per case

Submitting as anonymous