canuc80k2902·3/50

Hai Nửa Cân Bằng

Nộp bài trên LQDOJ

Bài 2.10 · Constructive Algorithms

Cho một số chẵn . Hãy dựng một dãy gồm số nguyên dương đôi một khác nhau sao cho:

  • phần tử đầu đều chẵn;
  • phần tử cuối đều lẻ;
  • tổng của nửa đầu bằng tổng của nửa cuối.

Nếu có nhiều dãy hợp lệ, bạn có thể in bất kỳ dãy nào.

Input

  • Dòng đầu chứa số nguyên - số bộ test.
  • Mỗi bộ test gồm một dòng chứa số chẵn .

Output

  • Với mỗi bộ test, in NO nếu không tồn tại dãy hợp lệ.
  • Ngược lại, in YES trên một dòng và in phần tử của dãy trên dòng tiếp theo. Chữ cái trong YES và NO có thể viết hoa hoặc viết thường.

Constraints

  • .
  • , và chẵn.
  • Tổng các giá trị qua mọi bộ test không vượt .
  • Mỗi phần tử được in phải nằm trong đoạn từ đến .

Scoring

  • Subtask ( số điểm): Tổng các giá trị không vượt .
  • Subtask ( số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

3
12
14
16

Output

YES
2 4 6 8 10 12 1 3 5 7 9 17
NO
YES
2 4 6 8 10 12 14 16 1 3 5 7 9 11 13 23

Giải thích: Với và , tổng của nửa chẵn lần lượt bằng tổng của nửa lẻ trong dãy được in. Khi , nửa sau phải gồm bảy số lẻ nên có tổng lẻ, không thể bằng tổng chẵn của nửa đầu.

Lời giải tóm tắt
  • Ý tưởng: Đặt m=n/2. Tổng của m số lẻ có cùng parity với m, trong khi tổng của các số chẵn luôn chẵn; vì thế cần m chẵn, tương đương n chia hết cho 4.
  • Ý tưởng: Khi điều kiện này đúng, lấy nửa đầu là 2,4,...,2m. Ở nửa sau, dùng 1,3,...,2m-3, rồi chọn số cuối bằng hiệu hai tổng. Giá trị cuối là 3m-1, là số lẻ và lớn hơn mọi số lẻ đã dùng. Thuật toán chạy trong O(n) thời gian.