Cho một danh sách \(X\) gồm các số \((1, 2, \dots, N)\), một dãy con tăng là một tập hợp con của các số này xuất hiện theo thứ tự tăng dần, và một dãy con giảm là một tập hợp con của các số này xuất hiện theo thứ tự giảm dần. Ví dụ, \((5, 7, 8)\) là một dãy con tăng của \((4, 5, 3, 7, 6, 2, 8, 1)\).

Gần 80 năm trước, hai nhà toán học Paul Erdős và George Szekeres đã chứng minh một kết quả nổi tiếng: \(X\) được đảm bảo có một dãy con tăng độ dài ít nhất \(\sqrt{N}\) hoặc một dãy con giảm độ dài ít nhất \(\sqrt{N}\). Ví dụ, \((4, 5, 3, 7, 6, 2, 8, 1)\) có một dãy con giảm độ dài 4: \((5, 3, 2, 1)\).

Tôi đang dạy một lớp tổ hợp và tôi muốn "chứng minh" định lý này cho lớp của mình bằng ví dụ. Đối với mỗi số \(X[i]\) trong dãy, tôi sẽ tính hai giá trị:

• \(A[i]\): Độ dài của dãy con tăng dài nhất của \(X\) mà kết thúc tại \(X[i]\) (coi \(X[i]\) là số lớn nhất trong dãy con đó).
• \(B[i]\): Độ dài của dãy con giảm dài nhất của \(X\) mà kết thúc tại \(X[i]\) (coi \(X[i]\) là số nhỏ nhất trong dãy con đó).

Phần then chốt trong chứng minh của tôi là cặp \((A[i], B[i])\) là khác nhau đối với mọi \(i\), và điều này ngụ ý rằng \(A[i]\) hoặc \(B[i]\) phải ít nhất là \(\sqrt{N}\) đối với một số \(i\) nào đó. Với dãy số được liệt kê ở trên, đây là tất cả các giá trị của \(A[i]\) và \(B[i]\):

  i  |  X[i]  |  A[i]  |  B[i] 
-----+--------+--------+--------
  0  |   4    |   1    |   4
  1  |   5    |   2    |   4
  2  |   3    |   1    |   3
  3  |   7    |   3    |   4
  4  |   6    |   3    |   3
  5  |   2    |   1    |   2
  6  |   8    |   4    |   2
  7  |   1    |   1    |   1

Tôi đã nghĩ ra một dãy số thực sự thú vị để minh họa sự thật này, và tôi đã tính \(A[i]\) và \(B[i]\) cho mọi \(i\), nhưng sau đó tôi quên mất dãy số ban đầu của mình là gì. Cho \(A[i]\) và \(B[i]\), bạn có thể giúp tôi dựng lại \(X\) không?

\(X\) phải bao gồm các số \((1, 2, \dots, N)\) theo một thứ tự nào đó, và nếu có nhiều dãy số khả thi, bạn nên chọn dãy có thứ tự từ điển nhỏ nhất. Điều này có nghĩa là \(X[0]\) phải nhỏ nhất có thể, và nếu vẫn còn nhiều giải pháp, thì \(X[1]\) phải nhỏ nhất có thể, và cứ tiếp tục như vậy.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ test, \(T\). \(T\) bộ test tiếp theo, mỗi bộ gồm ba dòng.

Dòng đầu tiên của mỗi bộ test chứa một số nguyên duy nhất \(N\). Dòng thứ hai chứa \(N\) số nguyên dương cách nhau bởi dấu cách, đại diện cho \(A[0], A[1], \dots, A[N-1]\). Dòng thứ ba cũng chứa \(N\) số nguyên dương cách nhau bởi dấu cách, đại diện cho \(B[0], B[1], \dots, B[N-1]\).

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất một dòng chứa "Case #x: ", tiếp theo là \(X[0], X[1], \dots, X[N-1]\) theo thứ tự và cách nhau bởi dấu cách.

Ràng buộc

• \(1 \le T \le 30\).
• Đảm bảo rằng có ít nhất một giải pháp khả thi cho \(X\).

Phân nhóm

• Small dataset (Test set 1): \(1 \le N \le 20\).
• Large dataset (Test set 2): \(1 \le N \le 2000\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

2
1
1
1
8
1 2 1 3 3 1 4 1
4 4 3 4 3 2 2 1

Case #1: 1
Case #2: 4 5 3 7 6 2 8 1

Nguồn

Google Code Jam 2013, Vòng 2, bài Erdős–Szekeres.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.