eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Вбити дракона

Вбити дракона

Невелика група відважних магів зібралась вбити злого дракона. Оскільки вони займаються цим кожного тижня, вони вже напам'ять вивчили поведінку драконів і здатні передбачати усі їх дії з точністю до секунди. Маги бувають двох видів --- атакуючі та лікарі. Атакучі маги наносять шкоду дракону, а лікарі відновлюють здоров'я поранених магів. Кожен атакуючий маг може оточити дракона антимагічною аурою, яка безперервно наносить дракону шкоду. Аналогічно кожен лікар може ооточити усіх магів на полі бою аурою, яка безперервно відновлює здоров'я усіх магів. Доки маг підтримує свою ауру, її потужність (пошкодження чи сцілення, які виходять з цієї аури за одиницю часу) лінійно зростє. Але потужність аури кожного мага не може перевищувати деякої фіксованої величини, пов'язаної з цим магом. Як тільки маг перестає підтримувати свою ауру, її потужність починає лінійно спадати до тих пір, доки вона не досягне нуля або доки маг не почне підтримувати її знову. Таким чином, потужність аури завжди невід'ємна. Аури різних магів ніяк не впливають одна на одну. Спільна шкода, що наноситься дракону, дорівнює сумі шкод, які наносяться кожною з аур атакуючих магів. Аналогічно загальне сцілення магів дорівнює сумі сцілень, які отримуються від кожної з аур лікарів. Здоров'є мага не може превищувати свого печаткового значення, однакового для усіх магів. Протягом усього бою дракон у якомусь порядку застосовує заклинання. Одне і те ж заклинання може застосовуватись драконом декілька разів підряд. Перше заклинання --- вогнений смерч --- утворює стіну вогню на усьому полі бою, крім невеличкого шматка землі у самому центрі цього смерчу. Доки маг знаходиться у вогні, він отримує постійшу шкоду, рівну потужності цього вогненого смерчу, і не може використовувати закяття. У центрі смерчу достатньо місця, щоб там могли поміститись усі маги. Знаходячись у центрі смерчу, маг не отримує шкоди і має можливість чаклувати. При різних застосування смерчу його центр може опинятись у різних точках поля бою. Друге заклинання --- подих дракона. Доки він діє, кожен маг на полі бою отримує постійну шкоду, рівну потужності цього подиху. На шастя, під час подиху дракона на полі є декілька \textit{відтносно безпечних} місць, де маги здатні використовувати свої закляття (у довільній іншій точці маг не здатний це зробити). У кожному з таких місць здатний розміститись лише один маг. Кількість таких місць завжди дорівнює кількості магів. Як і випадку смерчу, при різних застосуваннях подиху дракону відносно безпечні місця можуть появлятись у різних точках. Подих дракона вимагає більше магічної сили, ніж вогняний смерч, тому дракон ніколи не використовує його більше двох разів подряд. Через деякий час битва надоїдає дракону, і він миттєво вбиває усіх магів одним ударом хвоста. Далі будемо називать \textit{атакою} дракона або застосування одного з двох його заклинань, або удар хвостом. Перша атака дракона починається у момент часу \textbf{0}. Кожна його наступна атака починається у момент завершення попередньої атаки. Також потрібно враховувати, що у момент, коли дракон змінює одну свою атаку на іншу, діє перша з них. Віразу ж після початку чергового вогненого смерчу усе маги біжать по прямій до його центру. У випадку подиху дракона кожен маг обирає собі одне з відносно безпечних місць (кожен --- своє власне) і біжить по прямій до нього. Під час бігу декілька магів можуть знаходитись одночасно у одній і тій же точці, але це не відміняє умови, що місце може вважатись відносно безпечним під час подиху дракона лише для одного мага, який знаходиться там. Довільне із заклинань дракона застосовується протягом достатньо довгого часу, щоб маг всигнув за такий час добігти від довільної з безпечних точок попереднього заклинання до довільної з безпечних точок поточного (при цьому не гарантується, что маг може добігти туди живим). Більше того, якщо поточне заклинання --- вогнений смерч, то його тривалості завідомо вистачає для того, щоб усі маги встигли не тільки добігти до його центру, але й повністю відновити своє здоров'я та збільшити потужність атакуючих чи лікувальних аур до максимума. Заклинання дракона можуть мати різну потужність, но вона завжди строго більше максимальної суммарної потудності аур усіх лікарів. Якщо у якийсь момент часу рівень здоров'я одного з магів опуститься до нуля, то усі маги тут же загинуть. Вбити дракона складніше, ніж мага --- для цього потрібно не тільки зменшити його здоров'я до нуля, але ще й застосувати після цього добиваюче заклинання. Маги можуть застосовувати його лише тоді, коли вони усі знаходяться у центрі вогненого смерчу. Звичайно, у момент застосування добиваючого заклинання усі маги повинні бути ще живі. Добиваюче заклинання діє миттєво. У момент часу \textbf{0} усі маги розміщені у початку координат, потужність аури кожного лікаря дорівнює її максимальному значенню, а потужність аури кождого атакуючого мага дорівнює нулю. \InputFile У першому рядку записані цілі невід'ємні числа \textbf{n}, \textbf{m} та \textbf{k} --- кількість атакуючих магів, кількість лікарів та загальна кількість атак дракона (\textbf{1} ≤ \textbf{n + m} ≤ \textbf{10}; \textbf{1} ≤ \textbf{k} ≤ \textbf{10}). У другому рядку записані цілі числа \textbf{hp_m}, \textbf{v} та \textbf{hp_d} --- початковий рівень здоров'я мага, швидкість бігу мага та початковий рівень здоров'я дракона (\textbf{1} ≤ \textbf{hp_m}, \textbf{hp_d} ≤ \textbf{10^9}; \textbf{1} ≤ \textbf{v} ≤ \textbf{10^6}). Наступні \textbf{n} рядків описують атакуючих магів. У \textbf{i}-му з них записані цілі числа \textbf{dps_i}, \textbf{id_i} та \textbf{dd_i} --- максимальна потужність аури \textbf{i}-го атакуючого мага, швидкість зростання потужності його аури у ті моменти часу, коли він підтримує заклинання, та швидкість зменшення потужності його аури у ті моменти, коли він біжить до чергової безпечної точки (\textbf{1} ≤ \textbf{dps_i}, \textbf{id_i}, \textbf{dd_i} ≤ \textbf{10^6}). Наступні \textbf{m} рядків описують лікарів. У \textbf{i}-му з них записані цілі числа \textbf{hps_i}, \textbf{ih_i} та \textbf{dh_i}, які описують ті ж величини, що описують числа \textbf{dps_i}, \textbf{id_i} та \textbf{dd_i} для атакуючих магів (\textbf{1} ≤ \textbf{hps_i}, \textbf{ih_i}, \textbf{dh_i} ≤ \textbf{10^6}). Далі йде \textbf{k} блоків, які описують атаки дракона у хронологічному порядку. Якщо чергова атака --- вогнений смерч, то перший рядок блоку являє собою єдине слово "\textbf{Storm}". У другому рядку блока через пропуск записані цілі числа \textbf{d} та \textbf{t} --- потужність та тривалість заклинання (\textbf{1} ≤ \textbf{d}, \textbf{t} ≤ \textbf{10^6}). У третьому рядку блоку записані цілі числа \textbf{x} та \textbf{y} --- координати центру смерчу (\textbf{−1000} ≤ \textbf{x}, \textbf{y} ≤ \textbf{1000}). Якщо чергова атака --- подих дракона, то перший рядок блоку являє собою єдине слово "\textbf{Breath}". У другому рядку блоку через пропуск записані цілі числа \textbf{d} та \textbf{t} --- потужність та тривалість заклинання (\textbf{1} ≤ \textbf{d}, \textbf{t} ≤ \textbf{10^6}). У наступних \textbf{n + m} рядках блоку задано по два цілих числа \textbf{x_i} та \textbf{y_i} --- координати відносно безпечних місць (\textbf{−1000} ≤ \textbf{x_i}, \textbf{y_i} ≤ \textbf{1000}). Усі відносно безпечні місця розміщені у різних точках. Якщо чергова атака --- удар хвостом, то блок, який її описує, складається з єдиного рядка "\textbf{Tail}". Гарантується, що серед усіх атак є рівно один удар хвостом і що він завершує список атак. Також гарантується, що у списку немає більше двох подихів дракона підряд. Тривалість заклинання дракона вимірюється в секундах, координати --- в метрах, швидкість магов --- у метрах за секунду. Потужність аури мага та потужність заклинання дракона вимірюються в одиницях здоров'я за секунду, швидкість зростання/зменшення потужності аури мага --- в одиницях здоров'я в секунду за секунду. Зверніть увагу на те, що хоча усі числа у вхідних даних цілі, переміщення, шкода, сцілення та зміна потужності аури відбувається неперервно. \OutputFile Якщо маги не здатні вбити дракона, виведіть "\textbf{You are not prepared}". У протилежному випадку у першому рядку виведіть "\textbf{No useful loot again}". У другому рядку виведіть єдине ціле число --- мінімальний номер атаки дракона, під час якої ві може померти. Атаки нумеруються з одиниці.
Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB
Вхідні дані #1
1 1 2
1 5 10
1 3 2
1 1 1
Storm
7 11
0 0
Tail
Вихідні дані #1
No useful loot again
1
Автор Денис Дубльонних
Джерело 2013 Петрозаводск, Зима, Контест Уральского университета, Кубок Контура, Задача B