VM 13 Bài 12 - Dãy số

View as PDF

Submit solution

Points: 1.78 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
VM13 - Trần Anh Hướng Thái Huy, Nguyễn Tấn Sỹ Nguyên
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

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 \leq S \leq 1500~
  • ~1 \leq T \leq 10^{9}~
  • Dữ liệu đảm bảo tồn tại ít nhất một dãy số thỏa mãn.

Sample Input

5 2

Sample Output

6
3
1 1 2

Comments

Please read the guidelines before commenting.


There are no comments at the moment.