### PROBLEM LINK:

[Practice][1]

[Contest][2]

**Author:** [Vasia Antoniuk][3]

**Tester:** [Sergey Kulik][4]

**Editorialist:** [Mugurel Ionut Andreica][5]

### DIFFICULTY:

SIMPLE

### PREREQUISITES:

None

### PROBLEM:

Chef must draw the minimum number of balloons from a box containing **R** red, **G** green and **B** blue balloons, in such a way that he is certain that there will be at least **K** balloons of the same color among the drawn balloons.

### QUICK EXPLANATION:

The answer is **min{R,K-1}+min{G,K-1}+min{B,K-1}+1**.

### EXPLANATION:

Let’s consider what is the worst case that Chef can encounter before he is certain that he extracted at least **K** balloons of the same color. If all **R**, **G** and **B** are greater than or equal to **K** then the worst case is that Chef picks **K-1** balloons of each of the 3 colors. After extracting **3x(K-1)** balloons he can be certain that, after the next balloon he extracts, there will be at least **K** balloons of the same color. On the other hand, he cannot stop after extracting less than or equal to **3x(K-1)** balloons because of the worst case we mentioned (meaning that in this case it’s possible to **not** have at least **K** balloons of the same color).

In the general case, when any of **R**, **G** or **B** can be smaller than **K**, the worst case is defined as follows. For each color **C**, if there are at least **K** balloons of that color, then the worst case will contain **K-1** balloons of that color. Otherwise it will contain all the balloons of that color. This means that as soon as Chef extracts **min(R,K-1)+min(G,K-1)+min(B,K-1)** balloons, he only needs one more balloon to be certain that he has at least **K** balloons of the same color among the extracted balloons. Thus, the answer is **min(R,K-1)+min(G,K-1)+min(B,K-1)+1**.

Time complexity: **O(1)** per test case.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.

[1]: http://www.codechef.com/problems/CHBLLNS

[2]: http://www.codechef.com/APRIL16/problems/CHBLLNS

[3]: http://www.codechef.com/users/antoniuk1

[4]: http://www.codechef.com/users/xcwgf666

[5]: http://www.codechef.com/users/mugurelionut

[6]: X

[7]: Y