OJ Board

I still wonder how people get this calculated in under 0.002s.. What worked for me was to first cache pairs (c, d) for every x: 1..20'000'000 such that x = 2^a * 5^b * r; c = a - b; // easily calculated d = r % 10; Then considering: if x -> (c, d) then lastnonzerodigit(x) = { d, if c = 0 | 5, if c<0...

Gradient descent with centroid as a starting point works well too.
Is there a geometrical solution though?

A simpler example where single Floyd-Warshall is too greedy: it discards shorter path over city 3 because it's expensive to party there, even though a more expensive city (5) is inevitably encountered later. 5 5 1 10 10 20 10 30 1 2 2 1 3 1 2 4 2 3 4 1 4 5 5 1 5 I'm guessing running the algorithm th...