Táo và Chuối

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Cho $n$ quả táo và $m$ quả chuối, mỗi quả có trọng lượng nguyên. Trọng lượng táo nằm trong $[1, k]$ , trọng lượng chuối cũng nằm trong $[1, k]$ .

Với mỗi tổng trọng lượng $w$ từ $2$ đến $2 k$ , hãy tính số cách chọn một quả táo và một quả chuối sao cho tổng trọng lượng của chúng bằng $w$ .

Dữ liệu vào

Dòng 1: ba số nguyên $k$ , $n$ , $m$ .
Dòng 2: $n$ số nguyên — trọng lượng các quả táo $a_{1}, a_{2}, \dots, a_{n}$ .
Dòng 3: $m$ số nguyên — trọng lượng các quả chuối $b_{1}, b_{2}, \dots, b_{m}$ .

Dữ liệu ra

$2 k - 1$ số nguyên — với mỗi $w$ từ $2$ đến $2 k$ , số cặp $(i, j)$ sao cho $a_{i} + b_{j} = w$ .

Ràng buộc

$1 \leq k, n, m \leq 2 \times 10^{5}$
$1 \leq a_{i} \leq k$ , $1 \leq b_{j} \leq k$

Ví dụ

Input	Output	Giải thích
5 3 4 5 2 5 4 3 2 3	0 0 1 2 1 2 4 2 0	Với $w = 8$ : táo trọng 5 (2 quả) × chuối trọng 3 (2 quả) = 4 cặp.
10 10 10 4 5 2 7 3 5 6 2 5 6 2 3 5 6 2 2 6 3 5 3	0 0 6 9 6 16 21 13 11 10 6 2 0 0 0 0 0 0 0

Bình luận

Không có bình luận tại thời điểm này.