Pythonで石を取り除くことで最大スコアを見つけるプログラム

a、b、cの3つの値があるとします。サイズがそれぞれa、b、cの3つの石の山でソリティアゲームをプレイしています。毎ターン、プレイヤーは2つの異なる空でない山を選択し、それぞれから1つの石を取り、スコアに1ポイントを追加します。空でない山が2つ未満になると、ゲームは終了します。したがって、取得できる最大スコアを見つける必要があります。

したがって、入力がa =4、b =4、c =6の場合、初期状態は（4、4、6）であるため、出力は7になり、次の手順を実行できます-

• 現在の状態が（3、3、6）になるように、1番目と2番目の杭から選択します

• 現在の状態が（2、3、5）になるように、1番目と3番目の杭から選択します

• 現在の状態が（1、3、4）になるように、1番目と3番目の杭から選択します

• 現在の状態が（0、3、3）になるように、1番目と3番目の杭から選択します

• 現在の状態が（0、2、2）になるように、2番目と3番目のパイルから選択します

• 現在の状態が（0、1、1）になるように、2番目と3番目のパイルから選択します

• 現在の状態が（0、0、0）になるように、2番目と3番目のパイルから選択します

そして最後に、空でない山が2つ未満になるため、ゲームは終了します。

これを解決するには、次の手順に従います-

• 最小：=a、b、cの最小値

• maximum：=a、b、cの最大値

• 左：=a + b+c-最大-最小

• maximum-left <=minimumの場合、

  • 最小値+左を返す-（1 +最小値-（最大-左））/2の商

• 最小値+（（最大値-最小値）の最小値と左）を返す

例

理解を深めるために、次の実装を見てみましょう-

def solve(a, b, c):
   minimum = min(a,b,c)
   maximum = max(a,b,c)
   left = a+b+c-maximum-minimum
   if maximum-left<=minimum:
      return minimum + left-(1+minimum-(maximum-left))//2
   return minimum + min(maximum-minimum,left)

a = 4
b = 4
c = 6
print(solve(a, b, c))

入力

4, 4, 6

出力

7