Cho dãy số nguyên A gồm N phần tử và số nguyên dương K (K <= N).

Hãy tìm giá trị tổng lớn nhất của một đoạn con liên tiếp có độ dài đúng bằng K.

Input:

• Dòng 1: Hai số nguyên N, K (1 <= K <= N <= 10^5).

• Dòng 2: N số nguyên A[i] (|A[i]| <= 10^9).

Output:

• Một số nguyên duy nhất là tổng lớn nhất tìm được.

Ví dụ 1:

Input:

5 3
2 1 5 1 3

Output:

9

Ví dụ 2:

Input:

4 2
-1 -2 -3 -4

Output:

-3

Cho dãy số nguyên A có N phần tử và số nguyên K. Hãy tìm giá trị trung bình cộng lớn nhất của K phần tử liên tiếp trong dãy. Giá trị trung bình của đoạn từ i đến i + K - 1 được tính bằng: (Ai + Ai+1 + ... + Ai+K-1)/K.

Input:

• Dòng đầu tiên chứa N và K (1 ≤ K ≤ N ≤ 10^5).

• Dòng thứ hai chứa N số nguyên A; (-10^4 ≤ Ai ≤ 10^4).

Output:

• In ra giá trị trung bình lớn nhất. Kết quả có thể là số thực (hệ thống chấm chấp nhận sai số 10^-5).

• Lưu ý khi code: Với C++, dùng fixed và setprecision(5) để in.

Gợi ý thuật toán: Về mặt toán học, vì K là hằng số dương, nên để Trung bình lớn nhất thì Tổng của K phần tử phải lớn nhất. Ta tìm tổng lớn nhất của cửa sổ K phần tử (Sliding Window), sau đó lấy tổng đó chia cho K (ép kiểu sang số thực).

Vi dụ:

Test 1:

Input:

4 4
1 12 -5 -6

Output:

0.50000

Test 1:

Input:

6 3
1 12 -5 -6 50 3

Output:

15.66667

Cho dãy số A và số nguyên K, S.

Hãy tìm vị trí bắt đầu (chỉ số tính từ 1) của đoạn con liên tiếp đầu tiên có độ dài K mà tổng của nó lớn hơn hoặc bằng S.

Nếu không có, in ra -1.

Input:

• Dòng 1: N, K, S (S <= 10^14).

• Dòng 2: N số nguyên A[i].

Output:

• Chỉ số bắt đầu của đoạn con tìm được hoặc -1.

Ví dụ 1:

Input:

5 3 10
1 2 3 6 1

Output:

2

Ví dụ 2:

Input:

4 2 100
10 20 30 40

Output:

-1

Cho dãy số nguyên dương A. Tìm tích lớn nhất của K phần tử liên tiếp.

Vì kết quả có thể rất lớn, hãy in ra phần dư của tích đó cho 10^9 + 7.

(Lưu ý: Bài toán yêu cầu tìm đoạn có tích thực tế lớn nhất, sau đó mới chia dư. Tuy nhiên để đơn giản cho mức độ cơ bản, giả sử dữ liệu đảm bảo tích không vượt quá long long hoặc chỉ yêu cầu tính tích modulo ngay từ đầu. Ở đây ta yêu cầu: Tìm tích lớn nhất modulo 10^9+7).

Input:

• Dòng 1: N, K.

• Dòng 2: N số nguyên dương A[i] (A[i] <= 100).

Output:

• Tích lớn nhất (modulo 10^9 + 7).

Ví dụ 1:

Input:

5 2
2 5 3 4 2

Output:

15

Ví dụ 2:

Input:

4 3
1 2 3 4

Output:

24

Cho dãy số A và số K.

Với mỗi cửa sổ trượt độ dài K (từ trái sang phải), hãy in ra số lượng các phần tử khác nhau (distinct elements) trong cửa sổ đó.

Input:

• Dòng 1: N, K.

• Dòng 2: N số nguyên A[i] (A[i] <= 10^5).

Output:

• In ra N - K + 1 số nguyên trên một dòng.

Ví dụ 1:

Input:

7 4
1 2 1 3 4 2 3

Output:

3 4 4 3

Ví dụ 2:

Input:

5 3
1 1 1 1 1

Output:

1 1 1

Cho dãy A, số K và số X.

Hãy đếm xem có bao nhiêu cửa sổ độ dài K mà trong đó số X xuất hiện ít nhất 1 lần.

Input:

• Dòng 1: N, K, X.

• Dòng 2: N số nguyên A[i].

Output:

• Số lượng cửa sổ thỏa mãn.

Ví dụ 1:

Input:

6 3 5
1 2 5 3 4 5

Output:

4

Ví dụ 2:

Input:

5 2 10
1 2 3 4 5

Output:

0

Kiểm tra xem có tồn tại hai cửa sổ độ dài K nào có tổng bằng nhau không?

In ra "YES" nếu có, "NO" nếu không.

Input:

• Dòng 1: N, K.

• Dòng 2: N số nguyên A[i].

Output:

• YES hoặc NO.

Ví dụ 1:

Input:

6 2
1 5 2 4 1 5

Output:

YES

Ví dụ 2:

Input:

5 3
1 2 3 4 5

Output:

NO

Cho chuỗi S chỉ gồm các chữ cái tiếng Anh thường và số nguyên K.

Hãy tìm số lượng nguyên âm (u, e, o, a, i) lớn nhất trong một chuỗi con liên tiếp độ dài K.

Input:

• Dòng 1: Chuỗi S (độ dài <= 10^5).

• Dòng 2: Số nguyên K.

Output:

• Số lượng nguyên âm lớn nhất.

Ví dụ 1:

Input:

abciiidef
3

Output:

3

Ví dụ 2:

Input:

hello
2

Output: 1

Cho dãy số A và số K.

Với mỗi cửa sổ trượt độ dài K, hãy tìm giá trị lớn nhất trong cửa sổ đó.

In ra N - K + 1 số nguyên.

Input:

• Dòng 1: N, K.

• Dòng 2: N số nguyên A[i].

Output:

• Dãy max của từng cửa sổ.

Ví dụ 1:

Input:

8 3
1 3 -1 -3 5 3 6 7

Output:

3 3 5 5 6 7

Ví dụ 2:

Input:

4 2
4 3 2 1

Output:

4 3 2

Cho dãy A và số K.

Hãy tìm một cửa sổ độ dài K sao cho (Max - Min) trong cửa sổ đó là lớn nhất.

In ra giá trị chênh lệch đó.

Input:

• Dòng 1: N, K.

• Dòng 2: N số nguyên A[i].

Output:

• Giá trị chênh lệch lớn nhất tìm được.

Ví dụ 1:

Input:

5 3
1 5 10 2 8

Output:

9

Ví dụ 2:

Input:

4 4
1 2 3 4

Output:

3

Cho một chuỗi ký tự S chỉ gồm các chữ cái tiếng Anh thường và hoa, chữ số và ký tự đặc biệt. Hãy tìm độ dài của chuỗi con liên tiếp dài nhất mà trong đó không có ký tự nào bị lặp lại.

Input:

• Một dòng duy nhất chứa chuỗi S (độ dài 1 ≤ len(S) ≤ 10^5).

Output:

• In ra một số nguyên là độ dài lớn nhất tìm được.

Gợi ý thuật toán: Sử dụng kỹ thuật Hai con trở (Two Pointers) hoặc Cửa sổ trượt co giãn.

• Dùng 2 biến (L (trái) và R (phải).

• Di chuyển R sang phải. Dùng một mảng đếm (hoặc Map) để kiểm tra ký tự S[R] đã xuất hiện trong đoạn [L, R] chưa.

• Nếu đã xuất hiện, tăng L lên để loại bỏ ký tự trùng lặp đó.

• Cập nhật độ dài max ans = max(ans, R - L + 1).

Ví dụ:

Test 1:

Input:

abcabcbb

Output:

3

Test 2:

Input:

pwwkew

Output:

3

Bạn sẽ được cung cấp một danh sách các số nguyên a[] và một số nguyên k duy nhất. Bạn cần chọn ra đúng k phần tử từ mảng a để tạo thành mảng a′ sao cho chỉ số không công bằng của a′ là nhỏ nhất. Chỉ số không công bằng của một mảng được tính như sau:

max(a') - min(a')

Ở đây:

• max biểu thị số nguyên lớn nhất trong mảng a'

• min biểu thị số nguyên nhỏ nhất trong mảng a'

Ví dụ a = [1,4,7,2], k = 2, chọn bất kỳ hai phần tử là [4, 7] thì chỉ số không công bằng = max([4,7]) - min([4,7]) = 7 - 4 = 3

Dữ liệu đầu vào gồm:

1. Dòng 1: Số nguyên n - số lượng phần tử của mảng

2. Dòng 2: Số nguyên k - số lượng phần tử phải chọn

3. Dòng 3 đến dòng (n + 2): Mỗi dòng chứa một số nguyên a[i] - phần tử của mảng

Dữ liệu đầu ra là: In ra một số nguyên duy nhất là chỉ số không công bằng nhỏ nhất có thể đạt được khi chọn k phần tử

max(a') - min (a')

Trong đó a' là mảng gồm k phần tử được chọn.

Ràng buộc:

2 <= n <= 10^5

2 <= k <= n

0 <= a[i] <= 10^9

Input 01:

10
4
1
2
3
4
10
20
30
40
100
200

Output 01:

3

Input 02:

7
3
10
100
300
200
1000
20
30

Output 02:

20

Cho một mảng A có N phần tử. Hãy tìm trung vị của dãy con liên tiếp cỡ K.

Trung vị là số ở chính giữa một dãy sau khi sắp xếp dãy đó.

Ràng buộc: ~1 \leq K \leq N \leq 2.10^5~; ~0 \leq A[i] \leq 10^9~

Input 01:

8 2
7 6 6 2 9 6 2 7

Output 01:

6 6 2 2 6 2 2

Input 02:

6 1
7 2 9 2 4 6

Output 02:

7 2 9 2 4 6