11092 - IIUC HexWorld

[jurajz]

I have AC this problem, but I am not satisfied with my solution. Time 0.879, memory 30400.

Distance of Alice is easy, just abs(A-B). For distance of Bob, I precalculated x and y coordinate and some addition variables for every cell, but I remember only every 10th cell, for avoiding of MLE. Then, for A and B, I made additional computation to find out x and y coordinate for A and B and then write as result sqrt(sqr(xA-xB)+sqr(yA-yB)).

As I can see, most of solutions are accepted in minimum memory and very good time (the best is 0.002). Any idea for easy solution of Bob distance, without precalculation?

Thanks in advance!

Please sorry for my bad english.

[fushar]

To calculate the position of an arbitrary point on this grid, first we have to know on which layer it resides. Example: 0 is on the 0th layer, 3 is 1st, 26 is 3rd, etc. Notice that number of points on each layer is 6^n, the layer can be computed easily. Now that we know the layer, we determine on which side of the hexagon the point lies. There are 6 sides, so there are 6 conditional-if.

This problem is very similar to this TopCoder SRM problem, http://www.topcoder.com/stat?c=problem_ ... nt&pm=6093