Problem B
Overnight Oats
As a true porridge connoisseur, Julia has decided to start eating a new type of porridge – overnight oats. During an $N$-day period, each evening she will either prepare a cup of overnight oats, eat her oldest cup of overnight oats, or do neither. However, since overnight oats are food, and food can go bad, the oats can also expire (even though Julia stores them in her refrigerator). Each cup has a shelf life of $X$ days, after which it goes bad. Julia also leaves room in her stomach for all the other types of porridge she eats (oat porridge, semolina porridge, rice porridge, etc.), so you should not feel bad for her only getting to eat a single cup of overnight oats a time, and not even every day.
It is guaranteed that the refrigerator will be empty at the end of the $N$ days. Additionally, Julia will never eat if there are no overnight oats in the fridge. Julia wants to avoid eating expired overnight oats.
Is this possible?
Input
The first line contains the integer $N$ ($1 \leq N \leq 3 \cdot 10^5$).
The second line contains the integer $X$ ($1 \leq X \leq 3 \cdot 10^5$).
Then follow $N$ lines, each containing either “ADD”, “EAT”, or “PASS”.
Output
Print “yay!” if no cup of overnight oats expires before Julia eats it.
Print “ono..” if any cup becomes too old.
Scoring
Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.
|
Group |
Points |
Constraints |
|
$1$ |
$41$ |
$N \leq 1000$ |
|
$2$ |
$59$ |
No additional constraints. |
Explanation of Sample 1
The porridge Julia prepares on the first day will on the third day be $2$ days old, which is one more than its shelf life and so it will be expired when she eats it :(
| Sample Input 1 | Sample Output 1 |
|---|---|
3 1 ADD PASS EAT |
ono.. |
| Sample Input 2 | Sample Output 2 |
|---|---|
8 3 ADD ADD EAT ADD EAT ADD EAT EAT |
yay! |
