Số 3
View as PDFGabe là một cậu bé rất yêu thích số học. Mọi thứ liên quan tới số học đều làm cậu hứng thú, ngoại trừ duy nhất một thứ. Đó là chữ số ~3~. Không hiểu vì lý do gì mà cậu vô cùng căm ghét con số ấy. Ít thì không sao, nhưng chỉ cần thấy ít nhất ~K~ chữ số ~3~ là lập tức cậu trở nên cáu gắt khó chịu. Hôm nay là ngày sinh nhật của Gabe. Bố của cậu đã mua cho cậu một bộ bài. Bộ bài này gồm ~N~ lá bài, mỗi lá bài có viết trên nó 1 con số có giá trị dương bé hơn ~10^9~ và được xếp chồng lên nhau. Trớ trêu thay, bộ bài này lại có rất nhiều chữ số ~3~. Bố của Gabe không muốn cậu con trai mình tức giận, nên muốn lấy bớt một vài lá bài, sao cho trong số những lá bài còn lại, số lượng chữ số ~3~ không được lớn hơn hoặc bằng K. Tuy nhiên, nếu lấy một cách cẩu thả, bộ bài sẽ bị nhăn và Gabe sẽ lập tức nghi ngờ. Vì thế, ông quyết định sẽ lấy một số lá bài ở trên cùng bộ bài và một số lá bài ở dưới đáy bộ bài đi và giữ nguyên phần còn lại. Nhưng liệu điều đó có khả thi? Hãy giúp bố của Gabe tính số cách lấy bớt bài sao cho phần còn lại có số lượng chữ số 3 không lớn hơn hoặc bằng ~K~.
INPUT:
- Dòng đầu tiên gồm 2 số nguyên dương ~N~, ~K~
- Dòng thứ hai gồm N số ~a_i~ , (~1 \leq i \leq N~) là con số được viết trên lá bài thứ ~i~ tính từ trên cùng bộ bài trở xuống.
- Dữ liệu đảm bảo ~K~ bé hơn hoặc bằng tổng chữ số của ~N~ số.
OUTPUT:
- Gồm 1 số duy nhất là số cách lấy bớt một số lá bài sao cho phần còn lại có số lượng chữ số ~3~ không lớn hơn hoặc bằng ~K~.
VÍ DỤ
Input 1
5 3
13 24 333 3 33
Output 1
5
Input 2
6 1
3 3 3 3 3 3
Output 2
0
Subtask 1: ~15\%~ số test thỏa mãn ~N \leq 20~
Subtask 2: ~15\%~ số test thỏa mãn ~N \leq 100~
Subtask 3: ~15\%~ số test thỏa mãn ~N \leq 1000~
Subtask 4: ~15\%~ số test thỏa mãn ~N \leq 100000, K=1~
Subtask 5: ~20\%~ số test thỏa mãn ~N \leq 100000~
Subtask 6: ~20\%~ số test thỏa mãn ~N \leq 1000000~
Comments
Bumb
ukm
tuyệt