Решение задачи "Сражение с монстрами " с Codeforces

Без пояснения   Просмотров: 9


В линию выстроены n монстров, пронумерованных числами с 1 по n. У i-го монстра есть hi очков здоровья (hp). Вы можете атаковать с силой, равной a hp, а ваш соперник может атаковать с силой, равной b hp.

Вы и ваш соперник сражаетесь с этими монстрами. Сначала вы и ваш соперник идете к первому монстру и сражаетесь с ним до тех пор, пока он не будет мертв, затем вы и ваш соперник отправляетесь ко второму монстру и сражаетесь с ним до тех пор, пока и он не будет мертв, и так далее. Смерть монстра наступает, когда значение его hp становится меньшим или равным 0.

Сражение с монстром происходит поочередно.

Вы атакуете монстра с силой a hp. Если он погибает после вашего удара, вы получаете одно очко и затем вы и соперник переходите к следующему монстру.
Ваш соперник атакует монстра с силой b hp. Если монстр погибает после этой атаки, никто не получает очко и вы с соперником переходите к следующему монстру.
У вас есть некоторая секретная техника, с помощью которой можно заставить вашего соперника пропустить свой ход. Вы можете использовать эту технику не более, чем k раз всего (например, если есть два монстра и k=4, то вы можете использовать эту технику 2 раза во время сражения с первым монстром и 1 один раз — со вторым, но не 2 раза с первым монстром и 3 раза со вторым).

Ваша задача — определить максимальное число очков, которое вы можете получить, если будете использовать секретную технику оптимально.

Код

#include <algorithm>
#include <iostream>
using namespace std;

int main()
{
    int n, a, b, k;
    cin >> n >> a >> b >> k;
    int h[200005];
    for(int i = 0; i < n; i++){
        cin >> h[i];
        h[i] = ((h[i] - 1) % (a + b)) / a;
    }
    sort(h, h + n);
    int s = 0;
    int i = 0;
    for(; i < n; i++){
        s += h[i];
        if(s > k) break;
    }
    cout << i << endl;
}

         

 Администратор Photo Автор: Администратор


Отправить решение задачи
Чтобы отправить решение вам нужно войти в систему или зарегистрироваться

Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться