ajinkyakale_86 wrote: > Hi here is a problem for you to ponder on. Was asked in one of the > ACM's competition I suppose. The > problem is that consider a spiral matrix increasing in cloackwise > fashion like this one.. > > 7 8 9 ... > 6 1 2 > 5 4 3 > > The position of element 1 is considered to b (0,0). Write a code to > find the position of the element entered. For example, if 3 is > entered, answer is (1,1). If 5 is entered, answer is (-1,1)... > (The element can be any positive number...)
For some reason, this reminded me of "parametric equations". It sometimes helps to expand out the given ACM set. 73 74 75 76 77 78 79 80 81 72 43 44 45 46 47 48 49 50 71 42 21 22 23 24 25 26 51 70 41 20 7 8 9 10 27 52 69 40 19 6 1 2 11 28 53 68 39 18 5 4 3 12 29 54 67 38 17 16 15 14 13 30 55 66 37 36 35 34 33 32 31 56 65 64 63 62 61 60 59 58 57 Probably a "takes too long" problem if you try to iteratively scan the spiral on a really large number. Something that would significantly reduce the time is to notice that the diagonal contains the squares of 1, 3, 5, 7, 9, ... (1, 9, 25, 49, 81). Then only four compares (maximum) need to be done to determine which side the target number is on. Once that is determined, the position is easy to calculate. Figuring out which diagonal is being used is pretty straight-forward - use (unsigned int)sqrt(element) with a little tweaking if the result is even. Probably useful to special-case 1 (the center). -- Thomas Hruska CubicleSoft President Ph: 517-803-4197 *NEW* VerifyMyPC 2.5 Change tracking and management tool. Reduce tech. support times from 2 hours to 5 minutes. http://www.CubicleSoft.com/VerifyMyPC/
