codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ```