Đoạn con bằng k
Xem PDFcó một xâu kí tự nhị phân \(S\) định làm quà tặng cho đội trưởng đội tuyển quốc gia tin học Thanh Ngọc nhân dịp đội trưởng đạt được một tầm cao mới trên Codeforces. Thanh Ngọc là một người đơn giản, nhưng vô cùng tinh tế, cậu không thích những thứ quá lớn. Do đó, Thanh Ngọc đã đánh giá mòn quà của qua \(q\) câu hỏi, mỗi câu hỏi là một số tự nhiên \(k\). cần trả lời xem, với mỗi số tự nhiên \(k\) có tồn tại một đoạn con liên tiếp của xâu \(S\) mà tổng các kí tự trong đoạn con này đúng bằng \(k\) hay không.
Do quá bận rộn, các bạn hãy giúp trả lời câu hỏi này nhé.
Input
- Dòng đầu tiên chứa một số nguyên dương \(n\) là độ dài xâu \(S\) của .
- Dòng tiếp theo chứ xâu \(S\) độ dài đúng bằng \(n\).
- Dòng tiếp theo là một số nguyên dương \(q\) là số câu hỏi mà Thanh Ngọc sẽ hỏi.
- \(q\) dòng cuồi cùng, mỗi dòng là một số nguyên không âm \(k\) là một câu hỏi của Thanh Ngọc.
Output
- In ra \(q\) dòng, với mỗi dòng, in "Ami Dep Trai" nếu tồn tại một đoạn con liên tiếp của \(S\) có tổng bằng \(k\), hoặc in ra "Luong Xiao Lin" trong trường hợp ngược lại.
Scoring
-
Subtask \(1\) (\(30\%\) số điểm): \(n , k \leq 10^3, q \leq 10^5\)
-
Subtask \(2\) (\(70\%\) số điểm): \(n, q , k \leq 10^5\)
Example
Test 1
Input
3
110
3
1
2
100000Output
Ami Dep Trai
Ami Dep Trai
Luong Xiao LinNote
Các xâu con của \(|110|\) là |11| , |10| , |1| , |1| , |0| , |110|, tương ứng với tổng là 2 , 1 , 1 , 1 , 0 , 2.
Bình luận
bài này nói dễ hiểu là đếm xem thử số phần tử có giá trị 1 có lớn hơn k hay không, đúng thì in Ami Dep Trai không thì ngược lại;
TH đặc biệt: nếu k==0 và không có phần tử có giá trị 0 thì in Luong Xiao Lin
giờ mới hiểu 🙂
Thank you bạn vì mình đọc xong đề nhưng chẳng hiểu gì hết! Nhờ bạn mà mình mới hiểu!