[Học thêm HSG9]Thi thử HSG9

Bộ đề bài

Trở lại kỳ thi
# Bài tập Điểm Thời gian: Giới hạn bộ nhớ
1 Số trung bình 20 (p) 1.0s 1G
2 Xâu đảo ngược 25 (p) 1.0s 1G
3 Dãy số 25 (p) 1.0s 1G
4 Máy rút tiền tự động 30 (p) 1.0s 1G

1. Số trung bình

Điểm: 20 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: trungbinh.inp Output: trungbinh.out

2. Xâu đảo ngược

Điểm: 25 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: reverse.inp Output: reverse.out

Cho \(N\) xâu ký tự có độ dài mỗi xâu không vượt quá \(20\). Hãy kiểm tra xem có hai xâu \(st_i\) và \(st_j\) sao cho khi \((i<j)\) và đảo ngược \(1\) trong \(2\) xâu, ta được xâu còn lại.

Input

Dòng thứ nhất chứa số nguyên \(T(T<=10)\) - số lượng test case
Với mỗi test case, có cấu trúc như sau:
Dòng thứ nhất chứa số nguyên dương \(N(N \leq 1000)\) - số lượng xâu.
\(N\) dòng tiếp theo, mỗi dòng chứa một xâu ký tự

Output

Gồm \(T\) dòng, mỗi dòng chứa kết quả của test case. YES nếu có cặp \((i,j)\) thỏa mãn và NO nếu ngược lại.

Sample
Input 
2

3
a 
b
c

4
a 
b
ab
ba
Output 
NO
YES

3. Dãy số

Điểm: 25 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: seq.inp Output: seq.out

Cho dãy số nguyên \(A\) có \(n\) phần tử \(A_1,A_2,...,A_n\).
Nhiệm vụ của bạn là đếm số cặp \((i,j) (1 \leq i \leq j \leq n)\) sao cho \(\Sigma_{k=i}^j (L \leq a_k \leq R)\)

Dữ liệu vào

  • Dòng thứ nhất chứa ba số nguyên dương \(N,L,R\) là lần lượt là số lượng phần tử của mảng \(A\), cận trái \(L\) và cận phải \(R\).
  • Dòng thứ hai chứa \(N\) số nguyên là dãy \(A_1,A_2,...,A_N\)

Dữ liệu ra

  • In ra số lượng cặp thoả mãn yêu cầu đề bài.

Chấm điểm

Ràng buộc chung

  • \(N \leq 10^6\)
  • \(|a_i|,|L|,|R| \leq 10^9\)

Subtask

  • Subtask \(1\): \(65\%\) số điểm có \(N \leq 10^4\).
  • Subtask \(2\): \(15\%\) số điểm có duy nhất một vị trí không thỏa mãn.
  • Subtask \(3\): \(20\%\) số điểm không có ràng buộc gì thêm.

Sample

Sample 1
Input 
5 2 4
1 2 3 4 5
Output 
6
Giải thích

Có những cặp sau : \((2,2),(2,3),(2,4),(3,3),(3,4),(4,4)\)

Sample 2
Input 
5 2 2
1 2 3 4 5
Output 
1
Giải thích

Chỉ có cặp \((2,2)\)

4. Máy rút tiền tự động

Điểm: 30 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: atm.inp Output: atm.out

Một cây ATM có N tờ tiền có mệnh giá lần lượt là \(a_1,a_2,...,a_n\). Huy Hoàng muốn rút \(M\) đồng, hãy giúp ATM tìm ra một cách rút tiền cho Huy Hoàng.

Input

Dòng đầu tiên chứa hai số nguyên dương \(N,M\)
Dòng thứ hai chứa \(N\) số nguyên \(a_1,a_2,a_3,...,a_n\).

Output

Dòng thứ nhất chứa số lượng tiền cần trả.Không có cách in ra \(-1\).
Dòng thứ hai chứa các tờ tiền.

Ràng buộc

Các tờ tiền có thể có mệnh giá từ \(1\) đến \(10^9\).
Do cây ATM của NKT nên nó chỉ có tối đa \(20\) tờ tiền và luôn luôn có \(1\) tờ tiền.
Huy Hoàng rất giàu nên anh ấy luôn rút ít nhất \(1\) đồng và anh ta có thể rút tối đa \(1\) tỷ - giới hạn tối đa của thẻ anh ấy chứ không phải là số dư của anh ấy.

Sample
Input 
3 10
1 5 5
Output 
2
5 5