물 붓는 게임을 확인하는 C++ 코드는 모두 승자인지 여부

n개의 요소가 있는 배열 A가 있고 다른 숫자 s가 있다고 가정합니다. 테이블에 빈 물 머그잔 하나와 비어 있지 않은 물 머그 n개가 있습니다. 게임에는 소수의 플레이어가 있습니다. 각 이동에서 플레이어는 비어 있지 않은 물 머그잔을 가져 와서 컵에 모든 물을 붓습니다. 넘치면 플레이어가 패배합니다. 우리는 그들 모두가 승자가 될지 여부를 확인해야 합니다(컵이 넘치지 않을 것입니다). 하나의 업이 이미 완전히 채워진 경우 다음 플레이어는 자신의 이동을 플레이하지 않습니다. 여기서 s는 빈 컵의 용량이고 A[i]는 i번째 컵에 있는 물의 양입니다.

따라서 입력이 A =[3, 1, 3]과 같으면; s =4이면 첫 번째 및 두 번째 플레이어가 컵을 채울 것이기 때문에 출력은 True가 됩니다. 마지막으로 플레이어는 해당 동작을 하지 않습니다.

단계

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

k := 0
n := size of A
sort the array A
for initialize i := 0, when i < n - 1, update (increase i by 1), do:
   k := k + A[i]
if k > s, then:
   return false
Otherwise
   return true

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
bool solve(vector<int> A, int s){
   int k = 0;
   int n = A.size();
   sort(A.begin(), A.end());
   for (int i = 0; i < n - 1; i++)
      k += A[i];
   if (k > s)
      return false;
   else
      return true;
}
int main(){
   vector<int> A = { 3, 1, 3 };
   int s = 4;
   cout << solve(A, s) << endl;
}

입력

{ 3, 1, 3 }, 4

출력

1