\(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.0}}}}}\)

\(\color{red}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

\(\color{red}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)

\(\color{orange}{\text{Hint 1}}\)

• Đề yêu cầu: Với mỗi số \(k\) nhận vào, kiểm tra xem trong xâu \(S\) có đoạn con nào có đúng \(k\) chữ số \(1\) hay không

Cách đơn giản nhất là mình sẽ thử từng đoạn \([i_1; i_2] \in [0; S.size)\) và xuất ra màn hình nếu tồn tại đoạn con đó

Độ phức tạp sẽ là \(O(n ^ 2)\) dể kiểm tra

\(\color{orange}{\text{Hint 2}}\)

• Nhận thấy nếu trong xâu \(S\) chỉ có \(cnt\) chữ số \(1\) thì không có bất cứ đoạn con nào có hơn \(cnt\) chữ số \(1\)

• Nhận thấy nếu đoạn con \([i_1; i_2]\) có \(k\) chữ số \(1\) thì khi mình di chuyển hai con trỏ \(i_1\) và \(i_2\) lại gần nhau hơn, thì nó sẽ có ít chữ số \(1\) đi

Vậy tại \(i_1\) cố định đoạn \([i_1; i_2]\) có nhiều hơn \(k\) chữ số \(1\) thì mình di chuyển \(i_2\) lại gần

• Nhận thấy nếu đoạn con \([i_1, i_2]\) có \(k\) chữ số \(1\) thì khi mình cố định con trỏ \(i_1\) hoặc \(i_2\) thì khi mình di chuyển con trỏ còn lại ra xa hơn nó sẽ có thêm chữ số \(1\)

Vậy tại \(i_1\) cố định đoạn \([i_1; i_2]\) có ít hơn \(k\) chữ số \(1\) thì mình di chuyển \(i_2\) ra xa

• Từ đó, việc kiểm tra của chúng ta rút còn \(O(n \log n)\) bằng việc chặt nhị phân \(i_2\) với \(i_1 \in [0; S.size)\)

\(\color{orange}{\text{Hint 3}}\)

• Nhận thấy rằng từ vị trí \(i_1 = 0\) cố định và \(i_2 = S.size - 1\) thì chứa toàn bộ chữ số \(1\) trong \(S\)

Khi kiểm tra, nếu đoạn \([i_1; i_2]\) có nhiều chữ số hơn, mình chỉ việc di chuyển nó lại gần

Ngược lại không di chuyển ra xa được nữa, tức là \(k > cnt\) thì sẽ không có đoạn con thỏa mãn

• Từ nhận xét trên, ta giảm độ phức tạp còn \(O(\log n)\) việc chặt nhị phân \(i_2\) với \(i_1 = 1\)

\(\color{orange}{\text{Hint 4}}\)

• Nếu trong dãy không có bất cữ chữ số \(0\) nào mà \(k = 0\) thì không có đoạn con thỏa mãn

• Nếu \(k > cnt\) thì không có đoạn con thỏa mãn dù \(S\) có bao nhiêu chữ số \(1\)

• Ngược lại, với \(i_1 = 1\) cố định, ta luôn có cách chọn \(i_2\) phù hợp để nó có đúng \(x\) chữ số với \(x \leq cnt\)

• Từ nhận xét trên, ta giảm độ phức tạp còn \(O(1)\) cho việc kiểm tra

\(\color{goldenrod}{\text{Space Optimization}}\)

• Ta không cần lưu xâu \(S\) mà chỉ cần đếm số lượng chữ số \(1\) vào biến \(cnt\)

Dùng \(getchar()\) để nhận từng kí tự

\(\color{green}{\text{Preference AC Code }}\): Online Solving

\(^{^{\color{purple}{\text{Complexity : }} O(n + q)\ \color{purple}{\text{time}}\ ||\ O(1)\ \color{purple}{\text{memory}}}}\)

int main()
{
    int n; /// Số kí tự trong xâu S
    cin >> n;

    char c;
    while (c = getchar(), c != '0' && c != '1'); /// loại các kí tự không thuộc xâu $S$
    int cnt = (c == '1');          /// nhận phần tử dầu tiên
    for (int i = 1; i < n; ++i)    /// duyệt các phần tử còn lại
        cnt += (getchar() == '1'); /// tăng biến đếm nếu chữ số hiện tại là 1

    for (int q = readInt(); q--; ) /// Với mọi truy vấn
    {
        int k;
        cin >> k;

        if (k == 0 && cnt == n)     /// Không có đoạn con nào bằng 0
            puts("Luong Xiao Lin");
        else if (k > cnt)           /// Không có đoạn con nào đúng k số 1
            puts("Luong Xiao Lin");
        else                        /// Tồn tại đoạn con thỏa mãn
            puts("Ami Dep Trai");
    }
    return 0;
}