VMSEQ - Dãy số
Giới hạn- Thời gian: 1.0s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Dãy con khác rỗng của một dãy số là dãy số thu được khi ta xóa một số phần tử (có thể không xóa phần tử nào và không được xóa hết) và giữ nguyên thứ tự các phần tử còn lại trong dãy. Ví dụ với dãy số {3, 1, 1, 2, 3}, ta có {3, 1, 1, 2, 3}, {3, 1, 3}, {2, 3}, ... là các dãy con khác rỗng; {3, 3, 1}, {2, 1}, {4}, {}, ... không phải là dãy con khác rỗng.
Hai dãy số được gọi là phân biệt nếu chúng có số phần tử khác nhau hoặc tồn tại một vị trí mà phần tử của hai dãy khác nhau. Ví dụ {1} và {2}, {1} và {1, 1}, {1, 2} và {2, 1} là các cặp dãy số phân biệt.
Hãy đếm số lượng dãy số có đúng S dãy con khác rỗng phân biệt, biết rằng mỗi phần tử trong dãy là một số nguyên dương không lớn hơn T . Trong các dãy số thỏa điều kiện trên, tìm dãy có ít phần tử nhất . Nếu có nhiều dãy có cùng số phần tử là ít nhất, tìm dãy có thứ tự từ điển nhỏ nhất .
Input
- Một dòng chứa 2 số nguyên S và T .
Output
- Dòng 1 ghi ra số lượng dãy số tìm được.
- Dòng 2 ghi ra một số L là số phần tử của dãy số tìm được.
- Dòng 3 ghi ra L số nguyên dương tương ứng với L phần tử của dãy số tìm được.
Giới hạn
- 1 ≤ S ≤ 1500
- 1 ≤ T ≤ 10 9
- Dữ liệu đảm bảo tồn tại ít nhất một dãy số thỏa mãn.
Example
Input:
5 2
Output:
6
3
1 1 2
- Người up: voj
- Nguồn bài: VM13 - Trần Anh Hướng Thái Huy, Nguyễn Tấn Sỹ Nguyên