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.