Dãy con chung zigzag dài nhất

Xem PDF

Điểm: 400 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Cho dãy \(A\) gồm \(N\) phần tử gồm các số nguyên dương \(A_1, A_2, ..., A_N\) và dãy \(B\) gồm \(M\) phần tử gồm các số nguyên dương \(B_1, B_2, ..., B_M\). Dãy \(C\) được gọi là dãy con chung zigzag độ dài \(K\) của \(A, B\) nếu tồn tại hai dãy chỉ số như sau:

  • \(1 \leq i_1 < i_2 < ... < i_K \leq N\).
  • \(1 \leq j_1 < j_2 < ... < j_K \leq M\).

Sao cho \(C_p = A_{i_p} = B_{j_p}\) và thoả mãn một trong hai điều kiện sau:

  • $C_1 > C_2 < C_3 > ... $
  • $C_1 < C_2 > C_3 < ... $

Yêu cầu: Tìm dãy \(C\) là dãy con chung zigzag của \(A, B\) sao cho độ dài \(K\) lớn nhất có thể.

Input

  • Gồm ba dòng:
  • Dòng thứ nhất chứa hai số nguyên dương \(N, M\).
  • Dòng thứ hai gồm \(N\) số nguyên dương \(A_1, A_2, ..., A_N\) \((A_i \leq 10^6)\).
  • Dòng thứ ba gồm \(M\) số nguyên dương \(B_1, B_2, ..., B_M\) \((B_i \leq 10^6)\).

Output

  • Gồm hai dòng:
  • Dòng thứ nhất in ra số \(K\) là độ dài dãy con chung \(C\) dài nhất tìm được.
  • Dòng thứ hai in ra \(K\) số nguyên dương \(C_1, C_2, ..., C_K\). Nếu có nhiều dãy \(C\) thoả mãn, in ra một dãy bất kì.

Scoring

  • Subtask \(1\) (\(30\%\) số điểm): \(N, M \leq 10^2\).
  • Subtask \(2\) (\(30\%\) số điểm): \(N, M \leq 10^3\).
  • Subtask \(3\) (\(40\%\) số điểm): \(N, M \leq 5.10^3\).
  • Nếu in ra đúng số \(K\) thì sẽ được \(50\%\) số điểm của test. Nếu in ra thêm được dãy \(C_1, C_2, ..., C_K\) mà đúng sẽ được thêm \(50\)% số điểm của test.

Example

Test 1

Input
6 8
4 3 6 5 8 7
2 4 1 6 5 1 8 7 
Output
5
4 6 5 8 7

Bình luận

Không có bình luận nào.