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

Bộ đề bài

Trở lại kỳ thi
# Bài tập Điểm Thời gian: Giới hạn bộ nhớ
1 Bài 1: Khuyến mãi 25 (p) 0.5s 512M
2 Bài 2: Điểm du lịch 25 (p) 1.0s 512M
3 Bài 3: Trưng bày 25 (p) 0.8s 512M
4 Bài 4: Đoạn ổn định 25 (p) 0.5s 512M

1. Bài 1: Khuyến mãi

Điểm: 25 (p) Thời gian: 0.5s Bộ nhớ: 512M Input: PROMO.INP Output: PROMO.OUT

Để chuẩn bị cho năm học mới, Bảo cần ít nhất \(N\) quyển vở. Khi đến cửa hàng văn phòng phẩm, Bảo thấy đang có chương trình khuyến mãi vô cùng hấp dẫn: Cứ mua \(K\) quyển vở thì khách hàng sẽ được tặng thêm \(1\) quyển vở miễn phí. Biết rằng giá bán lẻ của mỗi quyển vở là \(P\) đồng.

Yêu cầu: Hãy tính số tiền ít nhất mà Bảo cần chuẩn bị để có được từ \(N\) quyển vở trở lên.

Input

  • Gồm một dòng duy nhất chứa ba số nguyên dương \(N, K, P\).

Output

  • In ra một số nguyên duy nhất là số tiền ít nhất Bảo cần trả để có đủ vở.

Constraints

  • \(1 \le K \le N \le 10^{12}\)
  • \(1 \le P \le 10^6\)

Scoring

  • Subtask \(1\) (\(50\%\) số điểm): \(N, K \le 10^4\).
  • Subtask \(2\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input 
10 3 5000
Output 
40000
Note

Để có \(10\) quyển vở, Bảo sẽ mua \(8\) quyển và được tặng \(2\) quyển. Tổng số tiền phải trả: \(8 \cdot 5000 = 40000\) (đồng).

Test 2

Input 
5 5 10000
Output 
50000
Note

Bảo phải mua \(5\) quyển vở với giá tiền: \(5 \cdot 10000 = 50000\) (đồng).

2. Bài 2: Điểm du lịch

Điểm: 25 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: TOUR.INP Output: TOUR.OUT

Trên đường Mân Thái có \(N\) trạm dừng chân. Trạm thứ \(i\) có điểm cảnh quan là \(A_i\). Trí muốn chọn hai trạm \(i\) và \(j\) (\(i < j\)) để tham quan. Chỉ số trải nghiệm được tính bằng tổng điểm cảnh quan của hai trạm trừ đi khoảng cách giữa chúng, theo công thức:

\[f(i, j) = A_i + A_j - (j - i)\]

Yêu cầu: Giúp Trí chọn hai trạm dừng chân \(i, j\) sao cho chỉ số trải nghiệm \(f(i, j)\) đạt giá trị lớn nhất.

Input

  • Dòng đầu tiên chứa số nguyên dương \(N\) (\(2 \le N \le 2 \cdot 10^5\)).
  • Dòng thứ hai chứa \(N\) số nguyên dương \(A_1, A_2, \dots, A_N\) (\(1 \le A_i \le 10^9\)).

Output

  • In ra hai số nguyên \(1 \le i < j \le N\) mà \(f(i, j)\) lớn nhất.
  • Nếu tồn tại nhiều cặp \((i, j)\) khác nhau có cùng giá trị \(f(i, j)\) lớn nhất, bạn có thể in ra bất kỳ cặp nào trong số đó.

Example

Test 1

Input 
5
8 1 9 4 2
Output 
1 3
Note

Trạm \(1\) được \(8\) điểm và trạm \(3\) được \(9\) điểm. Khoảng cách \(= 3 - 1 = 2\). Điểm trải nghiệm \(= 8 + 9 - 2 = 15\).

Scoring

  • Subtask \(1\) (\(30\%\) số điểm): \(N \le 5000\).
  • Subtask \(2\) (\(30\%\) số điểm): \(A_i = A_1\) với mọi \(i\).
  • Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.

3. Bài 3: Trưng bày

Điểm: 25 (p) Thời gian: 0.8s Bộ nhớ: 512M Input: SHELF.INP Output: SHELF.OUT

Tại Hội chợ triển lãm Đà Nẵng 2026, Linh quản lý một kệ trưng bày gồm \(N\) món đồ lưu niệm xếp thành hàng ngang. Đánh số thứ tự \(1, 2, \dots, N\) cho các món đồ từ trái sang phải; món thứ \(i\) có độ bắt mắt là số nguyên dương \(A_i\).

Để tối ưu không gian, Linh quyết định cất đi tối đa \(K\) món đồ. Các món đồ còn lại được dồn sát vào nhau và giữ nguyên thứ tự ban đầu để tạo thành dãy trưng bày mới.

Yêu cầu: Hãy giúp Linh chọn cất đi không quá \(K\) món đồ sao cho dãy các độ bắt mắt còn lại đạt thứ tự từ điển lớn nhất.

Nhắc lại: Quy tắc so sánh thứ tự từ điển giữa hai dãy số \(a\) và \(b\): Ta so sánh \(a_j\) với \(b_j\) tại vị trí \(j\) đầu tiên mà \(a_j \neq b_j\) khi xét \(j\) từ trái sang phải – dãy nào có giá trị lớn hơn sẽ lớn hơn. Ví dụ: dãy \((4, 3, 5)\) lớn hơn dãy \((4, 3, 1)\). Nếu không tìm thấy vị trí khác biệt nào – tức một dãy là tiền tố của dãy kia, dãy dài hơn sẽ được xem là lớn hơn. Ví dụ: dãy \((9, 8, 7)\) lớn hơn dãy \((9, 8)\).

Input

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

Output

  • In ra một dòng chứa độ bắt mắt của các món đồ trong dãy trưng bày tối ưu nhất, các số cách nhau một khoảng trắng.

Example

Test 1

Input 
5 2
3 1 5 2 4
Output 
5 2 4
Note

Phương án tối ưu: Cất món số 1 và món số 2.

Test 2

Input 
3 2
9 1 2
Output 
9 2
Note

Dãy này có thứ tự từ điển lớn hơn dãy \((9, 1)\) và \((9)\).

Scoring

  • Subtask \(1\) (\(30\%\) số điểm): \(N \leq 20\).
  • Subtask \(2\) (\(30\%\) số điểm): \(N \leq 2000\).
  • Subtask \(3\) (\(15\%\) số điểm): Các phần tử trong dãy \(A\) đôi một khác nhau.
  • Subtask \(4\) (\(25\%\) số điểm): Không có ràng buộc gì thêm.

4. Bài 4: Đoạn ổn định

Điểm: 25 (p) Thời gian: 0.5s Bộ nhớ: 512M Input: PEACE.INP Output: PEACE.OUT

Cho một dãy gồm \(N\) số nguyên \(A_1, A_2, \dots, A_N\). Một đoạn con liên tiếp của dãy từ phần tử thứ \(L\) đến phần tử thứ \(R\) (\(1 \le L \le R \le N\)) được gọi là một đoạn ổn định nếu tổng các phần tử trong đoạn con này có giá trị nằm trong đoạn \([U, V]\). Nói cách khác:

\[U \le \sum_{i=L}^{R} A_i = A_L + A_{L+1} + \dots + A_R \le V\]

Yêu cầu: Cho trước dãy số \(A\) và hai giá trị \(U, V\). Hãy đếm xem có tất cả bao nhiêu đoạn ổn định trong dãy.

Input

  • Dòng đầu tiên chứa ba số nguyên \(N, U, V\) (\(1 \le N \le 10^5; -10^{14} \le U \le V \le 10^{14}\)).
  • Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \dots, A_N\) (\(-10^9 \le A_i \le 10^9\)).

Output

  • In ra một số nguyên duy nhất là số lượng đoạn ổn định đếm được.

Example

Test 1

Input 
4 -2 2
-2 5 -1 2
Output 
5
Note

Có \(5\) đoạn con liên tiếp có tổng nằm trong \([-2, 2]\) là:

  • Đoạn \([1, 1]\) có tổng là \(-2\).
  • Đoạn \([1, 3]\) có tổng là \(-2 + 5 - 1 = 2\).
  • Đoạn \([3, 3]\) có tổng là \(-1\).
  • Đoạn \([3, 4]\) có tổng là \(-1 + 2 = 1\).
  • Đoạn \([4, 4]\) có tổng là \(2\).

Scoring

  • Subtask \(1\) (\(30\%\) số điểm): \(N \le 2000\).
  • Subtask \(2\) (\(30\%\) số điểm): \(A_i \ge 0\) với mọi \(1 \le i \le N\).
  • Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.