Ôn tập thi TS10 Chuyên tin 2026 -- Đề số 3 - Bộ đề bài

#	Bài tập	Điểm	Thời gian:	Giới hạn bộ nhớ
1	SHORTEN	30 (p)	2.0s	1G
2	COVER	30 (p)	2.0s	1G
3	Ghép cặp đối xứng	20 (p)	3.5s	1G
4	COUNTPAIR	20 (p)	5.0s	1G

1. SHORTEN

Điểm: 30 (p) Thời gian: 2.0s Bộ nhớ: 1G Input: SHORTEN.inp Output: SHORTEN.out

Cho \(n\) từ. Với mỗi từ:

Nếu độ dài của từ không quá \(10\), in nguyên từ đó.
Nếu độ dài của từ lớn hơn \(10\), hãy rút gọn từ theo dạng: ký tự đầu + số lượng ký tự ở giữa + ký tự cuối.

Ví dụ: từ có độ dài \(14\) thì số ký tự ở giữa là \(12\).

Input

Dòng đầu tiên chứa số nguyên \(n\).
\(n\) dòng tiếp theo, mỗi dòng chứa một xâu \(s_i\).

Output

In ra \(n\) dòng, dòng thứ \(i\) là dạng sau khi xử lý của từ \(s_i\).

Constraints

\(1 \le n \le 100\).
\(1 \le |s_i| \le 100\).
Các xâu chỉ gồm chữ cái tiếng Anh in thường.

Scoring

Subtask \(1\) (\(30\%\) số điểm): \(n = 1\) và \(|s_i| \le 10\).
Subtask \(2\) (\(30\%\) số điểm): \(n \le 10\) và \(|s_i| \le 20\).
Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input

5
hello
algorithm
competitive
xxxxxxxxxxx
transformation

Output

hello
algorithm
c9e
x9x
t12n

Note

Các từ có độ dài lớn hơn \(10\) được rút gọn theo ký tự đầu, số ký tự ở giữa và ký tự cuối.

2. COVER

Điểm: 30 (p) Thời gian: 2.0s Bộ nhớ: 1G Input: COVER.inp Output: COVER.out

Có \(n\) thời điểm bắt đầu \(a_1, a_2, \dots, a_n\), được sắp xếp tăng dần.

Ta chọn một số nguyên dương \(k\). Với mỗi thời điểm \(a_i\), nó tạo ra một đoạn thời gian: \([a_i, a_i + k - 1]\).

Mỗi đoạn trên phủ đúng \(k\) thời điểm nguyên liên tiếp. Tổng số thời điểm được phủ là số lượng thời điểm nguyên thuộc ít nhất một trong các đoạn đã cho. Nếu các đoạn giao nhau thì phần giao chỉ được tính một lần.

Hãy tìm giá trị nhỏ nhất của \(k\) sao cho tổng số thời điểm được phủ ít nhất là \(h\).

Input

Dòng đầu tiên chứa số nguyên \(T\) - số lượng bộ test.
Mỗi bộ test gồm:
- Một dòng chứa hai số nguyên \(n\) và \(h\).
- Một dòng chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\).

Output

Với mỗi bộ test, in ra một dòng chứa giá trị nhỏ nhất của \(k\) tìm được.

Constraints

\(1 \le T \le 1000\).
\(1 \le n \le 2 \cdot 10^5\).
Tổng \(n\) trên tất cả các bộ test không vượt quá \(2 \cdot 10^5\).
\(1 \le h \le 10^{18}\).
\(1 \le a_1 < a_2 < \dots < a_n \le 10^9\).

Subtask

Subtask 1 (20% số điểm): \(n = 1\).
Subtask 2 (30% số điểm): \(h \le 10^5, a_i \le 10^5\) và tổng \(n\) trên tất cả các bộ test không vượt quá \(5000\).
Subtask 3 (30% số điểm): Tổng \(n\) trên tất cả các bộ test không vượt quá \(5000\).
Subtask 4 (20% số điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input

Output

4
7
5

Note

Ở bộ test đầu tiên, nếu \(k = 4\), các đoạn là \([1, 4], [4, 7], [10, 13]\). Tổng số thời điểm nguyên được phủ là \(11\) (các điểm \(\{1, 2, 3, 4, 5, 6, 7, 10, 11, 12, 13\}\)), đủ lớn hơn hoặc bằng \(10\). Nếu \(k = 3\), tổng số thời điểm nguyên được phủ chỉ là \(9\), chưa đủ.

3. Ghép cặp đối xứng

Điểm: 20 (p) Thời gian: 3.5s Bộ nhớ: 1G Input: PAIRING.inp Output: PAIRING.out

Một xâu được gọi là đối xứng được nếu ta có thể sắp xếp lại các ký tự của xâu đó để tạo thành một xâu palindrome.

Ví dụ:

Xâu aabb đối xứng được, vì có thể sắp xếp thành abba.
Xâu abc không đối xứng được.

Cho \(n\) xâu \(s_1, s_2, \dots, s_n\). Hãy đếm số cặp chỉ số \((i, j)\) sao cho \(1 \le i < j \le n\) và xâu \(s_i + s_j\) là xâu đối xứng được. Ở đây \(s_i + s_j\) là xâu tạo được bằng cách nối \(s_i\) với \(s_j\).

Input

Dòng đầu tiên chứa số nguyên \(n\).
\(n\) dòng tiếp theo, dòng thứ \(i\) chứa xâu \(s_i\).

Output

In ra một số nguyên duy nhất là số cặp thỏa mãn.

Constraints

\(1 \le n \le 10^5\).
Tổng độ dài của tất cả các xâu không vượt quá \(10^6\).
Các xâu chỉ gồm chữ cái tiếng Anh in thường từ a đến z.

Scoring

Subtask \(1\) (\(30\%\) số điểm): \(n \le 200\).
Subtask \(2\) (\(30\%\) số điểm): \(n \le 5000\).
Subtask \(3\) (\(20\%\) số điểm): Các xâu chỉ gồm các chữ cái từ a đến j.
Subtask \(4\) (\(20\%\) số điểm): Không có giới hạn gì thêm.

Example

Test 1

Input

6
ab
ba
abc
c
aa
bb

Output

Note

Các cặp hợp lệ là (ab, ba), (ab, abc), (ba, abc), (c, aa), (c, bb) và (aa, bb).
Ví dụ: ab + ba = abba là một xâu palindrome.

4. COUNTPAIR

Điểm: 20 (p) Thời gian: 5.0s Bộ nhớ: 1G Input: COUNTPAIR.inp Output: COUNTPAIR.out

Cho dãy số nguyên \(a_1, a_2, \dots, a_n\).

Với mỗi vị trí \(i\), định nghĩa \(L_i\) là số lần giá trị \(a_i\) xuất hiện trong đoạn \(a_1, a_2, \dots, a_i\). Nói cách khác, \(L_i\) là số lần xuất hiện của \(a_i\) tính từ đầu dãy đến vị trí \(i\).

Tương tự, với mỗi vị trí \(i\), định nghĩa \(R_i\) là số lần giá trị \(a_i\) xuất hiện trong đoạn \(a_i, a_{i+1}, \dots, a_n\). Nói cách khác, \(R_i\) là số lần xuất hiện của \(a_i\) tính từ vị trí \(i\) đến cuối dãy.

Hãy đếm số cặp chỉ số \((i, j)\) sao cho \(1 \le i < j \le n\) và \(L_i > R_j\).

Input

Dòng đầu tiên chứa số nguyên dương \(n\).
Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\).

Output

Một dòng duy nhất chứa số cặp chỉ số \((i, j)\) thỏa mãn yêu cầu.

Constraints

\(1 \le n \le 10^6\).
\(1 \le a_i \le 10^9\).

Subtask

Subtask \(1\) (\(30\%\) số điểm): \(n \le 200\).
Subtask \(2\) (\(30\%\) số điểm): \(n \le 5000\).
Subtask \(3\) (\(20\%\) số điểm): \(a_i \le 10^5\).
Subtask \(4\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input

7
1 2 1 1 2 2 1

Output

Note

Có \(8\) cặp chỉ số \((i, j)\) thỏa mãn \(1 \le i < j \le n\) và \(L_i > R_j\).

Test 2

Input

3
1 1 1

Output

Note

Chỉ có một cặp chỉ số thỏa mãn yêu cầu.

Test 3

Input

5
1 2 3 4 5

Output

Note

Không có cặp chỉ số nào thỏa mãn yêu cầu.