TLE '17 Contest 8 P2 - Ship Defense

View as PDF

Submit solution


Points: 5 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type
Fax McClad attacked by enemy ships.

Fax McClad, Croneria's most defensive bounty hunter, is under attack by the Dankey Kang Gang! He must activate certain defense modes on his personal ship, the Kyuwing, in order to prevent as much damage as possible.

Fax's Kyuwing has H health points and is equipped with D defense modes. Each defense mode has an armor and shield component. Every second, shields block up to Si of the incoming damage while armor reduces the remaining damage by Ai%. At any given time, at most one defense mode can be activated, and defense modes can be reactivated.

There are E enemy ships that each shoot at Fax's Kyuwing over the course of the battle. Enemy ship j deals Xj damage for Lj seconds starting at the Tjth second. Note that at any second, the incoming damage is the total damage from all sources at that second.

Since repairs can be quite expensive, Fax wants to optimally choose defense modes to activate in order to reduce the amount of damage he receives. Can you tell him the maximum amount of health points that his ship can have after these enemy encounters?

Input Specification

The first line contains three space-separated integers: H (1H108), D (0D5), and E (0E1000).

D lines of input follow. The ith line contains Ai (0Ai100) and Si (0Si10000).

E lines of input follow. The jth line contains Tj (0Tj500), Lj (1Lj500), and Xj (1Xj50).

Output Specification

The maximum amount of health points that Fax's ship can have remaining, rounded to two decimal places.

If Fax's ship cannot sustain all of the damage, that is, his Kyuwing's health points become 0, then output: DO A BARREL ROLL!.

Sample Input 1

Copy
100 2 2
50 0
0 10
0 10 11
5 1 50

Sample Output 1

Copy
60.50

Explanation 1

Fax should utilize defense mode 1 during the fifth second.

During all other times, Fax should switch to defense mode 2 in order to block more of the incoming damage.

Sample Input 2

Copy
10 1 1
50 10
3 1 50

Sample Output 2

Copy
DO A BARREL ROLL!

Comments

There are no comments at the moment.