Và...
Xem dạng PDFCho số nguyên không âm ~x~, hãy tìm dãy số nguyên ~a_1, a_2, \ldots, a_n~ thỏa mãn các điều kiện sau:
~0 \le a_i \le x~ với ~1 \le i \le n~.
Tổng AND của các dãy con liên tiếp của ~a~ là đôi một phân biệt.
Nói cách khác, định nghĩa ~f(l, r)=a_l \,\&\, a_{l+1} \,\&\, \ldots \,\&\, a_r~ (tổng AND của dãy con liên tiếp từ vị trí ~l~ đến vị trí ~r~). Với mọi bộ bốn chỉ số ~(l_1, r_1, l_2, r_2)~ sao cho ~l_1 \le r_1~, ~l_2 \le r_2~ và ~(l_1, r_1) \ne (l_2, r_2)~ thì ~f(l_1, r_1) \ne f(l_2, r_2)~.
Độ dài ~n~ là lớn nhất có thể.
Input
Mỗi test gồm nhiều test case. Dòng đầu tiên của bộ dữ liệu chứa số nguyên dương ~t~ (~1 \le t \le 10~) là số lượng test case. Mô tả của mỗi test case như sau.
Mỗi test case gồm một số nguyên duy nhất ~x~ (~1 \le x \le 10^6~) — giới hạn giá trị của dãy ~a~.
Output
Với mỗi test case, hãy in ra đáp án theo định dạng như sau:
Dòng đầu tiên gồm số nguyên ~n~ (~1 \le n \le 2000~) — độ dài dãy ~a~.
Dòng thứ hai gồm ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ (~0 \le a_i \le x~) — các phần tử của dãy ~a~.
Có thể chỉ ra rằng độ dài dãy ~a~ thỏa yêu cầu đề bài không thể vượt quá ~2000~.
Scoring
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | ~500~ | ~x \le 16~ |
| 2 | ~1250~ | Không có ràng buộc gì thêm |
| Tổng | ~1750~ |
Sample Input 1
2
1
2
Sample Output 1
1
1
2
1 2
Notes
Ở test case thứ hai, với ~a = [1, 2]~ thì:
Đoạn con ~[1]~ có giá trị tổng AND bằng ~1~.
Đoạn con ~[2]~ có giá trị tổng AND bằng ~2~.
Đoạn con ~[1, 2]~ có giá trị tổng AND bằng ~1 \,\&\, 2 = 0~.
Cả ba đoạn con đều có giá trị tổng AND phân biệt nhau, nên dãy ~a~ thỏa yêu cầu đề bài. Có thể chứng minh không tồn tại dãy ~a~ có độ dài từ ~3~ trở lên thỏa yêu cầu đề bài.
Bình luận
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.