311A.md (2293B)
1 Source: https://codeforces.com/problemset/problem/311/A 2 3 A. The Closest Pair 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 Currently Tiny is learning Computational Geometry. When trying to solve a problem called "The Closest Pair Of Points In The Plane", he found that a code which gave a wrong time complexity got Accepted instead of Time Limit Exceeded. 22 23 The problem is the follows. Given *n* points in the plane, find a pair of points between which the distance is minimized. Distance between (*x*1, *y*1) and (*x*2, *y*2) is . 24 25 The pseudo code of the unexpected code is as follows: 26 27 ``` 28 input n 29 for i from 1 to n 30 input the i-th point's coordinates into p[i] 31 sort array p[] by increasing of x coordinate first and increasing of y coordinate second 32 d=INF //here INF is a number big enough 33 tot=0 34 for i from 1 to n 35 for j from (i+1) to n 36 ++tot 37 if (p[j].x-p[i].x>=d) then break //notice that "break" is only to be 38 //out of the loop "for j" 39 d=min(d,distance(p[i],p[j])) 40 output d 41 ``` 42 43 Here, *tot* can be regarded as the running time of the code. Due to the fact that a computer can only run a limited number of operations per second, *tot* should not be more than *k* in order not to get Time Limit Exceeded. 44 45 You are a great hacker. Would you please help Tiny generate a test data and let the code get Time Limit Exceeded? 46 47 Input 48 49 A single line which contains two space-separated integers *n* and *k* (2 ≤ *n* ≤ 2000, 1 ≤ *k* ≤ 109). 50 51 Output 52 53 If there doesn't exist such a data which let the given code get TLE, print "no solution" (without quotes); else print *n* lines, and the *i*-th line contains two integers *x**i*, *y**i* (|*x**i*|, |*y**i*| ≤ 109) representing the coordinates of the *i*-th point. 54 55 The conditions below must be held: 56 57 * All the points must be distinct. 58 * |*x**i*|, |*y**i*| ≤ 109. 59 * After running the given code, the value of *tot* should be larger than *k*. 60 61 Examples 62 63 Input 64 65 ``` 66 4 3 67 ``` 68 69 Output 70 71 ``` 72 0 0 73 0 1 74 1 0 75 1 1 76 ``` 77 78 Input 79 80 ``` 81 2 100 82 ``` 83 84 Output 85 86 ``` 87 no solution 88 ```