開始前にゲーム内の最小および最大数の子を見つけるC++プログラム

K個の要素を持つ配列Aがあるとします。ゲームにはN人のプレーヤーがいて、ゲームマスターがそこにいると考えてください。このゲームにはKラウンドがあります。 i番目のラウンドでは、ゲームマスターはA[i]人の子供を持つグループを形成することを発表します。次に、残りの子はできるだけ多くのA[i]子のグループを形成します。 1人の子供が複数のグループに参加することはできません。グループなしで残された人はゲームを離れます。他は次のラウンドに進みます。ラウンドはプレーヤーを失うことなく行うことができます。結局、K回戦後はちょうど2人の子供が残っており、勝者と宣言されています。開始前に、ゲーム内の可能な限り最小および最大の子の数を見つけるか、Nの有効な値が存在しないことを確認する必要があります。

したがって、入力がA =[3、4、3、2]の場合、出力は[6、8]になります。これは、ゲームが6人の子で開始された場合、続行されるためです

• ラウンド1では、そのうちの6人が3人の2つのグループを形成します

• 彼らは4人と2人の子供を持つ2つのグループを形成しています

• 次に、子供が1人、子供が3人のグループで、その1人がゲームを終了します

• それらのうちの3つは1と2のグループを形成し、1つは去ります。

最後の2人の子供が勝者として宣言されます。

ステップ

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

n := size of A
Define a large array a, l, r, a of size: 100010.
l := 2, r = 2
for initialize i := 1, when i <= n, update (increase i by 1), do:
   a[i] := A[i - 1]
for initialize i := n, when i >= 1, update (decrease i by 1), do:
   x := a[i], L := (l + x - 1)
   if L > R, then:
      return -1, 0
   l := L, r = R + x - 1
return l, r

例

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

#include <bits/stdc++.h>
using namespace std;

void solve(vector<int> A){
   int n = A.size();
   int l, r, a[100010];
   l = 2, r = 2;
   for (int i = 1; i <= n; i++)
      a[i] = A[i - 1];
   for (int i = n; i >= 1; i--){
      int x = a[i], L = (l + x - 1) / x * x, R = r / x * x;
      if (L > R){
         cout << "-1, 0";
      }
      l = L, r = R + x - 1;
   }
   cout << l << ", " << r << endl;
   return;
}
int main(){
   vector<int> A = { 3, 4, 3, 2 };
   solve(A);
}

入力

{ 3, 4, 3, 2 }

出力

6, 8