Programme C++ pour trouver le nombre minimum et maximum d'enfants avant le début du jeu

Supposons que nous ayons un tableau A contenant K éléments. Considérons un jeu avec N joueurs et un maître de jeu. Ce jeu comporte K tours. Au premier tour du jeu, le maître du jeu annonce que les enfants A[i] seront formés en groupes. Les enfants restants forment alors autant de groupes d’enfants A[i] que possible. Un enfant ne peut pas participer à plus d'un groupe. Personne dans le groupe ne quitte le jeu. D'autres accèdent au tour suivant. Il ne peut y avoir aucune perte de joueur au cours d'un tour. Finalement, après le tour K, il ne restait plus que deux enfants et ils furent déclarés vainqueurs. Il faut soit trouver le nombre minimum et maximum d'enfants qui peuvent exister dans le jeu avant de commencer, soit déterminer que N n'a pas de valeur valide.

Donc, si l'entrée est quelque chose comme A = [3, 4, 3, 2] alors la sortie sera [6, 8] car si le jeu commence avec 6 enfants alors il continuera

• au 1er Dans le tour, 6 d'entre eux forment deux groupes de 3 personnes chacun

• Ils forment deux groupes de 4 et 2 enfants respectivement

• Puis un groupe de 1 enfant et 3 enfants, 1 quittera le Jeu

• Trois des ils forment un groupe de 1 et 2. Je vais partir.

Les 2 derniers enfants ont été déclarés gagnants.

Étapes

Pour résoudre ce problème, nous suivrons les étapes suivantes -

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

Exemple

Voyons l'implémentation suivante pour une meilleure compréhension -

#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);
}

Input

{ 3, 4, 3, 2 }

Output

6, 8

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!