### PROBLEM LINKS

### DIFFICULTY

MEDIUM

### EXPLANATION

The model solution for this problem is very simple, and this problem can be solved for larger **N**. However I have set **N** ≤ 36 for keeping away from guessing the simple solution from the constraint. Naive bruteforce algorithms with **O(N!/K!/(N-K)!)** or O**(N*2^{N/2})** will get TimeLimitExceeded. I would like to say that the tester can solve this problem by an optimized bruteforce solution.

Let’s start the explanation of the model solution. We don’t have to check all combinations. At first, sort Pi, and consider the case where **P _{1} ≤ P_{2} ≤ … ≤ P_{N}.** There is at least one answer that first i problems and last

**K-i**problems are chosen, that is, problem 1, 2, …,

**i**, and problem

**N-K+i+1, N-K+i+2,**…,

**N**are chosen. This method is

**O(N**time implemented naively as the setter’s solution.

^{2}+ K^{3})A short proof is the following. Let one of the optimal sets be the problem **A _{1}, A_{2}, …, A_{K}**, and let the set don’t contain problem

**B**and

**C**, where

**B**<

**A**. For the set of

_{K}< C**K-1**problems

**A**, let

_{1}, A_{2}, …, A_{K-1}**x**be the probability that all problems are solved correctly, and y be the probability that

**K-2**problems solved correctly. Then, the probability of solving

**K-1**problems correctly for the set of

**K**problems

**A**

_{1},

**A**

_{2}, …,

**A**

_{k-1},

**Z**is ( 1-

**P**

_{Z}/100 ) * x +

**P**

_{Z}/100 *

**y**. Because this is the linear function of

**P**

_{Z}, the set of problems

**A**

_{1}**,

**A**

_{2}, …,

**A**

_{K-1},

**B**and

**A**

_{1},

**A**

_{2}, …,

**AK**-1,

**C**are also optimal sets.

### SETTER’S SOLUTION

Can be found here.

### TESTER’S SOLUTION

Can be found here.