Trung vị cố định
Đề bài
Mô tả
Với một dãy gồm số nguyên không âm , trong đó lẻ, trung vị của là phần tử thứ (đánh số từ ) khi sắp xếp các phần tử theo thứ tự tăng dần. Ví dụ:
- Với , trung vị là (dãy đã được sắp xếp, và ).
- Với , trung vị là (sau khi sắp xếp ta được , và ).
- Với , trung vị là .
Cho dãy gồm số nguyên không âm với lẻ, và một số nguyên không âm . Một số phần tử của bị mất (được ký hiệu là ). Hãy khôi phục các phần tử bị mất sao cho trung vị của đúng bằng , hoặc cho biết điều đó là không thể.
Dữ liệu vào
Dòng đầu tiên chứa số nguyên dương (): số bộ test. Mỗi bộ test gồm:
- Dòng thứ nhất chứa hai số nguyên và (, lẻ, ): độ dài dãy và giá trị trung vị cần đạt.
- Dòng thứ hai chứa số nguyên (): các phần tử của , trong đó nghĩa là bị mất.
Dữ liệu đảm bảo tổng trên tất cả các bộ test không vượt quá .
Dữ liệu ra
Với mỗi bộ test, in ra "YES" (không có dấu ngoặc kép) nếu có cách khôi phục các phần tử bị mất để trung vị của bằng . Ngược lại, in ra "NO".
Nếu đáp án là "YES", dòng tiếp theo in ra số nguyên () là dãy sau khi khôi phục (các phần tử đã biết giữ nguyên). Nếu có nhiều dãy thỏa mãn, in ra một dãy bất kỳ. Có thể chứng minh rằng với ràng buộc của bài, nếu tồn tại dãy hợp lệ thì cũng tồn tại một dãy có mọi phần tử nằm trong đoạn .
Ràng buộc
- , lẻ; tổng trên tất cả các bộ test không vượt quá
- ,
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 5 3 2 0 -1 2 5 4 4 -1 6 0 -1 7 8 2 5 6 8 9 10 11 7 9 2 5 6 8 9 10 11 5 8 4 4 4 -1 -1 |
YES 0 2 2 YES 4 4 6 0 4 YES 2 5 6 8 9 10 11 NO NO |
Bộ test thứ nhất: có trung vị ; cũng hợp lệ. Bộ test thứ hai: có trung vị ; cũng hợp lệ. Bộ test thứ ba: cách khôi phục duy nhất là giữ nguyên , trung vị là . Bộ test thứ tư: trung vị của là , khác . Bộ test thứ năm: trung vị luôn là dù khôi phục thế nào. |
| 3 1 5 -1 1 0 7 3 0 -1 -1 1 |
YES 5 NO YES 0 0 1 |
Bộ test thứ hai: không có phần tử bị mất, trung vị là . Bộ test thứ ba: có trung vị . |
Bình luận