K개의 요소가 있는 배열 A가 있다고 가정합니다. 한 게임에 N명의 플레이어가 있고 게임 마스터가 있다고 생각해 보십시오. 이 게임에는 K 라운드가 있습니다. i번째 라운드에서 게임 마스터는 A[i]명의 자녀로 그룹을 형성할 것을 알립니다. 그런 다음 나머지 자식은 가능한 한 많은 A[i] 자식 그룹을 형성합니다. 한 어린이는 여러 그룹에 참여할 수 없습니다. 그룹 없이 남겨진 사람들은 게임을 떠납니다. 나머지는 다음 라운드로 진행합니다. 라운드는 플레이어 손실 없이 있을 수 있습니다. 결국 K 라운드가 끝나고 정확히 두 명의 자녀가 남았고, 그들이 승자로 선언되었습니다. 시작하기 전에 게임에서 가능한 가장 작은 수와 가장 큰 수의 어린이를 찾거나 유효한 N 값이 존재하지 않는지 확인해야 합니다.
따라서 입력이 A =[3, 4, 3, 2]와 같으면 출력은 [6, 8]이 됩니다. 왜냐하면 게임이 6명의 자식으로 시작하면 계속 진행되기 때문입니다.
-
1라운드에서는 6명이 3명씩 두 그룹을 형성합니다.
-
그들은 4명과 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