HSG lớp 10 Hà Tĩnh 2024-2025

Bộ đề bài

Trở lại kỳ thi
# Bài tập Điểm Thời gian: Giới hạn bộ nhớ
1 Tìm số 7 (p) 1.0s 1G
2 Tuyến đường 7 (p) 1.0s 1G
3 Đoạn con đẹp 6 (p) 1.0s 1G

1. Tìm số

Điểm: 7 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Gọi \(F(x)\) là số ước nguyên dương của số nguyên dương \(x\) tính cả \(1\) và \(x\).

Ví dụ số \(6\) có \(4\) ước số dương là \(1, 2, 3\) và \(6\). Ta có \(F(6) = 4\).

Yêu cầu: Cho đoạn \([a, b]\) trên trục số, tìm số nguyên dương \(k\) nhỏ nhất thuộc đoạn \([a, b]\) mà \(F(k)\) lớn nhất.

Input

  • Vào từ tệp văn bản TIMSO.INP một dòng duy nhất chứa hai số nguyên dương \(a, b\) (\(1 \leq a \leq b \leq 10^9\); \(b - a \leq 10^6\)).

Output

  • Ghi ra tệp văn bản TIMSO.OUT một số nguyên dương \(k\) thỏa mãn yêu cầu bài toán.

Example

Test 1

Input 
7 10
Output 
8
Note

Trong đoạn \([7, 10]\) ta có:

  • Số \(7\) có \(2\) ước dương là \(1, 7 \Rightarrow F(7) = 2\);
  • Số \(8\) có \(4\) ước dương là \(1, 2, 4, 8 \Rightarrow F(8) = 4\);
  • Số \(9\) có \(3\) ước dương là \(1, 3, 9 \Rightarrow F(9) = 3\);
  • Số \(10\) có \(4\) ước dương là \(1, 2, 5, 10 \Rightarrow F(10) = 4\);

Vậy số \(8\) là số nhỏ nhất và \(F(8) = 4\) lớn nhất.

Ràng buộc

  • Có \(60\%\) số test ứng với \(60\%\) số điểm thỏa mãn: \(a, b \leq 10^6, b - a \leq 10^2\).
  • \(40\%\) số test còn lại ứng với \(40\%\) số điểm của bài không có ràng buộc gì thêm.

2. Tuyến đường

Điểm: 7 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Người ta muốn xây dựng một tuyến đường qua một vùng đất. Tuyến đường được chia thành \(N\) đoạn. Để làm được việc này người ta phải san nền cho vùng đất mà tuyến đường sẽ di qua. Ban đầu, nền đường tại đoạn thứ \(i\) (\(1 \le i \le N\)) có độ cao là \(h_i\) và người ta muốn sau khi san nền, tại tất cả các đoạn đường, nền đường đều có cùng một độ cao là \(k\).

Tại những đoạn mà nền đường có độ cao \(h_i > k\) người ta cần đào đi một lượng đất là \(h_i - k\) và mất chi phí \(h_i - k\).
Tại những đoạn mà nền đường có độ cao \(h_i < k\) người ta cần đắp thêm một lượng đất là \(k - h_i\) và mất chi phí \(k - h_i\).

Yêu cầu: Cho biết độ cao \(k\) của nền đường, hãy tính tổng chi phí cần bỏ ra để san nền cho \(N\) đoạn đường với độ cao \(k\).

Input

  • Vào từ tệp văn bản SANNEN.INP:
    • Dòng đầu tiên ghi 2 số nguyên dương \(N, M\) lần lượt là số đoạn đường cần san nền và số bộ dữ liệu, mỗi bộ tương ứng với một số nguyên dương \(k\) (\(1 \le N \le 10^5\), \(1 \le M \le 10^5\), \(1 \le k \le 10^9\));
    • Dòng thứ hai chứa \(N\) số nguyên dương \(h_1, h_2, \dots, h_N\) với \(h_i\) là độ cao của nền đường tại đoạn thứ \(i\) (\(1 \le h_i \le 10^9\), \(1 \le i \le N\));
    • \(M\) dòng tiếp theo, mỗi dòng chứa một số nguyên dương \(k\).

Output

  • Ghi ra tệp văn bản SANNEN.OUT gồm \(M\) dòng, mỗi dòng chứa một số nguyên dương tương ứng là kết quả tính được theo dữ liệu vào.

Example

Test 1

Input 
5 3
3 2 7 1 9
4
1
6
Output 
14
17
16

Ràng buộc

  • Có \(60\%\) số test ứng với \(60\%\) số điểm thỏa mãn: \(1 \le N \le 10^3\), \(1 \le M \le 10^3\);
  • \(40\%\) số test còn lại ứng với \(40\%\) số điểm của bài không có ràng buộc gì thêm.

3. Đoạn con đẹp

Điểm: 6 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Cho hai số nguyên dương \(N, K\) và dãy số nguyên dương \(A\) gồm \(N\) phần tử \(a_1, a_2, \dots, a_N\).

Đoạn con đẹp của dãy số \(A\) được xác định là tập hợp các phần tử liên tiếp từ vị trí điểm đầu \(L\) đến vị trí điểm cuối \(R\) (\(1 \le L \le R \le N\)) của dãy \(A\) mà với mọi cặp \((i, j)\) (\(L \le i \le j \le R\)) luôn thỏa mãn điều kiện \(|a_i - a_j| \le K\).

Yêu cầu: Hãy tìm đoạn con đẹp dài nhất của dãy số \(A\).

Input

  • Vào từ tệp văn bản BSUB.INP:
    • Dòng thứ nhất chứa 2 số nguyên dương \(N, K\) (\(0 < N \le 10^6, 0 < K \le 10^9\));
    • Dòng thứ hai chứa \(N\) số nguyên dương \(a_1, a_2, \dots, a_N\) (\(0 < a_i \le 10^9, 1 \le i \le N\)).

Output

  • Ghi ra tệp văn bản BSUB.OUT gồm một số nguyên dương là độ dài của đoạn con đẹp dài nhất tìm được.

Example

Test 1

Input 
7 3
10 3 6 5 6 16 17
Output 
4
Note

Đoạn con đẹp dài nhất tìm được là \(3, 6, 5, 6\) có độ dài bằng \(4\).

Scoring

  • Có \(30\%\) số test ứng với \(30\%\) số điểm thỏa mãn: \(1 \le N \le 10^2\);
  • Có \(20\%\) số test ứng với \(20\%\) số điểm thỏa mãn: \(1 \le N \le 10^3\);
  • Có \(20\%\) số test ứng với \(20\%\) số điểm thỏa mãn: \(1 \le N \le 10^5\);
  • Có \(30\%\) số test ứng với \(30\%\) số điểm của bài không có ràng buộc gì thêm.