Chương trình C ++ để tìm số lượng con nhỏ nhất và lớn nhất trong trò chơi trước khi bắt đầu

Giả sử chúng ta có một mảng A với K số phần tử. Hãy xem xét, trong một trò chơi có N người chơi và một bậc thầy của trò chơi ở đó. Trò chơi này có K vòng. Ở vòng thứ i, người điều khiển trò chơi thông báo thành lập các nhóm với A [i] số trẻ em. Sau đó, các trẻ còn lại tạo thành nhiều nhóm A [i] trẻ nhất có thể. Một trẻ không được tham gia vào nhiều nhóm. Những người còn lại không có nhóm thì rời khỏi trò chơi. Những người khác tiếp tục vào vòng tiếp theo. Một vòng đấu có thể không có người chơi nào bị mất. Cuối cùng, sau vòng K chỉ còn lại đúng hai em và được tuyên bố là người chiến thắng. Chúng tôi phải tìm số lượng trẻ em nhỏ nhất và lớn nhất có thể trong trò chơi trước khi bắt đầu hoặc xác định rằng không tồn tại giá trị hợp lệ nào của N.

Vì vậy, nếu đầu vào là A =[3, 4, 3, 2], thì đầu ra sẽ là [6, 8], bởi vì nếu trò chơi bắt đầu với 6 con, thì nó sẽ tiến hành

• Ở vòng 1, 6 người trong số họ tạo thành hai nhóm 3 người

• Họ đang thành lập hai nhóm với 4 và 2 trẻ em

• Sau đó, một nhóm có 1 trẻ em và nhóm khác có 3 trẻ và 1 nhóm đó sẽ rời khỏi trò chơi

• Ba người trong số họ tạo thành một nhóm gồm 1 và 2 và 1 người sẽ rời đi.

2 người con cuối cùng được tuyên bố là người chiến thắng.

Các bước

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

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

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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

Đầu vào

{ 3, 4, 3, 2 }

Đầu ra

6, 8