Home > Backend Development > C++ > body text

C++ program to find the minimum and maximum number of children before the game starts

WBOY
Release: 2023-08-27 15:21:02
forward
1246 people have browsed it

C++ 程序以找到游戏开始前的最小和最大儿童数量

Suppose we have an array A containing K elements. Consider a game with N players and a game master. This game has K rounds. In round i of the game, the game master announces that A[i] children will be formed into groups. The remaining children then form as many groups of A[i] children as possible. A child cannot participate in more than one group. No one in the group leaves the game. Others advance to the next round. There may be no player losses in a round. Finally, after round K, only two children were left and they were declared the winners. We must either find the minimum and maximum number of children that may exist in the game before starting, or determine that N does not have a valid value.

So if the input is something like A = [3, 4 , 3, 2] then the output will be [6, 8] because if the game starts with 6 children then it will continue

  • In the first round, 6 of them formed two groups of 3 people each

  • They formed two groups of 4 and 2 respectively Children

  • Then a group of 1 child and 3 children, 1 will leave the game

  • The three of them form a group of 1 and 2 Group. 1 will leave.

The last 2 kids were declared the winners.

Steps

To solve this problem we will follow the following steps-

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
Copy after login

Example

Let us see the following implementation for better understanding -

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

Input

{ 3, 4, 3, 2 }
Copy after login

Output

6, 8
Copy after login

The above is the detailed content of C++ program to find the minimum and maximum number of children before the game starts. For more information, please follow other related articles on the PHP Chinese website!

source:tutorialspoint.com
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template