Dãy bậc k (THTB TQ 2020)

Xem PDF

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

Mít mới học ba định nghĩa mới liên quan đến dãy số như sau:

  • Một dãy số được gọi là dãy đầy đủ bậc \(K\) khi dãy số có đúng \(K\) phần tử và gồm đủ các phần tử từ \(1\) đến \(K\). Ví dụ dãy số \((2, 3, 1)\) là dãy số đầy đủ bậc \(3\).

  • Dãy số \(B\) được gọi là dãy con của dãy số \(A\) khi dãy số \(B\) được tạo ra bằng cách xóa bỏ một số phần tử của dãy số \(A\) (giữ nguyên thứ tự trước sau và có thể không xóa bỏ phần tử nào). Ví dụ dãy số \(A\)\((4, 2, 1, 2, 5, 6)\), một số dãy số con của dãy số \(A\)\((4, 1, 6)\); \((2, 2, 5, 6)\); \((4, 2, 1, 2, 5, 6)\); ...

  • Dãy số \(A\) được gọi là có thứ tự từ điển nhỏ hơn dãy số \(B\) khi tồn tại vị trí \(i\) mà:

    • Với mọi vị trí \(j\) \((j < i)\) thì \(a_j = b_j\)
    • \(a_i < b_i\)

Sau khi học xong lý thuyết, thầy giáo đã giao cho Mít một bài tập rất khó:

Cho một số \(K\) và dãy số \(A\)\(N\) số nguyên dương không lớn hơn \(K\). Hãy tìm dãy con của dãy số \(A\) có thứ tự từ điển nhỏ nhất và là một dãy đầy đủ bậc \(K\).

Yêu cầu: Hãy lập trình giúp Mít tìm dãy con thỏa mãn yêu cầu của thầy giáo.

Input

Vào từ thiết bị vào chuẩn theo khuôn dạng sau:

  • Dòng đầu tiên chứa một số nguyên dương \(T\) \((T \le 5)\) là số bộ dữ liệu.
  • Mỗi bộ dữ liệu có cấu trúc như sau:
    • Dòng đầu tiên chứa hai số nguyên dương \(N\)\(K\) là số lượng phần tử của dãy số \(A\) và số \(K\) cho trước. \((2 \le K \le N)\)
    • Dòng tiếp theo chứa \(N\) số nguyên dương \(x\) là các phần tử của dãy số \(A\) \((x \le K)\).

Output

  • Ghi ra thiết bị ra chuẩn: với mỗi bộ dữ liệu ghi ra một dãy con thỏa mãn yêu cầu. Dữ liệu đảm bảo luôn có kết quả.

  • Các số trên một dòng được ghi cách nhau bởi dấu cách

Example

Test 1

Input
2
4 3
3 2 1 2
8 4
4 2 3 3 1 3 2 4
Output
 3 1 2
 1 3 2 4

Scoring

  • Subtask \(1\): \(30\%\) số test ứng với \(N \le 18\)
  • Subtask \(2\): \(20\%\) số test khác ứng với \(N \le 30\)
  • Subtask \(3\): \(20\%\) số test khác ứng với \(N \le 10^5\), \(K \le 10\)
  • Subtask \(4\): \(30\%\) số test còn lại ứng với \(K \le N \le 10^5\)

Bình luận

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