레이팅 미적용설명
수직선 위 위치 \(0, 1, 2, \ldots, N\)에 노드가 있다. 입자는 현재 위치 \(X\)에서 출발한다. 매 단계마다
- 확률 \(\dfrac{A}{B}\)로 위치를 \(1\) 감소시킨다.
- 확률 \(\dfrac{B-A}{B}\)로 위치를 \(1\) 증가시킨다.
위치가 \(0\) 또는 \(N\)에 닿으면 이동을 멈춘다. 입자가 위치 \(N\)에서 멈출 확률을 구하여라.
답은 기약분수 \(P/Q\) 형태로 출력한다.
제약
- \(1 \le A < B \le 10\)
- \(1 \le X < N \le 100\)
입력 형식
한 줄에 정수 \(A\), \(B\), \(X\), \(N\)이 공백으로 구분되어 주어진다.
출력 형식
위치 \(N\)에서 멈출 확률을 기약분수 \(P/Q\) 형태로 한 줄에 출력한다. (\(\gcd(P, Q) = 1\), \(Q \ge 1\))
예제 1
입력
1 2 1 2
출력
1/2
설명
\(p = \frac{1}{2}\)이므로 대칭 이동. 시작 위치 \(1\)에서 \(N=2\)에 도달할 확률은 \(\frac{X}{N} = \frac{1}{2}\)이다.
예제 2
입력
1 4 1 3
출력
9/13
설명
왼쪽 확률 \(p = \frac{1}{4}\), \(r = \frac{1/4}{3/4} = \frac{1}{3}\). \(P(\text{win}|1) = \frac{r^1 - 1}{r^3 - 1} = \frac{-2/3}{-26/27} = \frac{9}{13}\)이다.
문제 정보
riseoj 작성
출처 Original
태그