AlternateColors2 | Topcoder Archive

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.

Definition

Class:: AlternateColors2
Method:: countWays
Parameters:: int, int
Returns:: long
Method signature:: long countWays(int n, int k)
(be sure your method is public)

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

```
1
```
```
1
```
```
Returns: 1
```
There was only one ball. This ball was necessarily the first ball destroyed. Therefore, it had to be red.
```
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.
```
6
```
```
4
```
```
Returns: 9
```
```
6
```
```
1
```
```
Returns: 21
```
```
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.
```
100000
```
```
100000
```
```
Returns: 1666700000
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.