시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 225 100 63 43.448%

문제

1부터 N으로 번호가 매겨진 박스와 1부터 N으로 번호가 매겨진 열쇠가 있다. i번째 키는 i번째 박스를 열 수 있다.

다못이는 각각의 박스에 정확하게 하나의 열쇠를 무작위로 넣는다. 각각의 열쇠가 박스에 들어갈 확률은 모두 같다고 가정한다. 그리고 나서 박스를 모두 잠근다. 다못이는 M개의 폭탄이 있다. 폭탄이 하는 역할은 잠겨져 있는 박스를 여는 역할을 한다. 박스를 열 때, 열쇠는 부셔지지 않는다. 다못이가 잠겨진 박스를 열고 나면, 그 키를 이용해서 또 다른 박스를 열 수가 있다. 다못이의 전략은 박스 하나를 선택해서 폭탄을 이용해서 키를 얻는다. 그리고 나서 그 열쇠로 박스를 열고 또 그 속의 열쇠로 열고, 열 박스가 없을 때 까지 한다. 그리고 나서 폭탄이 남았으면 그 폭탄을 이용해서 다시 반복한다.

다못이는 모든 열쇠를 얻고 싶다. 다못이가 모든 열쇠를 얻을 확률을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 박스와 열쇠의 개수 N과 폭탄의 개수 M이 공백을 사이에 두고 주어진다. N은 20보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다.

출력

다못이가 모든 열쇠를 얻을 확률을 A/B 형태로 출력한다. A와 B는 최대공약수가 1인 자연수이다.

예제 입력

2 1

예제 출력

1/2

힌트

Box1에 열쇠2가 들어있으면, 모든 키를 얻을 수 있다.

출처