trang chủ / đề bài / icpc20_reg_a

Giả kim thuật 101

Đề bài

Mô tả

Là học sinh trường Phù thủy và Pháp sư Hogwarts, Harry phải học môn Giả kim thuật: môn học về tính chất ma thuật của các nguyên tố và sự biến đổi các chất. Trong buổi thực hành Giả kim hôm nay, Harry thử nghiệm biến đổi các chất. Trong thế giới phép thuật có vô số chất, được đánh số bằng các số nguyên dương. Khi kết hợp hai chất i và j, ta thu được chất i⊕j, trong đó ⊕ là phép xor theo bit.

Nhắc lại cách phép xor theo bit hoạt động: phép xor theo bit nhận hai dãy bit cùng độ dài và thực hiện phép "hoặc loại trừ" trên từng cặp bit tương ứng. Kết quả ở mỗi vị trí là 1 nếu đúng một trong hai bit là 1, và là 0 nếu cả hai bit đều là 0 hoặc đều là 1. Ví dụ:

      0 1 0 1  (số thập phân 5)
XOR   0 0 1 1  (số thập phân 3)
    = 0 1 1 0  (số thập phân 6)

Như vậy 5⊕3=6. Trong bài này, ta nói kết hợp chất 5 và chất 3 sẽ được chất 5⊕3=6. Lưu ý thứ tự kết hợp các chất không quan trọng, nhờ tính giao hoán và kết hợp của phép xor:

  • a⊕b=b⊕a,
  • a⊕(b⊕c)=(a⊕b)⊕c.

Harry muốn tạo ra chất m bằng cách dùng nhiều chất nhất có thể. Tuy nhiên, phòng thí nghiệm của Hogwarts chỉ có m chất đánh số từ 1 đến m, nên Harry chỉ được dùng các chất này và không được dùng chất nào hai lần.

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên t, số bộ dữ liệu.
  • Mỗi bộ dữ liệu gồm một dòng chứa số nguyên m. Đảm bảo luôn có thể tạo ra chất m chỉ dùng các chất đánh số từ 1 đến m, mỗi chất không quá một lần.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra hai dòng:

  • Dòng thứ nhất chứa n: số chất nhiều nhất Harry có thể dùng.
  • Dòng thứ hai chứa n số nguyên cách nhau bởi dấu cách: các chất Harry dùng.

Nếu có nhiều đáp án tối ưu, bạn phải in ra đáp án có thứ tự từ điển nhỏ nhất. Danh sách a1,a2,…,an có thứ tự từ điển nhỏ hơn danh sách b1,b2,…,bn khi và chỉ khi tồn tại chỉ số i sao cho cả hai điều kiện sau đều đúng:

  • a1=b1,a2=b2,…,ai−1=bi−1,
  • ai<bi.

Ràng buộc

  • 1≤t≤103.
  • 1≤m≤103.

Ví dụ

Input Output Giải thích
3
1
4
5
1
1
4
1 2 3 4
4
1 2 3 5
1=1; 1⊕2⊕3⊕4=4; 1⊕2⊕3⊕5=5.
2
2
3
1
2
2
1 2
Với m=2: 1⊕2=3≠2 nên chỉ dùng được chất 2. Với m=3: 1⊕2=3.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0