Học sinh giỏi lớp 9 của Đà Năng 2024

Cho dãy số nguyên dương có \(N\) phần tử và một chỉ số \(K\).

Yêu cầu: Hãy tính tổng \(K\) phần tử lớn nhất trong dãy số nguyên dương đã cho.

Input

• Dòng \(1\): chứa hai số nguyên \(N, K\).
• Dòng \(2\): chứa \(N\) số nguyên dương lần lượt là các giá trị của các phần tử trong dãy số.

Output

• Ghi ra một số nguyên duy nhất là kết quả tìm được.

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(K = 2, N \leq 10\).
• Subtask \(2\) (\(30\%\) số điểm): \(K = 3, N \leq 100\).
• Subtask \(3\) (\(30\%\) số điểm): \(N \leq 10^5\).

Example

10 3
1 2 3 4 5 6 7 8 9 10

27

Nhân dịp tết cổ truyền Đức và Nhi được bố mẹ cho rất nhiều kẹo, vì được nghỉ học nên Đức và Nhi bày ra một trò chơi như sau. Hai bạn chơi oẳn tù tì với nhau, ai thắng có thể lấy 1 viên kẹo, để ghi lại kết quả Đức sử dụng các kí tự để ghi chú, nếu Đức thắng sẽ dùng kí tự \(D\) nếu Nhi thắng sẽ dùng kí tự \(N\), nếu hòa sẽ dùng kí tự \(H\).

Yêu cầu: Hãy cho biết số lượng kẹo của Đức và Nhi là bao nhiêu sau khi kết thúc trò chơi.

Input

Đọc từ file văn bản GAME.INP chuối kí tự dùng để ghi lại kết quả trò chơi.

Output

Ghi ra file văn bản GAME.OUT 2 số nguyên lần lượt là số kẹo của Đức và Nhi.

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(|S| \leq 200\).
• Subtask \(2\) (\(60\%\) số điểm): \(|S| \leq 10^3\).

Example

HDNDNNNDDNN

4 6

Tóm tắt: Cho mảng số nguyên \(A\) có \(N\) phần tử và một số nguyên dương \(K\).

Yêu cầu: Hãy đếm số đoạn con liên tiếp có đúng \(K\) số lẻ.

Input

Đọc từ file văn bản CHUMDEN.INP:

• Dòng 1 chứa \(N, K\), \((1 \leq K \leq N \leq 10^6)\)
• Dòng 2 chứa các số nguyên của mảng \(A\), \((1 \leq A_i \leq 10^6)\).

Output

Ghi ra file văn bản CHUMDEN.OUT một số nguyên duy nhất là kết quả bài toán.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N \leq 100\).
• Subtask \(2\) (\(30\%\) số điểm): \(N \leq 5 \times 10^3\).
• Subtask \(2\) (\(40\%\) số điểm): không có ràng buộc gì thêm.

Example

4 2
1 3 2 3

3

Tóm tắt: Cho dãy số nguyên \(A\) độ dài \(N\).

Yêu cầu: Hãy tìm cách xóa đi ít phần tử nhất sao cho phần còn lại là một dãy tăng.

Input

Đọc từ file văn bản TANGQUA.INP:

• Dòng 1 chứa \(N\), \((1 \leq N \leq 10^5)\)
• Dòng 2 chứa các số nguyên của mảng \(A\), \((1 \leq A_i \leq 10^9)\).

Output

Ghi ra file văn bản TANGQUA.OUT một số nguyên duy nhất là kết quả bài toán.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N \leq 100\).
• Subtask \(2\) (\(30\%\) số điểm): \(N \leq 5 \times 10^3\).
• Subtask \(2\) (\(40\%\) số điểm): không có ràng buộc gì thêm.

Example

5
1 3 3 2 8

2