codeforces-scrape

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

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 ![](https://espresso.codeforces.com/a0c6a684203590998776587e7f02c93ba5771038.png).
     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 ```