Description
As the story goes the legendary, evil Gold Dragon, Troggate, is tired of his Dragon brethren
displaying their exquisite gold collections, and so Troggate has decided to get some gold from a
nearby settlement of smiths.
The small hamlet of Inflamaville is under threat of burning to the ground, if they cannot
produce enough gold to appease Troggatei
. Luckily like any great oppressor Troggate has some
exact (and known) threshold of gold that Troggate will accept in return for a non-razed village.
Unfortunately, Troggate will return at some predetermined moment in time to collect the said
gold amount, so the smiths of Inflamaville need to work quickly. You, the proprietor, of said
town will try to determine how quickly your smiths will need to work to meet Troggate’s
demand. Since other dragons are in the area you will make a general program to solve this
problem.
Your village has some incoming shipments of gold ore of varying qualities. The village smiths
can only work on one ore shipment at a time. However, your smiths can change which
shipment they work on instantaneously without finishing the prior shipment. Additionally,
smiths can work on shipments they had previously worked on without penalty. Smiths are
somewhat meticulous and will always work at the same paceii
.
The smiths work at some rate, s, determined by you, such that in one minute they can
process exactly s kilos of ore.
Additionally, not all ore is the same each shipment has some non-negative integer
quality q (q ≤ 1000), meaning that for every kilo of ore processed in the shipment
exactly q grams of gold is produced.
This means that gold ore with a higher quality will result in a quicker rate of acquiring gold ore!
You don’t want to overwork your smiths, so your job is to find the smallest s your smiths can
work at such that your village won’t be burned to the ground at each time when Troggate
returns. As in real life there might be situations in which appeasing Troggate is impossible. If
such is the case, your program should inform the user of the unrealistic demands.
Input Specification
The first line of input consists of a single positive integer, N, (N ≤ 105
) representing the number of
shipments. The next N lines contain one shipment description per line, composed of 3 positive integers,
t, a, and q, (t≤105
, a≤104
, q≤103
), representing the time the shipment arrives (in minutes from Troggates
demand), the amount of ore in kilos, and the quality of the shipment. The last line contains two positive
integers, t and a, (t≤105
, a≤104
) representing the time Trogate will arrive at the town (in minutes from
Troggate’s demand) and the amount of gold Troggate (in kilos) will request in kilos at time t. Troggate
will not arrive in town the same time as a shipment.
Output Specification
The first and only line of output should be either a single floating point number, s, representing the
minimum rate at which Inflamaville needs to process ore, such that it can meet Troggate’s goal. If there
is no way to satisfy Troggate’s greed, the output should be “HCF!”. Your answer will be considered
correct, if it has an error smaller than 10-4
(absolute or relative).
Sample Input Sample Output
4
1000 1000 10
8000 2000 20
9001 3000 40
2000 5000 50
2500 100
3.6
1
1000 1000 10
999 1
HCF!
4
1000 1000 10
8000 2000 20
9001 3000 40
2000 5000 50
10000 300
0.789556784
Explanation of Cases
Case 1
Our smiths finish processing the first section quickly. It takes less than 1000 time. So we get the full
amount, which is 1000 * 10 / 1000 = 10 kilos.
The second delivery (time 8000) and third delivery (time 9001) do not arrive before Troggate.
The fourth delivery arrives, but since Troggate arrives at time 2500, we have only 500 minutes to work.
This allows us to process (500 * 3.6) or 1800 kilos of ore. With these 1800 kilos we get (1800 * 50 / 1000)
= 90 kilos of gold.
Thus sum of these two amounts is the target of 100 kilos.
Case 2
Troggate arrives before any shipments. There is no way to satisfy him.
Case 3
With that awkward rate, we can process the first shipment for 1000 minutes. This gives us 7.8955 or so
kilos of gold. The fourth shipment is fully processed before the second or third shipment arrive. This
means that we acquire 250 kilos from shipment 4. We finish shipment 4 @ 8332.6666 minutes after
Troggates demand. We then process shipment 2 for 668.3333 minutes before shipment 3 arrives. We
get out 10.5537419 kilos. We then process shipment 3 for 999 minutes acquiring 31.550685732 kilos.
Shipment Time Amount of gold in kg
(approximations)
1 1000 7.8955
2 668.3333 10.5537419
3 999 31.550685732
4 8332.6666 250
Grading Criteria
Standard Input/output – 5 points
Style points – 25 points
Use a Heap/Priority Queue – 10 points
Use a Binary Search – 10 points
10 Cases from Dr. Meade – 5 points each
A maximum of 50 points will be given to solutions without a heap.
Extra Credit
For this problem you should write your own “difficult” case as well to get extra points.
No points will be given to cases that do not follow the input specification.
Each classmate’s solution your case breaks gives you points
Wrong answer 3 points
Runtime error 3 points
Time limit (10 – 20 seconds) 1 point
Time limit (20 – 60 seconds) 2 points
Time limit (60+ seconds) 3 points
Each case you work on gives you 1 point
i The author of this problem does not condone the burning of villages or the extortion of gold collecting peasants.
ii When no gold ore is available, the smiths will work on a sizable backlog of silver ore that needs processing.
