Thi thử TS10 SQRT lần 4 năm 2026

Có một hành lang, trên hành lang đó có \(n\) căn phòng, ban đầu có một học sinh đang đứng ở một căn phòng thứ \(x\) và học sinh đó muốn thực hiện một loạt các di chuyển để đi đến căn phòng thứ \(y\).

Cụ thể, chuỗi di chuyển của học sinh này được mô tả bằng một xâu có \(m\) kí tự chỉ bao gồm L và R, mỗi kí tự mô tả cho một hành động của học sinh đó, nếu nó là L thì có nghĩa học sinh đã đi từ phòng hiện tại đến phòng kế trước đó, nếu là R thì có nghĩa học sinh đã đi từ phòng hiện tại đến phòng kế tiếp đó. Một cách cụ thể, nếu căn phòng hiện tại học sinh đang ở là phòng thứ \(i\) thì nếu hành động là L, học sinh sẽ đến căn phòng \(i - 1\), ngược lại, học sinh đến căn phòng \(i + 1\).

Ngoài ra, vì hai đầu của hành lang bị chặn, nên nếu học sinh đang ở căn phòng thứ nhất, hành động L sẽ không thể xảy ra, tương tự, nếu căn phòng hiện tại học sinh đang ở là \(n\) thì hành động R sẽ không thể xảy ra.

Yêu cầu: Bạn được biết chuỗi hành động của học sinh, hãy đếm số lượng cặp căn phòng \(x\) và \(y\) mà với chuỗi hành động đó, học sinh có thể đi từ căn phòng thứ \(x\) đến căn phòng \(y\) mà không có hành động nào không thể xảy ra.

Input

• Dòng đầu tiên gồm hai số nguyên \(n\) và \(m\) (\(1 \le n, m \le 10^5\)).
• Dòng thứ hai gồm một xâu kí tự độ dài \(m\) chỉ bao gồm L và R mô tả chuỗi hành động của học sinh.

Output

• Gồm một dòng duy nhất chứa kết quả bài toán.

Scoring

• \(50\%\) số điểm của bài có dữ liệu thỏa mãn: \(n, m \le 100\).
• \(30\%\) số điểm của bài có dữ liệu thỏa mãn: \(n, m \le 1000\).
• \(20\%\) số điểm còn lại của bài không có ràng buộc gì thêm.

Example

5 3
LRL

4

3 2
LL

1

Cho một xâu kí tự \(s\) chỉ bao gồm các kí tự latin thường và kí tự số. Ta định nghĩa trọng số của một xâu kí tự \(t\) như sau:

• Gọi \(x\) là tổng các chữ số trong \(t\).
• Gọi \(y\) là tổng giá trị của các chữ cái trong \(t\). Ta định nghĩa giá trị của một chữ cái là vị trí của nó trong bảng chữ cái alphabet:
  • Kí tự a có giá trị là \(1\).
  • Kí tự b có giá trị là \(2\).
  • Kí tự c có giá trị là \(3\).
  • ...
  • Kí tự z có giá trị là \(26\).
• Khi đó, trọng số của xâu kí tự \(t\) là \(x - y\).

Một vài ví dụ cho trọng số của một xâu kí tự:

• Trọng số của xâu abc123 là \(x - y = (1 + 2 + 3) - (1 + 2 + 3) = 0\).
• Trọng số của xâu 11i là \(x - y = (1 + 1) - (9) = -7\).

Yêu cầu: Bạn hãy tìm trọng số lớn nhất của một xâu con bất kì (có thể rỗng) của xâu \(s\).

Input

• Gồm một dòng duy nhất chứa xâu kí tự \(s\). Độ dài của xâu \(s\) không quá \(10^6\).

Output

• Gồm một dòng duy nhất chứa kết quả bài toán: trọng số lớn nhất của một xâu con liên tiếp trong xâu \(s\).

Example

11ilqd

2

a1w59

14

Scoring

• \(30\%\) số điểm của bài có độ dài của xâu \(s\) không quá \(100\).
• \(30\%\) số điểm của bài có độ dài của xâu \(s\) không quá \(1000\).
• \(40\%\) số điểm còn lại của bài không có ràng buộc gì thêm.

Thời khóa biểu của học sinh trường THPT Chuyên Lê Quý Đôn có những tiết học chuyên sâu. Để chuẩn bị cho kì thi HSG sắp tới, thầy giáo chủ nhiệm muốn thực hiện sắp xếp lại thời khóa biểu nhằm dồn các tiết học chuyên sâu lại liên tiếp nhau để các thành viên lớp 11 Tin có thể tập trung ôn luyện.

Một cách cụ thể, thời khóa biểu của lớp 11 Tin gồm có \(n\) tiết học, các tiết học được đánh số thứ tự từ \(1\) đến \(n\) và mỗi tiết thứ \(i\) (\(1 \le i \le n\)) sẽ có mã số \(a_i\). Với một tiết học thứ \(i\), nếu \(a_i\) là một số nguyên tố thì tiết học đó là một tiết học chuyên sâu, ngược lại, đó là một tiết học các môn văn hóa khác.

Để đổi chỗ hai tiết học thứ \(i\) và \(j\), thầy giáo phải tốn \(|i - j|\) công sức. Thầy muốn tối thiểu hóa công sức sắp xếp mà vẫn có thể chuyển các tiết học chuyên sâu nằm liên tiếp nhau trên thời khóa biểu.

Yêu cầu: Bạn hãy lập trình giúp thầy giáo tính toán công sức nhỏ nhất phải bỏ ra để sắp xếp lại thời khóa biểu nhé.

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) – số lượng tiết học (\(1 \le n \le 10^5\)).
• Dòng thứ hai chứa mã số của các tiết học: \(a_1, a_2, \dots, a_n\) (\(1 \le a_1, a_2, \dots, a_n \le 10^8\)).

Output

• Gồm một dòng duy nhất chứa kết quả bài toán: công sức ít nhất mà thầy giáo chủ nhiệm phải bỏ ra.

Example

3
2 1 2

1

5
2 3 1 5 7

2

Scoring

• \(30\%\) số điểm của bài có dữ liệu thỏa mãn: \(n \le 100\).
• \(30\%\) số điểm của bài có dữ liệu thỏa mãn: \(n \le 1000\).
• \(30\%\) số điểm của bài có dữ liệu thỏa mãn: \(a_1, a_2, \dots, a_n \le 10^5\).
• \(10\%\) số điểm còn lại của bài không có ràng buộc gì thêm.

Cho dãy \(a\) gồm \(n\) phần tử được đánh số thứ tự từ \(1\) đến \(n\). Giá trị của phần tử thứ \(i\) là \(a_i\).

Một cách chọn các cặp phần tử không giao nhau là một cách chọn các cặp sao cho không có phần tử nào thuộc nhiều hơn một cặp.

Yêu cầu: Bạn cần tìm ra cách chọn ra \(k\) cặp phần tử không giao nhau sao cho tổng chênh lệch của giá trị hai phần tử trong một cặp là bé nhất.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n\) và \(k\) — số lượng phần tử của dãy \(a\) và số lượng cặp cần phải chọn (\(2 \cdot k \leq n \leq 10^5\)).
• Dòng thứ hai chứa giá trị của các phần tử trong dãy \(a\): \(a_1, a_2, \dots, a_n\) (\(1 \leq a_1, a_2, \dots, a_n \leq 10^9\)).

Output

• Gồm một dòng duy nhất chứa kết quả bài toán: tổng chênh lệch giá trị bé nhất của \(k\) cặp phần tử.

Example

5 2
1 2 3 4 5

2

5 1
1 3 5 7 9

2

Scoring

• \(30\%\) số điểm của bài có dữ liệu thỏa mãn: \(n \leq 100\).
• \(30\%\) số điểm của bài có dữ liệu thỏa mãn: \(n \leq 1000\).
• \(30\%\) số điểm của bài có dữ liệu thỏa mãn: \(a_1, a_2, \dots, a_n \leq 100\).
• \(10\%\) số điểm còn lại của bài không có ràng buộc gì thêm.