#include using namespace std; int main() { int n, v, g, x, y; cout << "n = "; cin >> n; while (g < n) { v++; g = 8 * (v * (v + 1) / 2); } if (n >= g - 2 * v) { // Bottom row y = -v; x = v - (g - n); } else if (n >= g - 4 * v) { // Left column x = -v; y = ((g - 2 * v) - n) - v; } else if (n >= g - 6 * v) { // Top row y = v; x = ((g - 4 * v) - n) - v; } else { // Right column x = v; y = v - ((g - 6 * v) - n); } printf("(%d;%d)\n", x, y); return 0; } /* -------------- * Task condition * -------------- * You have a spiral of whole numbers, starting from 0, like this: * * 36 < 35 < 34 < 33 < 32 < 31 < 30 * V ^ * 37 16 < 15 < 14 < 13 < 12 29 * V V ^ ^ * 38 17 4 < 3 < 2 11 28 * V V V ^ ^ ^ * 39 18 5 0 > 1 10 27 ... * V V V ^ ^ ^ * 40 19 6 > 7 > 8 > 9 26 51 * V V ^ ^ * 41 20 > 21 > 22 > 23 > 24 > 25 50 * V ^ * 42 > 43 > 44 > 45 > 46 > 47 > 48 > 49 * * You are given a number n and your goal is to find the coordinates of the number. * The distance between two neighbouring numbers is 1, meaning 0 is at (0;0), 1 is at (1;0), 38 is at (-3;1). * * -------------------------- * Explanation of my solution * -------------------------- * * My solution is a very mathematical one. First, I divide the spiral into squares, * depending on the offset of 0;0. * Example: * - Square 1 (because x and y are between -1 and 1 (one of them is always 1 or -1)): * 4 < 3 < 2 * V ^ * 5 1 * V * 6 > 7 > 8 * * - Square 2 (because x and y are between -2 and 2 (one of them is always 2 or -2)): * 16 < 15 < 14 < 13 < 12 * V ^ * 17 11 * V ^ * 18 10 * V ^ * 19 9 * V * 20 > 21 > 22 > 23 > 24 * * - Square 3 (because x and y are between -3 and 3 (one of them is always 3 or -3)): * 36 < 35 < 34 < 33 < 32 < 31 < 30 * V ^ * 37 29 * V ^ * 38 28 * V ^ * 39 27 * V ^ * 40 26 * V ^ * 41 25 * V * 42 > 43 > 44 > 45 > 46 > 47 > 48 * * And so on. I call the number of the square "v". * * Then there is the biggest number in the square, the one in the bottom right corner, I call that "g". * g for square 1 (v = 1) is 8, for v = 2: g = 24, for v = 3: g = 48 and so on. * We can see that each g is divisble by 8, but the multiplier is slightly tricky to find. * The multiplier is the sum of all whole number from 1 up until v. * * Example: * v = 2 * g = 8 * (Sum of numbers from 1 to v) = 8 * (1 + 2) = 8 * 3 = 24 * * v = 3 * g = 8 * (Sum of numbers from 1 to v) = 8 * (1 + 2 + 3) = 8 * 6 = 48 * * After we've found g and v, we start looking at the numbers in the corners. * The bottom right corner is g by definition, the bottom left corner is g - 2 * v, * the top left is g - 4 * v and the top right is g - 6 * v. * By comparing the values in the corners we can determine where the number is: * top row, bottom row, left column or right column. * * Example: * v = 2, g = 24, n = 11 * * if (n > bottom left corner) number is on bottom row (between 20 and 24) * else if (n > top left corner) number is on left column (between 16 and 20) * else if (n > top right corner) number is on top row (between 16 and 12) * else number is on right column (between 12 and 9) * * After we find on which side the number is, we can immediately determine the x or y coordinate, * as it will be +v or -v. * The final step is to determine the other coordinate. The formula differs slightly depending on a side, * but the gist of it is that we look at the difference between a corner number and our number, which gives * us distance from the corner number and we offset the searched coordinate. * * Example: * v = 2, g = 24, n = 11 * We have determined that our number is in the right column. * This means we know for sure that the X coordinate of n is 2. * * offset = corner number - n = (g - 6 * v) - 11 = 12 - 11 = 1 * * The Y coordinate of the corner number is 2 (12 is located at (2;2)). * In our case, we want to subtract our offset from that coordinate, so * * Y coordinate of n = Y coordinate of corner number - offset = 2 - 1 = 1. * * And so we found that n is located at (2;1) */