Học sinh giỏi 9 Hà Nội 2025-2026

Nhà trường tổ chức Hội chợ xuân kéo dài trong 7 ngày, giá thuê một gian hàng là \(K\) đồng/ngày. Lớp An có \(N\) đồng, muốn thuê một gian hàng trong 7 ngày để bán thiệp. Hỏi số tiền còn lại sau khi thuê gian hàng của lớp An là bao nhiêu?

Input

• Dòng đầu tiên chứa một số nguyên dương \(N\) \((N \leq 10^9)\) là số tiền lớp An có
• Dòng thứ hai chứa một số nguyên dương \(K\) \((K \leq 10^9)\) là giá thuê gian hàng trong một ngày

Output

• Một số nguyên là số tiền còn lại của lớp An, nếu không đủ tiền thuê trong 7 ngày thì ghi ra -1

Example

1000000
50000

650000

350000
50000

0

200000
50000

-1

Cho dãy số nguyên \(A\) gồm \(N\) phần tử phân biệt \(A_1, A_2, ..., A_N\) và số nguyên dương \(K\). Phần tử \(A_i\) được gọi là "cân bằng \(K\)" nếu trong dãy xuất hiện phần tử có giá trị bằng \(A_i + K\) và \(A_i - K\). Ví dụ dãy số \(5, 2, 4, 6\) và \(K = 1\) thì có \(1\) phần tử cân bằng là \(5\) vì dãy số có phần tử là \(5 - 1 = 4\) và \(5 + 1 = 6\).

Yêu cầu: Đếm số lượng phần tử "cân bằng \(K\)" của dãy số \(A\).

Input

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

Output

• In ra một số nguyên là kết quả của bài toán.

Example

6 1
4 1 7 8 5 6

3

6 2
4 -1 7 8 5 6

1

Scoring

• \(70\%\) số test ứng với \(70\%\) số điểm có \(K = 1; N \leq 10^3\) và \(0 \leq A_i \leq 10^3\)
• \(20\%\) số test tiếp theo ứng với \(20\%\) số điểm có \(K = 1; 0 \leq A_i \leq 10^6\)
• \(10\%\) số test còn lại ứng với \(10\%\) số điểm không có ràng buộc gì thêm

26 chữ cái tiếng Anh in thường được xếp thành một vòng tròn cách đều nhau 1 đơn vị như hình bên. Khoảng cách giữa hai kí tự là số bước đi chuyển ngắn nhất từ kí tự này đến kí tự kia. Ví dụ khoảng cách giữa hai kí tự d và e là 2; khoảng cách giữa a và z là 1.

Khoảng cách của một xâu là khoảng cách lớn nhất giữa hai kí tự bất kì của xâu đó. Ví dụ tính khoảng cách của xâu adc:

• Khoảng cách của a và d là 3.
• Khoảng cách của a và c là 2.
• Khoảng cách của d và c là 1.
  Vậy khoảng cách của xâu adc là \(max(3,2,1) = 3\).

Cho xâu \(S\) gồm \(N\) kí tự được đánh chỉ số từ 1 đến \(N\) và \(Q\) truy vấn, mỗi truy vấn yêu cầu tính khoảng cách của xâu con từ vị trí \(L\) đến vị trí \(R\) trong xâu \(S\) \((1 \leq L \leq R \leq N)\).

Input

• Dòng đầu tiên chứa xâu \(S\) chỉ gồm các kí tự tiếng Anh in thường gồm \(N\) kí tự \((1 \leq N \leq 10^5)\)
• Dòng thứ hai chứa số nguyên dương \(Q\) \((Q \leq 10^5)\)
• \(Q\) dòng tiếp theo, mỗi dòng gồm hai số nguyên \(L,R\) \((1 \leq L \leq R \leq N)\) mô tả đoạn con của xâu \(S\) cần tính khoảng cách

Output

• Gồm \(Q\) dòng, mỗi dòng gồm một số nguyên là kết quả của truy vấn tương ứng

Example

abcyzz
3
1 3
2 5
5 6

2
4
0

Scoring

• 50% số test ứng với 50% số điểm có \(Q = 1; N \leq 10^3\)
• 20% số test tiếp theo ứng với 20% số điểm có \(Q = 1\)
• 20% số test tiếp theo ứng với 20% số điểm có \(N \leq 10^3\)
• 10% số test còn lại ứng với 10% số điểm không có ràng buộc gì thêm

Cho dãy số nguyên \(A\) gồm \(N\) phần tử \(A_1, A_2, ..., A_N\) và số nguyên \(S\). Bạn có thể xóa đi một đoạn con liên tiếp bất kỳ trong dãy (tức là chọn hai chỉ số \(L, R\) với \(1 \leq L \leq R \leq N\) và xóa các phần tử \(A_L, A_{L+1}, ..., A_R\)). Quy ước: Nếu xóa hết dãy thì tổng còn lại bằng \(0\).

Yêu cầu: Tìm độ dài nhỏ nhất của đoạn con cần xóa sao cho tổng các phần tử còn lại của dãy không vượt quá \(S\). Nếu không cần xóa đoạn nào thì kết quả là \(0\), nếu không có cách xóa thỏa mãn thì kết quả là \(-1\).

Input

• Dòng đầu tiên chứa số nguyên dương \(N\) \((N \leq 10^5)\)
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, ..., A_N\) \((|A_i| \leq 10^5; 1 \leq i \leq N)\)
• Dòng thứ ba chứa số nguyên \(S\) \((|S| \leq 10^{14})\)

Output

• Gồm một số nguyên là kết quả của bài toán

Example

5
4 -5 4 4 -2
0

2

3
4 2 1
0

3

3
1 2 3
-2

-1

3
1 2 0
5

0

Scoring

• \(40\%\) số test ứng với \(40\%\) số điểm có \(N \leq 100; A_i \geq 0\)
• \(20\%\) số test tiếp theo ứng với \(20\%\) số điểm có \(N \leq 5000; A_i \geq 0\)
• \(20\%\) số test tiếp theo ứng với \(20\%\) số điểm có \(A_i \geq 0\)
• \(20\%\) số test còn lại ứng với \(20\%\) số điểm không có ràng buộc gì thêm

Trong một buổi tập bắn súng, có \(N\) tấm bia được xếp thành một hàng dọc, đánh số từ \(1\) tới \(N\). Độ bền của các tấm bia được mô tả bởi dãy số \(A\), tấm bia thứ \(i\) có độ bền ban đầu là \(A_i\). Một tấm bia được coi là bị phá hủy nếu độ bền của nó giảm xuống nhỏ hơn hoặc bằng \(0\) (khi này coi độ bền của tấm bia là \(0\)).

Xạ thủ được quyền chọn một loại đạn có sức công phá \(X\) (với \(X\) là số nguyên dương tùy ý) để sử dụng cho toàn bộ buổi tập. Mỗi lần bắn, xạ thủ bắn một viên đạn thẳng dọc theo hàng các tấm bia, viên đạn sẽ trúng tấm bia đầu tiên chưa bị phá hủy (tấm bia thứ \(i\) có chỉ số nhỏ nhất và độ bền \(A_i > 0\)). Do đạn có tính xuyên phá nên sẽ gây ảnh hưởng lên tấm bia thứ \(i\) và các tấm bia thứ \(j\) phía sau nó \((i ≤ j ≤ N)\). Độ bền của tấm bia thứ \(j\) bị giảm một lượng theo công thức: \(max(0, X - (j - i)^2)\).

Input

• Dòng đầu chứa hai số nguyên dương \(N, K\) (\(N \leq 2\cdot 10^5; K \leq 10^5\)) tương ứng là số tấm bia và số lần bắn tối đa.
• Dòng tiếp theo chứa \(N\) số nguyên dương mô tả dãy \(A\) (\(A_i \leq 10^9; 1 \leq i \leq N\)).

Output

• In ra một số nguyên dương \(X\) nhỏ nhất tìm được.

Example

6 3
6 7 1 3 2 1

5

3 1
3 7 3

8

Scoring

• \(30\%\) số test ứng với \(30\%\) số điểm có \(N, K \leq 30; A_i \leq 30\)
• \(20\%\) số test tiếp theo ứng với \(20\%\) số điểm có \(K = 1\)
• \(30\%\) số test tiếp theo ứng với \(30\%\) số điểm có \(N \leq 1000\)
• \(20\%\) số test còn lại ứng với \(20\%\) số điểm không có ràng buộc gì thêm