AlternateColors2

SRM 564 · 2012-06-05 · by vexorian

SRM 564 · 2012-06-05 · by vexorian · Math, Simple Search, Iteration

Show categories

Class Name: AlternateColors2

Return Type: long

Method Name: countWays

Arg Types: (int, int)

Problem Statement

Bob is playing with his ball destroyer robot. Initially, Bob had r red balls, g green balls and b blue balls. The robot repeated the following 3-step program until there were no balls left:

If there is at least one red ball available, destroy one red ball.
If there is at least one green ball available, destroy one green ball.
If there is at least one blue ball available, destroy one blue ball.

Bob forgot how many balls of each color he initially had. He only remembers that there were n balls in total and that the k-th (1-based index) ball that was destroyed was red. Return the total number of different initial settings that match that description. Formally, return the number of different tuples (r, g, b) such that r + g + b = n and the k-th ball that was destroyed was red.

Notes

It follows from the constraints that the return value will always fit into a long.

Constraints

n will be between 1 and 100000, inclusive.
k will be between 1 and n, inclusive.

Examples

100000
100000
Returns: 1666700000

1
1
Returns: 1

There was only one ball. This ball was necessarily the first ball destroyed. Therefore, it had to be red.

2
2
Returns: 1

3
3
Returns: 3

There are three cases in which the third ball to be destroyed is red: r = 3, b = 0, g = 0. r = 2, b = 1, g = 0. r = 2, b = 0, g = 1.

4
4
Returns: 4

17)

1000
2
Returns: 1

In order for the second destroyed ball to be red, there would have to be zero balls of the other colors.

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

Coding Area

Language: C++17 · define a public class AlternateColors2 with a public method long long countWays(int n, int k) · 187 test cases · 2 s / 256 MB per case