- Home
- Uncategorized
- COP 3502h Assignment 5 Dragon’s Greed

$30.00

Category: Uncategorized

Description

5/5 - (4 votes)

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.