1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
|
#include <iostream>
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)
*/
|
