CatAndMice
TCO19 SRM 760 · 2019-06-11 · by misof
Problem Statement
We are on an infinite horizontal plane. For each pair of integers (x, y) such that |x| <= N and |y| <= N there is an animal sitting on the point (x, y). The animal on (0, 0) is a cat and all other animals are mice.
The cats wants to run away in some direction, that is, along some infinite ray that starts at (0, 0). Along the way the cat will catch and eat all the mice it encounters.
The cat wants to catch exactly C mice. Return the number of different directions the cat can choose.
Constraints
- N will be between 1 and 5,000,000, inclusive.
- C will be between 1 and N, inclusive.
2 2 Returns: 8
The cat can choose any of the eight cardinal directions: horizontally, vertically, or diagonally (at 45 degrees).
2 1 Returns: 8
Again there are eight options for the cat. One of them is to run along the ray that goes approximately 26.57 degrees counter-clockwise from the positive x direction. When running along this ray the cat will catch and eat the mouse that sits on the point (2, 1), and no other mouse.
19 3 Returns: 48
One of the good options involves the cat eating the mice at (-5, 6), (-10, 12), and (-15, 18).
5000000 1 Returns: 45594542166976
1234 3 Returns: 180608
1234 1212 Returns: 0
In this setting it's not possible for the cat to catch exactly 1212 mice.
Submissions are judged against all 122 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class CatAndMice with a public method long long countDirections(int N, int C) · 122 test cases · 2 s / 256 MB per case