쌍절곤 가게

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

요약

길이 n인 이진 문자열 두 개를 이어 붙여 1의 개수 합이 k인 모든 디자인을 만들 수 있을 때, 저장해야 하는 문자열의 최소 개수를 구한다. 각 문자열은 양쪽 방향으로 쓸 수 있다.

난이도: 어려움10점 중 8점
유형: 조합론, 수학, 문자열, 완전 탐색
정답자: 아직 제출이 없습니다

문제

Nathan은 독특한 디자인의 기념품 쌍절곤을 파는 가게를 운영한다. 쌍절곤은 두 개의 막대를 사슬로 연결한 전통 무술 무기이다. Nathan의 디자인에서 각 막대에는 $n$ 개의 보석이 일렬로 박혀 있다. 이 보석은 석영 또는 오닉스이며, 흑백 무늬를 이룬다. 미적인 이유로 Nathan은 두 막대에 있는 오닉스의 총 개수가 정확히 $k$ 개인 쌍절곤만 판다. 예를 들어 $n=4$ , $k=5$ 일 때 가능한 디자인 중 하나는 다음과 같다.

최근 Nathan은 모든 가능한 디자인의 쌍절곤을 팔 수 있으면 좋겠다고 생각했다. 그러려면 모든 가능한 디자인의 쌍절곤을 창고에 두어야 하는데, 가능한 디자인의 수가 너무 많다!

그래서 Nathan은 타협하기로 했다. 그는 창고에 여러 개의 막대를 둘 것이다. 손님이 어떤 디자인을 주문하면, Nathan은 창고에서 막대 두 개를 꺼내 사슬로 연결한다. 막대는 대칭이므로, Nathan은 막대의 어느 쪽 끝에든 사슬을 연결할 수 있다. 예를 들어 $n=3$ , $k=2$ 이고 Nathan의 창고에 다음 막대들이 있다면:

그는 모든 가능한 디자인의 쌍절곤을 만들 수 있다. 예를 들어 손님이 다음 디자인의 쌍절곤을 요청하면:

Nathan은 막대 1과 3으로 그것을 만들 수 있다.

이제 Nathan은 궁금해한다. 모든 가능한 디자인의 쌍절곤을 만들 수 있으려면 창고에 막대를 최소 몇 개 두어야 할까? 이 수를 구해 보자.

입력

입력은 두 정수 $n$ 과 $k$ 를 포함한다 ( $1\le n\le 50$ ; $0\le k\le 2\cdot n$ ).

출력

Nathan이 창고에 두어야 하는 막대의 최소 개수를 정수 하나로 출력한다.

예제4

예제 1
입력
```
3 2
```
예상 출력
```
7
```
예제 2
입력
```
4 1
```
예상 출력
```
3
```
예제 3
입력
```
5 0
```
예상 출력
```
2
```
예제 4
입력
```
50 50
```
예상 출력
```
626155273417404
```