Bài 2. Số cặp nhảy (HSG THPT Hà Tĩnh - Khối 12 2026)

Xem dạng PDF

Gửi bài giải

Điểm: 1,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Tác giả:
Nguồn bài:
HSG THPT Hà Tĩnh - Khối 12 2026
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Hướng tới kỷ niệm ngày thành lập Đoàn Thanh niên Cộng sản Hồ Chí Minh, Tỉnh đoàn dự định tổ chức Hội thi khiêu vũ cho đoàn viên là các cặp đôi nam-nữ.

Theo danh sách đăng ký, có ~n~ bạn nam và ~m~ bạn nữ. Danh sách các bạn nam được đánh số từ 1 đến ~n~ có chiều cao lần lượt là ~a_1, a_2, \ldots, a_n~. Danh sách các bạn nữ được đánh số từ 1 đến ~m~ có chiều cao lần lượt là ~b_1, b_2, \ldots, b_m~. Ban tổ chức muốn ghép nhiều nhất các cặp nhảy theo thứ tự đăng ký sao cho mỗi cặp nhảy gồm một bạn nam và một bạn nữ có chiều cao bằng nhau. Tức là tồn tại dãy chỉ số ~1 \le i_1 < i_2 < \ldots < i_k \le n~ và ~1 \le j_1 < j_2 < \ldots < j_k \le m~ sao cho ~a_{i_\{1}\} = b_{j_\{1}\}, a_{i_\{2}\} = b_{j_\{2}\}, \ldots, a_{i_\{k}\} = b_{j_\{k}\}~.

Yêu cầu: Cho danh sách chiều cao của ~n~ bạn nam và ~m~ bạn nữ, hãy cho biết số cặp nhảy tối đa mà Ban tổ chức có thể ghép được.

Dữ liệu vào

Gồm ba dòng:

  • Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~m (n, m \le 10^6)~.
  • Dòng thứ hai chứa dãy số ~A~ gồm ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n (a_i \le 10^9)~ lần lượt là chiều cao của các bạn nam.
  • Dòng thứ ba chứa dãy số ~B~ gồm ~m~ số nguyên dương ~b_1, b_2, \ldots, b_m (b_i \le 10^9)~ lần lượt là chiều cao của các bạn nữ.

Kết quả

Một số nguyên là số cặp nhảy tối đa ghép được.

Ví dụ

Input 1

6 5
170 155 180 165 156 185
155 185 156 180 165

Output 1

3

Ba cặp nhảy được chọn theo thứ tự có chiều cao lần lượt là 155, 180, 165.

Ràng buộc

  • Có 40% số test ứng với 40% số điểm thỏa mãn: Dãy số ~A~ đã được sắp xếp và ~n, m \le 20~.
  • Có 30% số test khác ứng với 30% số điểm thỏa mãn: ~20 < n, m \le 10^3~.
  • Có 20% số test khác ứng với 20% số điểm thỏa mãn: ~20 < n \le 10^3, 10^3 < m \le 10^6, a_i \le 10^6~.
  • Có 10% số test còn lại ứng với 10% số điểm thỏa mãn: Dãy số ~A~ và dãy số ~B~ đã được sắp xếp, ~10^3 < n, m \le 10^6~.

Chương trình đọc dữ liệu từ bàn phím (stdin) và ghi kết quả ra màn hình (stdout).


Đang tải...