Lớp B 2026 - Contest #7 - Luyện tập

Cho dãy số nguyên dương gồm \(N\) phần tử \(a_1,a_2,...,a_N\). Với mỗi chỉ số \(1 \le i \le N\) đếm xem có bao nhiêu phần tử bé hơn \(a_i\).

Input

• Dòng đầu tiên gồm số nguyên dương \(N\) \((2 \le N \le 10^5)\)
• Dòng thứ hai gồm \(N\) số nguyên dương \(a_1,a_2,...,a_N\) \((a_i \le 10^9)\)

Output

• In ra \(N\) số nguyên, số thứ \(i\) cho biết số phần tử nhỏ hơn \(a_i\).

Example

5
3 2 1 1 2

4 2 0 0 2 

Một xưởng có \(n\) máy có thể được sử dụng để làm sản phẩm. Mục tiêu của bạn là tạo ra tổng cộng \(t\) sản phẩm.

Đối với mỗi máy, bạn biết số giây cần thiết để tạo ra một sản phẩm duy nhất. Các máy có thể hoạt động đồng thời, và bạn có thể tự do quyết định lịch trình của chúng.

Thời gian cần thiết ngắn nhất để tạo ra \(t\) sản phẩm là bao nhiêu?

Input

• Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(t\) (\(1 \le n \le 2 \times 10^5\), \(1 \le t \le 10^9\)): số lượng máy và sản phẩm.

• Dòng tiếp theo có \(n\) số nguyên \(k_1,k_2,\ldots,k_n\) (\(1 \le k_i \le 10^9\)): thời gian cần thiết để tạo ra một sản phẩm bằng mỗi máy.

Output

• In một số nguyên: thời gian tối thiểu cần thiết để tạo ra \(t\) sản phẩm.

Example

3 7
3 2 5

8

Scoring

\begin itemize

• Có 15% số điểm ứng với \(k_i=1\).
• Có 15% số điểm ứng với \(t=1\).
• 70% số điểm còn lại không có ràng buộc gì thêm.
  \end itemize

Trong cuộc thi "Học sinh tài năng" được tổ chức tại một trường học, ban tổ chức chuẩn bị một bảng điểm điện tử để hiển thị điểm số của từng thí sinh. Điểm số cua \(n\) thí sinh được hiển thị theo thứ tự từ thí sinh \(1\) đến thí sinh \(n,\) sau đó lặp lại vô hạn lần. Cụ thể, sau khi hiển thị điểm của thí sinh \(n\), bảng điểm sẽ quay lại hiển thị điểm của thí sinh \(1\) rồi thí sinh \(2\), và cứ thế không ngừng.

Yêu cầu: Hãy giúp ban tổ chức tính tổng \(k\) điểm số liên tiếp xuất hiện trên bảng điểm, bắt đầu từ vị trí \(p\).

Input

• Dòng thứ nhất chứa ba số nguyên dương \(n, k, p\) lần lượt là số thí sinh trong cuộc thi, số lượng điểm số cần tính và vị trí bắt đầu tính điểm trên bảng điện tử.
• Dòng thứ hai ghi \(n\) số nguyên dương \(a_1, a_2, ..., a_n\) \((1 \le a_i \le 10^9)\)

Output

• In ra một số nguyên duy nhất là kết quả của bài toán chia lấy dư cho \(10^9+7\).

Example

6 7 3
4 3 6 2 9 5

35

Scoring

• Có \(40\%\) số test với \(n \le 10^3; p = 1; k \le n\).
• Có \(30\%\) số test với \(n \le 10^3; p, k \le 10^6\).
• Có \(30\%\) số test với \(n \le 10^6; p, k \le 10^{18}\).

Trong kỳ thi lập trình thuộc Trại hè miền Trung --- Tây Nguyên 2023, diễn ra tại trường THPT chuyên Lê Quý Đôn (Bình Định), Ban tổ chức đã chuẩn bị một phần thưởng vô cùng dễ thương: một chú gấu bông xinh xắn sẽ thuộc về nhà vô địch!

Tuy nhiên, vẫn còn một việc nhỏ cần giải quyết: làm sao để đặt tên cho chú gấu này?

Một cái tên ý nghĩa nên được lấy cảm hứng từ chủ đề của kỳ thi --- là một xâu ký tự chỉ gồm chữ cái thường trong bảng chữ cái tiếng Anh, độ dài \(n\). Ban tổ chức mong muốn chọn một xâu con (substring) liên tiếp trong xâu chủ đề để làm tên cho chú gấu. Tuy nhiên, để cái tên thật đa dạng, xâu con đó cần phải chứa ít nhất \(k\) ký tự phân biệt.

Nhiệm vụ của bạn là: hãy đếm xem có bao nhiêu cách chọn xâu con khác nhau (về chỉ số bắt đầu hoặc kết thúc) từ xâu chủ đề mà thỏa mãn điều kiện có ít nhất \(k\) ký tự khác nhau.

Input

• Dòng đầu chứa hai số nguyên dương \(n\) và \(k\) \((n \leq 10^6, k \leq 26)\).
• Dòng thứ hai là xâu \(s\).

Output

• In ra một số nguyên không âm --- là số lượng xâu con thỏa mãn yêu cầu đề bài.

Example

7 2
abcabac

21

Scoring

• Subtask 1 (16% điểm): \(k = 1\)
• Subtask 2 (22% điểm): \(k = 2\)
• Subtask 3 (18% điểm): \(n \le 10^2\)
• Subtask 4 (24% điểm): \(n \le 10^4\)
• Subtask 5 (20% điểm): Không giới hạn gì thêm.