LCS2X - VOI 2014 - Dãy con chung bội hai dài nhất
Giới hạn- Thời gian: 1.0s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Dãy C = c1, c2, .. ck được gọi là dãy con của dãy A = a1, a2, .., an nếu C có thể nhận được bằng cách xóa bớt một số phần tử của dãy A và giữ nguyên thứ tự của các phần tử còn lại, nghĩa là tìm được dãy các chỉ số 1 ≤ l1 < l2 < … < lk ≤ n sao cho c1 = a_l1, c2 = a_l2, …, ck = a_lk. Ta gọi độ dài của dãy là số phần tử của dãy.
Cho hai dãy A = a1, a2, …, am và B = b1, b2, …, bn Dãy C = c1, c2, …, ck được gọi là dãy con chung bội hai của dãy A và B nếu C vừa là dãy con của dãy A, vừa là dãy con của dãy B và thỏa mãn điều kiện 2 × ci ≤ c(i+1) (i = 1, 2, …, k – 1).
Yêu cầu
Cho hai dãy A và B. Hãy tìm độ dài dãy con chung bội hai có độ dài lớn nhất của hai dãy A và B.
Input
Dòng đầu tiên chứa T là số lượng bộ dữ liệu. Tiếp đến là T nhóm dòng, mỗi nhóm cho thông tin về một bộ dữ liệu theo khuôn dạng sau:
- Dòng đầu chứa 2 số nguyên dương m và n.
- Dòng thứ hai chứa m số nguyên không âm a1, a2, ..., am mỗi số không vượt quá 10^9.
- Dòng thứ ba chứa n số nguyên không âm b1, b2, ..., bn mỗi số không vượt quá 10^9.
- Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.
Giới hạn
- 30% số test có m, n <= 15.
- 30% số test khác có m, n <= 150.
- có 40% số test còn lại có m, n <= 1500.
Output
Ghi ra T dòng, mỗi dòng ghi một số nguyên là độ dài dãy con chung bội hai dài nhất của dãy A và B tương ứng với bộ dữ liệu vào.
Example
Input: 1 5 5 5 1 6 10 20 1 8 6 10 20 Output: 3
- Người up: voj
- Nguồn bài: VOI 2014 - Ngày 1