Question

CРочно решить задачу на С++?В многопользовательской игре Agar.io игроки управляют бактериями. У каждой бактерии есть размер — целое положительное число. Если встречаются две бактерии разного размера, то бактерия большего размера поглощает меньшую бактерию. При этом меньшая бактерия исчезает, а размер большей бактерии увеличивается на размер меньшей бактерии. Если встречаются две бактерии равного размера, то ничего не происходит. Побеждает игрок, чья бактерия останется на игровом поле одна. В игре участвуют n игроков, вам даны размеры их бактерий. Определите, какие из игроков имеют возможность выиграть в этой игре. Формат ввода Программа получает на вход целое число n, 1≤ n≤ 105 — количество игроков. Следующие n строк содержат по одному числу ai — размеры бактерий, 1≤ ai≤ 109. Числа ai заданы в порядке неубывания. Формат вывода Программа должна вывести n чисел равных «0» или «1», по одному числу в строке. Если i-е число равно 0, то это означает, что i-й игрок (размер бактерии которого первоначально был равен ai) ни при каких обстоятельствах не может выиграть в этой игре. Если i-е число равно 1, то это означает, что i-й игрок имеет возможность выиграть в этой игре.

Answer 1

#include <iostream>

#include <vector>

#include <set>

#define ll long long

using namespace std;

signed main() {

   ll n;

   cin >> n;

   vector<pair<ll,ll>> a(n);

   vector<ll> pref(n,0),d(n,0),ans(n,0);

   set<ll> s;

   for(ll i = 0; i < n; i++){

       cin >> a[i].first;

       a[i].second = i;

       s.insert(a[i].first);

       if(i == 0)

           pref[i] = a[i].first;

       else

           pref[i] = pref[i-1] + a[i].first;

       d[i] = s.size();

   }

   if(d[n-1] > 1 || n == 1)

       ans[a[n-1].second] = 1;

   for(ll i = n - 2; i >= 0; i--){

       if(pref[i] > a[i + 1].first && ans[a[i+1].second] == 1 && d[i] > 1)

           ans[a[i].second] = 1;

   }

   for(ll i = 0; i < n; i++)

       cout << ans[i] << " ";

}

P.S. Откуда задача, уж больно часто я ее встречаю на подобных сайтах

Answer 2

Привет! Я могу помочь тебе с этой задачей на языке программирования C++. Вот решение:

cppCopy code
#include <iostream>
#include <vector>

int main() {
    int n;
    std::cin >> n;

    std::vector<int> sizes(n);
    for (int i = 0; i < n; i++) {
        std::cin >> sizes[i];
    }

    std::vector<int> canWin(n, 1); // Изначально предполагаем, что все игроки могут выиграть

    for (int i = 1; i < n; i++) {
        if (sizes[i] <= sizes[i - 1]) {
            canWin[i] = 0; // Если текущий игрок имеет размер меньший или равный предыдущему, то он не может выиграть
        }
    }

    for (int i = n - 2; i >= 0; i--) {
        if (sizes[i] >= sizes[i + 1] && canWin[i + 1] == 1) {
            canWin[i] = 0; // Если текущий игрок имеет размер больший или равный следующему и следующий игрок может выиграть, то текущий игрок не может выиграть
        }
    }

    for (int i = 0; i < n; i++) {
        std::cout << canWin[i] << std::endl;
    }

    return 0;
}

Эта программа считывает количество игроков n, а затем размеры бактерий каждого игрока. Затем она определяет, какие игроки могут выиграть в игре, и выводит результаты.

Алгоритм решения заключается в следующем:

1. Создаем вектор canWin размером n и заполняем его единицами, предполагая, что все игроки могут выиграть.
2. Проходим по размерам бактерий слева направо. Если размер текущей бактерии меньше или равен предыдущей, то помечаем игрока как того, кто не может выиграть (устанавливаем canWin[i] в 0).
3. Проходим по размерам бактерий справа налево. Если размер текущей бактерии больше или равен следующей и следующий игрок может выиграть (его флаг canWin[i + 1] равен 1), то помечаем текущего игрока как того, кто не может выиграть (устанавливаем canWin[i] в 0).
4. Выводим результаты canWin.

Надеюсь, это поможет! Если у тебя возникнут еще вопросы, не стесняйся задавать.