Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

LCS2X - VOI 2014 - Dãy con chung bội hai dài nhất

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

Được gửi lên bởi:VOJ Team
Ngày:2014-01-04
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:VOI 2014 - Ngày 1

hide comments
2017-08-16 21:18:50 Con Bò Huyền Thoại
https://kienthuc24h.com/bai-giai-lcs2x-spoj-voi2014-day-con-chung-boi-hai-dai-nhat/
2017-08-11 11:22:23
xem cách giải:
https://vietcodes.github.io/code/39/
2016-12-29 14:04:32
https://docs.google.com/document/d/1LiYbtO6B8kYwc34hyBdnqn4x1PMms53C426k4knEiVI/edit?copiedFromTrash
2016-12-03 09:09:18
ai 60đ để ý trường hợp 0*2=0
2016-12-02 14:42:49 xin đừng quên tôi
THAM KHẢO THUẬT TOÁN VÀ CODE TẠI: http://yeulaptrinh.pw/458/lcs2x-spoj/
2016-11-12 17:58:32
gg ez N ^ 2 http://liink.pw/zqyy
2016-11-12 14:30:39 Bui Van Hop
98.33 làm O(N^2) mà là sao ta @@
2016-09-19 02:58:13 minhsn
trau cung ac
2016-08-21 16:02:54
vcl nộp toàn 0 :)))))))))) gg quá -_-
2016-07-23 20:35:27
Trâu cụng Ac đc , bá vại .__.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.