So Square I Dont Care
All submissions for this problem are available.Murphy is on an investigation of the quantum data based on the values obtained from the black hole. She is now trying to finish her analysis and reconcile the gravity equation with quantum mechanics. In her last step she now needs to analyse systems with multiple objects at large distances. To explain in detail, she is given a number $N$. She needs to find a maximal cardinal set of lattice points lying within the region enclosed by $0 \leq x \leq N$, $0 \leq y \leq N$ such that the Manhattan distance between any two of them is at least $N$. A lattice point is a point whose integers are both coordinates. A Manhattan distance is the sum of absolute differences of each coordinate. Formally, the Manhattan distance between two points $(x_1,y_1)$ and $(x_2,y_2)$ is $|x_1-x_2|+|y_1-y_2|$. Since she can not find this out, she wants your help. ###Input Format - The first line has $T$, the number of test cases. - For each test case, the only line has an integer $N$. ###Constraints - $1 \leq T \leq 10$ - $1 \leq N \leq 100000$ ###Output Format - For each test case, print multiple lines. - In the first line, print the number of points. - In the next lines, in each line, print two space separated integers, denoting the $x$ and $y$ coordinates of each point. - If there are multiple correct solutions, you may print any. ###Sample Input 2 1 3 ###Sample Output 4 0 0 0 1 1 0 1 1 4 0 1 1 3 3 2 2 0
|Tags||constructive, math, shpc2019, shriram_c253|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.