ある局面において、\(2\) つの選択肢（サイコロの「出目を増やす」またはサイコロを「振り直す」）のどちらを取るべきかは、明らかにその局面おけるサイコロの出目のみによって定まります。 したがって、\(i = 1, 2, \ldots, N\) のそれぞれ（ \(i = T\) を除く）について、「サイコロの出目が \(i\) であるときにどちらの選択をするか」を決定することを考えます。

下記の \(2\) つの事実に注意します。

• 出目が \(T\) より大きい局面では、明らかに「振り直す」のが最適である。
• 「『出目を増やす』を行った後に『振り直す』」のは、単に「振り直す」よりも明らかに損である。よって、最適な戦略においては、ある出目 \(P\) で「出目を増やす」選択をするのであれば、\(P \leq P'\) を満たすすべて（出目 \(T\) を除く）の出目 \(P'\) で「出目を増やす」選択をする。

上記の \(2\) 点より、最適な戦略を求めるには下記を満たす戦略の中で最適なものを見つければ良いことがわかります。

\(1 \leq X \leq T\) を満たすある整数 \(X\) が存在して、出目が \(T-X+1\) 以上 \(T\) 未満の場合には『出目を増やす』選択をとり、それ以外（ただし \(T\) を除く）の場合には『振り直す』選択をとる。

すなわち本問題は、 \(1 \leq X \leq T\) を満たす上記の整数 \(X\) を「出目を \(S\) から \(T\) に変えるためにかかる費用の期待値」が最小となるように選ぶ問題です。

以下で、

• 「 \(T-X+1\leq S \leq T\) を満たす」という条件下で \(X\) を選ぶ場合
• 「 \(T-X+1\leq S \leq T\) を満たさない」という条件下で \(X\) を選ぶ場合

の \(2\) つの場合について「出目を \(S\) から \(T\) に変えるためにかかる費用の期待値」の最小値を計算します。（ただし、\(S > T\) のときは後者の場合のみを考えます。）
両者のうち小さい方の値がこの問題の答えとなります。

(1) 「 \(T-X+1\leq S \leq T\) を満たす」という条件下で \(X\) を選ぶとき

出目が \(S\) から \(T\) に変わるまで「出目を増やす」選択をとり続けるので、かかる費用は \(X\) の値によらず \(A(T-S)\) です。

(2) 「 \(T-X+1\leq S \leq T\) を満たさない」という条件下で \(X\) を選ぶとき

出目が \(S\) から \(T\) に変わるまでの過程は、下記の \(2\) つのステップに分かれます。

1. まず、出目が \(T-X+1\) 以上 \(T\) 以下になるまで、「振り直す」選択を取り続ける。
2. その後、出目が \(T\) になるまで「出目を増やす」選択を取り続ける。

それぞれのステップでかかる費用の期待値は次の通りです。

1. 「サイコロを \(1\) 回振り直した結果、出目が \(T-X+1\) 以上 \(T\) になる確率」は \(X/N\) であるので、\(1\) つ目のステップでサイコロを「振り直す」回数の期待値は \(N/X\) です。よって、\(1\) つ目のステップでかかる費用の期待値は \(BN/X\) です。
   
2. \(1\) つ目のステップを終えた時点での出目として、\(T-X+1\) 以上 \(T\) 以下の整数がありえます。また、それらは等確率で起こります。よって、\(2\) つ目のステップでかかる費用の期待値は、\(\lbrace\sum_{i = T-X+1}^{T} A(T-i)\rbrace/X = A(X-1)/2\) です。
   

よって、出目が \(S\) から \(T\) に変わるまでにかかる費用の期待値は \(A(X-1)/2 + BN/X\) です。
以下で、「 \(T-X+1\leq S \leq T\) を満たさない」という条件下で整数 \(X\) を選ぶときの \(A(X-1)/2 + BN/X\) の最小値を求める方法を述べます。

正の実数 \(x\) に対して定義された関数 \(f(x) = A(x-1)/2 + BN/x\) を考えます。関数 \(f(x)\) は相加・相乗平均の関係より \(x = \sqrt{2BN/A}\) のとき最小値を取ります。 また、\(f''(x) = 2BN/x^3\) であるので \(f(x)\) は下に凸な関数です。 よって、「 \(T-X+1\leq S \leq T\) を満たさない」かつ \(1 \leq X \leq T\) を満たす整数 \(X\) のうち、\(\sqrt{2BN/A}\) に近いものいくつかについて \(f(X)\) の値を計算してそれらの最小値をとれば良いです。 （ここで、実際には「 \(T-X+1\leq S \leq T\) を満たさない」という制約は無視しても良いことが示せます。）