Ôn tập thi TS10 Chuyên tin 2026 -- Đề số 2

Có \(N\) học sinh. Cần xếp tất cả \(N\) học sinh này thành các hàng sao cho số lượng học sinh ở mỗi hàng đều bằng nhau.

Ban tổ chức quy định: Số lượng hàng không được lớn hơn số học sinh của một hàng. Hỏi có thể xếp được nhiều nhất bao nhiêu hàng?

Input

• Một dòng duy nhất chứa số nguyên dương \(N\) (\(1 \le N \le 10^{12}\)).

Output

• In ra một số nguyên duy nhất là số hàng nhiều nhất tìm được.

Example

12

3

16

4

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(N \le 10^6\).
• Subtask \(2\) (\(50\%\) số điểm): \(N \le 10^{12}\).

Cho một dãy gồm \(N\) số nguyên dương \(A_1, A_2, \dots, A_N\). Một đoạn con (liên tiếp) của dãy được gọi là hợp lệ nếu số lượng giá trị phân biệt xuất hiện trong đoạn con đó không vượt quá \(K\).

Yêu cầu: Hãy tìm độ dài của đoạn con hợp lệ dài nhất.

Input

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\) (\(1 \le N, K \le 10^5\)).
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \dots, A_N\) (\(1 \le A_i \le 10^5\)).

Output

• In ra một số nguyên duy nhất là độ dài của đoạn con hợp lệ dài nhất.

Example

7 2
3 1 1 2 1 2 4

5

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(N \le 100\).
• Subtask \(2\) (\(20\%\) số điểm): \(N \le 1000\).
• Subtask \(3\) (\(30\%\) số điểm): \(K = 1\).
• Subtask \(4\) (\(30\%\) số điểm): Không có ràng buộc gì thêm.

Có \(N\) công việc cần xử lý. Công việc thứ \(i\) (\(1 \le i \le N\)) yêu cầu dùng \(T_i\) ngày để thực hiện và có hạn chót vào ngày \(D_i\).

Bạn bắt đầu làm việc từ ngày \(0\) và tại mỗi thời điểm chỉ có thể làm duy nhất một công việc. Bạn có quyền chọn làm hoặc bỏ qua bất kỳ công việc nào, cũng như tự quyết định thứ tự thực hiện các công việc đã chọn. Một công việc được xem là hoàn thành đúng hạn nếu tổng số ngày làm việc, tính từ ngày \(0\) cho đến khi làm xong công việc đó, không vượt quá hạn chót.

Yêu cầu: Hãy tính số lượng công việc lớn nhất mà bạn có thể hoàn thành đúng hạn.

Input

• Dòng đầu tiên chứa số nguyên dương \(N\) (\(1 \le N \le 10^5\)).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên dương \(T_i\) và \(D_i\) (\(1 \le T_i, D_i \le 10^9\)) mô tả thời gian cần thiết và hạn chót của công việc thứ \(i\).

Output

• In ra một số nguyên duy nhất là số lượng công việc tối đa hoàn thành đúng hạn.

Example

4
2 5
4 6
3 6
2 7

3

Scoring

• Subtask \(1\) (\(15\%\) số điểm): \(N \le 20\).
• Subtask \(2\) (\(20\%\) số điểm): \(N \le 2000\).
• Subtask \(3\) (\(30\%\) số điểm): \(N \le 10^5\) và thời gian làm mọi công việc đều bằng nhau (\(T_i = 1\) với mọi \(i\)).
• Subtask \(4\) (\(35\%\) số điểm): Không có ràng buộc gì thêm.

Một xâu ký tự được gọi là xâu đối xứng (Palindrome) nếu nó đọc từ trái sang phải hay từ phải sang trái đều giống hệt nhau (ví dụ: madam, racecar).

Ta định nghĩa rằng: Một xâu ký tự được gọi là xâu tiềm năng nếu ta có thể sắp xếp lại (hoán vị) các ký tự của nó để tạo thành một xâu đối xứng. Ví dụ, xâu aabcb là xâu tiềm năng vì có thể hoán vị thành bacab.

Yêu cầu: Cho một xâu \(S\) độ dài \(N\) chỉ gồm các chữ cái in thường tiếng Anh. Hãy đếm số lượng đoạn con liên tiếp của \(S\) là xâu tiềm năng.

Lưu ý: Hai chuỗi con có cùng giá trị nhưng nằm ở vị trí khác nhau được tính là hai đoạn con riêng biệt.

Input

• Một dòng duy nhất chứa xâu ký tự \(S\) (\(1 \leq N \leq 10^5\)).

Output

• In ra một số nguyên duy nhất là số lượng đoạn con liên tiếp của \(S\) thỏa mãn điều kiện.

Example

aabcb

8

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(N \leq 300\).
• Subtask \(2\) (\(20\%\) số điểm): \(N \leq 3000\).
• Subtask \(3\) (\(20\%\) số điểm): Xâu \(S\) chỉ gồm hai chữ cái a và b.
• Subtask \(4\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.