Xếp đồ chơi thành đống
Đề bài
Mô tả
Masha có đồ chơi được đánh số từ đến . Một cách sắp xếp là một cách chia toàn bộ đồ chơi thành các đống không rỗng. Thứ tự các đống cũng như thứ tự đồ chơi trong mỗi đống không quan trọng: hai cách sắp xếp được coi là khác nhau nếu tồn tại hai đồ chơi nằm chung một đống ở cách này nhưng nằm ở hai đống khác nhau ở cách kia.
Ban đầu tất cả đồ chơi nằm chung trong một đống. Mỗi thao tác, Sasha lấy đúng một đồ chơi từ đống đang chứa nó và đặt sang một đống khác; đống mới có thể được tạo ra và đống cũ có thể biến mất nếu nó trở nên rỗng.
Sasha muốn thử tất cả các cách sắp xếp, mỗi cách đúng một lần, với số thao tác ít nhất. Hãy giúp Sasha: in ra một dãy các cách sắp xếp sao cho
- cách sắp xếp đầu tiên là trạng thái ban đầu (tất cả đồ chơi trong một đống);
- mỗi cách sắp xếp xuất hiện đúng một lần;
- hai cách sắp xếp liên tiếp trong dãy khác nhau đúng một thao tác.
Nếu có nhiều đáp án, in ra bất kỳ đáp án nào.
Dữ liệu vào
Một dòng duy nhất chứa số nguyên là số đồ chơi.
Dữ liệu ra
Dòng đầu tiên in số lượng cách sắp xếp khác nhau.
Mỗi dòng tiếp theo in một cách sắp xếp, theo thứ tự Sasha sẽ thử. Trong mỗi đống, các đồ chơi được viết theo thứ tự tăng dần; các đống được viết theo thứ tự tăng dần của đồ chơi nhỏ nhất trong đống. Mỗi đống được bọc trong cặp ngoặc nhọn, các số trong một đống và các đống liên tiếp cách nhau bởi dấu phẩy, không có dấu cách (xem ví dụ).
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 | 5 {1,2,3} {1,2},{3} {1},{2},{3} {1},{2,3} {1,3},{2} |
Có cách chia đồ chơi thành các đống. Bắt đầu từ đống chung {1,2,3}, chuyển đồ chơi ra đống mới, rồi chuyển ra đống mới, rồi chuyển sang đống chứa , cuối cùng chuyển sang đống chứa . Một đáp án khác cũng được chấp nhận nếu thoả mãn cả ba điều kiện. |
| 2 | 2 {1,2} {1},{2} |
Chỉ có cách sắp xếp; chuyển đồ chơi ra đống riêng là đủ. |
Bình luận