Question

Паладину по работе нужно одолеть n монстров. Изначально у паладина есть h единиц здоровья. Про каждого монстра известно, что если паладин вступит с ним в бой, то во время битвы монстр нанесет ему ai единиц урона и здоровье паладина уменьшится на ai единиц. Если здоровье паладина станет меньше или равно 0, то он погибнет. Но если паладин сможет победить монстра, то он заберет у него его лечебное зелье, выпьет его и восстановит себе bi единиц здоровья. Ограничений на максимальное количество здоровья у паладина нет, т.е. после использования зелий его здоровье может стать больше, чем h

.

Паладин может сражаться с монстрами в любом порядке. Может ли паладин победить всех n

монстров и выжить?
Входные данные

В первой строке даны целые числа n
(1≤n≤2⋅105) и h (1≤h≤109

) — количество монстров и изначальное количество единиц здоровья паладина.

Следующие n
строк содержат по паре целых чисел ai (1≤ai≤109) и bi (0≤bi≤109) — урон от битвы с i-м монстром и количество единиц здоровья, которое восстанавливает зелье i

-го монстра.
Выходные данные

Если паладин может победить всех монстров и выжить, то выведите «YES» (без кавычек), иначе выведите «NO» (без кавычек).

Вы можете выводить каждую из букв в любом регистре.
Система оценки

В задаче 4 подзадачи. Подзадача 0
— тесты из условия, за нее баллы не начисляются. Тестирование подзадачи начинается, если пройдены все тесты в необходимых подзадачах. Система оценки «полная» означает, что решение получит баллы за прохождение всех тестов данной подзадачи.

Answer 1

Відповідь:

Пояснення:

Ми можемо використати жадібний підхід: сортувати монстрів за зменшенням величини ai - bi, тобто спочатку справжній урон, а потім відновлення.

def can_defeat_monsters(n, h, monsters):

   monsters.sort(key=lambda x: x[0] - x[1], reverse=True)

   for monster in monsters:

       damage, heal = monster

       if damage >= h:

           h -= damage

       else:

           if heal == 0:

               return "NO"

           num_potions = (h + damage - 1) // damage

           h += num_potions * heal

           h -= damage

   return "YES"

# Зчитуємо вхідні дані

n, h = map(int, input().split())

monsters = [list(map(int, input().split())) for _ in range(n)]

# Виводимо результат

result = can_defeat_monsters(n, h, monsters)

print(result)

Ця програма сортує монстрів за спаданням ефективності (урон - відновлення), а потім витрачає здоров'я паладина, або використовує зелья, доки паладин не поборе всіх монстрів або не помере. Якщо паладин виживає, виводиться "YES", інакше "NO".