ThreeDarts

SRM 836 · 2022-08-29 · by misof

SRM 836 · 2022-08-29 · by misof · Brute Force

Show categories

Class Name: ThreeDarts

Return Type: int[]

Method Name: throwDarts

Arg Types: (int)

Problem Statement

In darts, the target is divided into sections. Each section has an assigned point value: a positive integer. These values are as follows:

For each x between 1 and 20, inclusive, there are sections worth 1*x, 2*x, and 3*x points. (These are called "single x", "double x", and "triple x".)
In the middle of the target is the bullseye. The bullseye consists of two sections: the outer one is worth 25 points and the inner one is worth 50.

You are given the int N.

Determine whether it's possible to score exactly N points by hitting the target with at most three darts. If no, return an empty int[]. If yes, return a int[] containing one way of scoring N points: for each dart that hits the target the number of points it scores.

Constraints

N will be between 1 and 200, inclusive.

Examples

50
Returns: {50 }

The simplest way to score 50 points is to take one dart and hit the inner bullseye.

179
Returns: { }

There is no way to score exactly 179 points using at most three darts.

6
Returns: {3, 1, 2 }

If a solution exists, any valid solution will be accepted. It's not required to use the smallest possible number of darts. The returned int[] does not have to be sorted.

60
Returns: {30, 30 }

Different darts may hit the same section of the target and thus get the same score. (The value 30 can be scored with a single dart by hitting the "double 15" section that is worth 2*15 points.)

1
Returns: {1 }

25)

23
Returns: {1, 22 }

No section is worth exactly 23 points so we need to use at least two darts. Our solution throws one dart into the single 1 and then one dart into the double 11.

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

Coding Area

Language: C++17 · define a public class ThreeDarts with a public method vector<int> throwDarts(int N) · 200 test cases · 2 s / 256 MB per case