eolymp
bolt
Try our new interface for solving problems
Məsələlər

Убить дракона

Убить дракона

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Небольшая группа отважных магов собралась убить злого дракона. Поскольку они занимаются этим каждую неделю, они уже наизусть выучили поведение драконов и способны предсказывать все их действия с точностью до секунды.

Маги бывают двух видов — атакующие и лекари. Атакующие маги наносят урон дракону, а лекари восстанавливают здоровье раненых магов. Каждый атакующий маг может окружить дракона антимагической аурой, которая непрерывно наносит дракону урон. Аналогично каждый лекарь может окружить всех магов на поле боя аурой, которая непрерывно восстанавливает здоровье всех магов.

Пока маг поддерживает свою ауру, её мощность (повреждение либо исцеление, исходящее от этой ауры за единицу времени) линейно растёт. Но мощность ауры каждого мага не может превосходить некоторой фиксированной величины, связанной с этим магом. Как только маг перестаёт поддерживать свою ауру, её мощность начинает линейно убывать до тех пор, пока она не достигнет нуля либо пока маг не начнёт поддерживать её вновь. Таким образом, мощность ауры всегда неотрицательна.

Ауры разных магов никак не влияют друг на друга. Общий урон, наносимый дракону, равен сумме урона, наносимого каждой из аур атакующих магов. Аналогично общее исцеление магов равняется сумме исцеления, исходящего от каждой из аур лекарей. Здоровье мага не может превышать своего первоначального значения, одинакового для всех магов.

В течение всего боя дракон в каком-то порядке применяет заклинания. Одно и то же заклинание может применяться драконом несколько раз подряд.

Первое заклинание — огненный смерч — образует стену огня на всём поле боя, кроме небольшого клочка земли в самом центре этого смерча. Пока маг находится в огне, он получает постоянный урон, равный мощности этого огненного смерча, и не может использовать заклинания. В центре смерча достаточно места, чтобы там могли поместиться все маги. Находясь в центре смерча, маг не получает урона и имеет возможность колдовать. При разных применениях смерча его центр может оказываться в разных точках поля боя.

Второе заклинание — дыхание дракона. Пока оно действует, каждый маг на поле боя получает постоянный урон, равный мощности этого дыхания. К счастью, во время дыхания дракона на поле есть несколькоотносительно безопасных мест, где маги способны использовать свои заклинания (в любой другой точке маг не способен делать это). В каждом из таких мест способен разместиться только один маг. Количество таких мест всегда равно количеству магов. Как и в случае смерча, при разных применениях дыхания дракона относительно безопасные места могут появляться в разных точках. Дыхание дракона требует больше магической силы, чем огненный смерч, поэтому дракон никогда не использует его более двух раз подряд.

Через некоторое время сражение надоедает дракону, и он мгновенно убивает всех магов одним ударом хвоста.

Далее будем называть атакой дракона либо применение одного из двух его заклинаний, либо удар хвостом. Первая атака дракона начинается в момент времени 0. Каждая его следующая атака начинается в момент окончания предыдущей атаки. Также следует считать, что в момент, когда дракон меняет одну свою атаку на другую, действует первая из них.

Сразу же после начала очередного огненного смерча все маги бегут по прямой в его центр. В случае дыхания дракона каждый маг выбирает себе одно из относительно безопасных мест (каждый — своё собственное) и бежит по прямой к нему. Во время бега несколько магов могут находиться одновременно в одной и той же точке, но это не отменяет условия, что место может считаться относительно безопасным во время дыхания дракона только для одного мага, находящегося там.

Любое из заклинаний дракона применяется в течение достаточно длительного времени, чтобы маг успел за такое время добежать от любой из безопасных точек предыдущего заклинания до любой из безопасных точек текущего (при этом не гарантируется, что маг может добежать дотуда живым). Более того, если текущее заклинание — огненный смерч, то его длительности заведомо хватает для того, чтобы все маги успели не только добежать до его центра, но и полностью восстановить своё здоровье и увеличить мощность атакующих и лечащих аур до максимума. Заклинания дракона могут иметь разную мощность, но она всегда строго больше максимальной суммарной мощности аур всех лекарей.

Если в какой-то момент времени уровень здоровья одного из магов опустится до нуля, то все маги тут же погибнут. Убить дракона сложней, чем мага — для этого нужно не только уменьшить его здоровье до нуля, но ещё и применить после этого добивающее заклинание. Маги могут применить его только тогда, когда они все находятся в центре огненного смерча. Естественно, в момент применения добивающего заклинания все маги должны быть ещё живы. Добивающее заклинание действует мгновенно.

В момент времени 0 все маги расположны в начале координат, мощность ауры каждого лекаря равняется её максимальному значению, а мощность ауры каждого атакующего мага равна нулю.

Giriş verilənləri

В первой строке записаны целые неотрицательные числа n, m и k - количество атакующих магов, количество лекарей и общее количество атак дракона (1 n + m 10; 1 k 10). Во второй строке записаны целые числа hp_m, v и hp_d - начальный уровень здоровья мага, скорость бега мага и начальный уровень здоровья дракона (1 hp_m, hp_d10^9; 1 v 10^6).

Следующие n строк описывают атакующих магов. В i-й из них записаны целые числа dps_i, id_i и dd_i - максимальная мощность ауры i-го атакующего мага, скорость роста мощности его ауры в те моменты времени, когда он поддерживает заклинание, и скорость уменьшения мощности его ауры в те моменты, когда он бежит к очередной безопасной точке (1 dps_i, id_i, dd_i10^6).

Следующие m строк описывают лекарей. В i-ой из них записаны целые числа hps_i, ih_i и dh_i, описывающие те же величины, что описывают числа dps_i, id_i и dd_i для атакующих магов (1hps_i, ih_i, dh_i10^6).

Далее следуют k блоков, описывающих атаки дракона в хронологическом порядке.

Если очередная атака - огненный смерч, то первая строка блока представляет собой единственное слово "Storm". Во второй строке блока через пробел записаны целые числа d и t - мощность и длительность заклинания (1 d, t 10^6). В третьей строке блока записаны целые числа x и y - координаты центра смерча (-1000 x, y 1000).

Если очередная атака - дыхание дракона, то первая строка блока представляет собой единственное слово "Breath". Во второй строке блока через пробел записаны целые числа d и t - мощность и длительность заклинания (1 d, t 10^6). В следующих n + m строках блока дано по два целых числа x_i и y_i - координаты относительно безопасных мест (-1000x_i, y_i1000). Все относительно безопасные места расположены в разных точках.

Если очередная атака - удар хвостом, то блок, описывающий её, состоит из единственной строки "Tail".

Гарантируется, что среди всех атак есть ровно один удар хвостом и что он завершает список атак. Также гарантируется, что в списке нет более двух дыханий дракона подряд.

Длительность заклинания дракона измеряется в секундах, координаты - в метрах, скорость магов - в метрах в секунду. Мощность ауры мага и мощность заклинания дракона измеряются в единицах здоровья в секунду, скорость роста/уменьшения мощности ауры мага - в единицах здоровья в секунду за секунду.

Обратите внимание на то, что хотя все числа во входных данных целые, перемещение, урон, исцеление и изменение мощности ауры происходят непрерывно.

Çıxış verilənləri

Если маги не способны убить дракона, выведите "You are not prepared".

В противном случае в первой строке выведите "No useful loot again". Во второй строке выведите единственное целое число - минимальный номер атаки дракона, во время которой он может умереть. Атаки нумеруются с единицы.

Nümunə

Giriş verilənləri #1
1 1 2
1 5 10
1 3 2
1 1 1
Storm
7 11
0 0
Tail
Çıxış verilənləri #1
No useful loot again
1
Müəllif Денис Дублённых
Mənbə 2013 Петрозаводск, Зима, Контест Уральского университета, Кубок Контура, Задача B