### PROBLEM LINK:

**Author:** Omkar Prabhu

**Tester:** Hanlin Ren

**Editorialist:** Hanlin Ren

### DIFFICULTY:

SIMPLE

### PREREQUISITES:

None

### PROBLEM:

Chef’s company should fill N patents in the first M months. The M months are numbered from 1 to M, and there are K workers in the company. Any worker can only fill one patent, and only works in odd months or even months. You are given a string s, if s[i]=`'E'`

, then the i-th worker only works on even months(2,4,etc.), otherwise s[i]=`'O'`

and the i-th worker only works on odd months(1,3,etc.). At most x patents can be filled per month. Determine if it’s possible to fill N patents in M months.

### QUICK EXPLANATION:

Suppose there are o `'O'`

's and e `'E'`

's in s, then output `yes`

if and only if

### EXPLANATION:

First consider odd months. There are \lfloor\frac{M+1}{2}\rfloor odd months among the first M months, so we can fill at most x\lfloor\frac{M+1}{2}\rfloor patents. We can also count the number of `'O'`

's in s, say there are o `'O'`

's, then at most o patents can be filled. In total, we can fill at most \min(o,x\lfloor\frac{M+1}{2}\rfloor) patents in odd months.

Then we consider even months. There are \lfloor\frac{M}{2}\rfloor even months among the first M months, so we can fill at most x\lfloor\frac{M}{2}\rfloor patents. We count the number of `'E'`

's in s, say there are e `'E'`

's, then at most e patents can be filled. In total, we can fill at most \min(e,x\lfloor\frac{M}{2}\rfloor) patents in even months.

Therefore, in total we can fill

patents, and we compare this number to N.

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

Author’s solution can be found here.

Tester’s solution can be found here.