11453 - Traveling fishmonger

[baodog]

Cartagena 211286

Just at the first city, I can sell 5*(211286/10000)=105 fish, for
a profit of 1050 !! Which is greater than 594, the sample answer!!
I think the I/O is very wrong...

btw, I'm getting 2063 with floyd warshall + TSP DP.

[sohel]

Something is definitely wrong with this problem. Either the I/O is wrong or they couldn't explain the problem clearly.
I also started with selling the fishes in the base city and that yielded a profit of 1050. And later thought selling could only be done in one of the destination cities, but that also yields a profit > 594.

There wasn't even a single submission during the online contest. I guess, nobody could come up with a solution that matches the I/O.

[brianfry713]

The sample output is wrong, it should be:
Murcia Lorca -> 1250

He takes 3 days to travel the 55 km between Cartagena and Murcia, and then sell 422861 / 2000 = 211 fish on the next day. The price is 10 / (pow(1.2, 3) = 5.79, yielding a profit at Murcia of 1221.06.
He takes 11 more days to get to Lorca, then sells 44 fish. The price is 10 / (pow(1.2, 15) = 0.65, yielding a profit at Lorca of 28.56.
The total profit is 1249.62