만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

N-각형

시간 제한2초메모리 제한1024 MB

요약
1부터 k까지의 길이를 가진 선분들로 이루어진 집합 중, 변형되지 않은 n각형을 만들 수 있는 n개의 선분 조합이 없는 최대 크기의 집합을 구해 길이를 오름차순으로 출력한다.
난이도

어려움10점 중 8점

유형
그리디, 수학, 조합론, 정렬
정답자
아직 제출이 없습니다

문제

플랫랜드의 유명한 아동용품 제조사가 새로운 교육용 장난감을 출시하려고 한다. 이 장난감 세트는 여러 개의 선분으로 이루어지며, 아이들은 이 선분으로 여러 도형을 만들 수 있다.

그런데 신제품 발표회에서 한 전문가가 국가 위원회 앞에서 지적하기를, 비퇴화 nn-각형을 만드는 것은 아이들의 정신 발달에 매우 나쁜 영향을 줄 수 있으므로, 세트 안에 nn개의 선분으로 비퇴화 nn-각형을 만들 수 있는 그런 집합이 나타날 가능성을 피해야 한다고 했다.

생산 라인은 만들어지는 선분의 길이가 kk 이하인 자연수가 되도록 설계되어 있다. 회사 사장은 세트가 가능한 한 많은 선분으로 이루어지기를 원한다. 당신의 임무는 그러한 세트를 만드는 것이다.

입력

입력 파일은 두 정수를 포함한다. nn은 금지된 다각형의 꼭짓점 수이고, kk는 선분 길이의 최댓값이다 (3≤n≤103 \le n \le 10, 1≤k≤1081 \le k \le 10^8).

출력

출력 파일의 첫째 줄에는 주어진 제약에서 달성할 수 있는 세트 내 선분 개수의 최댓값을 출력한다.

둘째 줄에는 그 선분들의 길이를 비내림차순으로 출력한다. 답이 여러 개면 아무거나 출력한다.

예제1

  1. 예제 1

    입력
    3 7
    
    예상 출력
    5
    1 1 2 3 5