2072E.md (1805B)
1 Source: https://codeforces.com/problemset/problem/2072/E 2 3 E. Do You Love Your Hero and His Two-Hit Multi-Target Attacks? 4 5 time limit per test 6 7 3 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Akito decided to study a new powerful spell. Since it possesses immeasurable strength, it certainly requires a lot of space and careful preparation. For this, Akito went out into the field. Let's represent the field as a Cartesian coordinate system. 22 23 For the spell, Akito needs to place $0 \le n \le 500$ staffs at distinct integer coordinates in the field such that there will be exactly $k$ pairs $(i, j)$ such that $1 \le i \lt j \le n$ and $\rho(i, j) = d(i, j)$. 24 25 Here, for two points with integer coordinates $a = (x_a, y_a)$ and $b = (x_b, y_b)$, $\rho(a, b) = \sqrt{(x_a - x_b)^2 + (y_a - y_b)^2}$ and $d(a, b) = |x_a - x_b| + |y_a - y_b|$. 26 27 Input 28 29 The first line of input contains a single number $t$ ($1 \le t \le 1000$) — the number of test cases. 30 31 In the only line of each test case, there is a single number $k$ ($0 \le k \le 10^5$) — the number of pairs of staffs for which the equality $\rho(i, j) = d(i, j)$ must hold. 32 33 Output 34 35 For each test case, the first line of output should print the number $n$ ($0 \le n \le 500$) — the number of placed staffs. 36 37 In the following $n$ lines, pairs of integers $x_i, y_i$ $(-10^9 \le x_i, y_i \le 10^9)$ should be printed — the coordinates of the $i$-th staff. The points in which staffs stand must be distinct. 38 39 Example 40 41 Input 42 43 ``` 44 3 45 46 0 47 48 2 49 50 5 51 ``` 52 53 Output 54 55 ``` 56 6 57 69 52 58 4 20 59 789 9308706 60 1337 1337 61 -1234 -5678 62 23456178 707 63 10 64 -236 -346262358 65 273568 6435267 66 2365437 31441367 67 246574 -45642372 68 -236 56 69 4743623 -192892 70 10408080 -8173135 71 -237415357 31441367 72 -78125638 278 73 56 143231 74 5 75 1 1 76 2 1 77 1 5 78 3 5 79 1 10 80 ```