Program C++ untuk mencari bilangan minimum dan maksimum kanak-kanak sebelum permainan bermula

Katakan kita mempunyai tatasusunan A yang mengandungi unsur K. Pertimbangkan permainan dengan N pemain dan master permainan. Permainan ini mempunyai pusingan K. Dalam pusingan i permainan, master permainan mengumumkan bahawa kanak-kanak A[i] akan dibentuk dalam kumpulan. Kanak-kanak yang tinggal kemudian membentuk seberapa banyak kumpulan kanak-kanak A[i] yang mungkin. Seorang kanak-kanak tidak boleh mengambil bahagian dalam lebih daripada satu kumpulan. Tiada seorang pun dalam kumpulan meninggalkan permainan. Yang lain mara ke pusingan seterusnya. Mungkin tiada pemain kalah dalam satu pusingan. Akhirnya, selepas pusingan K, hanya tinggal dua kanak-kanak dan mereka telah diisytiharkan sebagai pemenang. Kita mesti sama ada mencari bilangan minimum dan maksimum kanak-kanak yang mungkin wujud dalam permainan sebelum memulakan, atau menentukan bahawa N tidak mempunyai nilai yang sah.

Jadi jika input adalah seperti A = [3, 4 , 3, 2] maka output akan menjadi [6, 8] kerana jika permainan dimulakan dengan 6 kanak-kanak maka ia akan diteruskan

• pada 1st In the bulat, 6 daripadanya membentuk dua kumpulan masing-masing 3 orang

• Mereka membentuk dua kumpulan masing-masing 4 dan 2 kanak-kanak

• Kemudian sekumpulan 1 kanak-kanak dan 3 kanak-kanak, 1 akan meninggalkan Permainan

• Tiga mereka membentuk kumpulan 1 dan 2. 1 akan pergi.

2 anak terakhir diisytiharkan sebagai pemenang.

Langkah

Untuk menyelesaikan masalah ini kami akan mengikuti langkah berikut -

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

Contoh

Mari kita lihat pelaksanaan berikut untuk pemahaman yang lebih baik -

#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

Atas ialah kandungan terperinci Program C++ untuk mencari bilangan minimum dan maksimum kanak-kanak sebelum permainan bermula. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!