codeforces-scrape

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

268C.md (1819B)


      1 Source: https://codeforces.com/problemset/problem/268/C
      2 
      3 C. Beautiful Sets of Points
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 Manao has invented a new mathematical term — a beautiful set of points. He calls a set of points on a plane beautiful if it meets the following conditions:
     22 
     23 1. The coordinates of each point in the set are integers.
     24 2. For any two points from the set, the distance between them is a non-integer.
     25 
     26 Consider all points (*x*, *y*) which satisfy the inequations: 0 ≤ *x* ≤ *n*; 0 ≤ *y* ≤ *m*; *x* + *y* > 0. Choose their subset of maximum size such that it is also a beautiful set of points.
     27 
     28 Input
     29 
     30 The single line contains two space-separated integers *n* and *m* (1 ≤ *n*, *m* ≤ 100).
     31 
     32 Output
     33 
     34 In the first line print a single integer — the size *k* of the found beautiful set. In each of the next *k* lines print a pair of space-separated integers — the *x*- and *y*- coordinates, respectively, of a point from the set.
     35 
     36 If there are several optimal solutions, you may print any of them.
     37 
     38 Examples
     39 
     40 Input
     41 
     42 ```
     43 2 2
     44 ```
     45 
     46 Output
     47 
     48 ```
     49 3  
     50 0 1  
     51 1 2  
     52 2 0
     53 ```
     54 
     55 Input
     56 
     57 ```
     58 4 3
     59 ```
     60 
     61 Output
     62 
     63 ```
     64 4  
     65 0 3  
     66 2 1  
     67 3 0  
     68 4 2
     69 ```
     70 
     71 Note
     72 
     73 Consider the first sample. The distance between points (0, 1) and (1, 2) equals ![](https://espresso.codeforces.com/bfe16f27ebc966df6f10ba356a1547b6e7242dd7.png), between (0, 1) and (2, 0) — ![](https://espresso.codeforces.com/23d63d8a57cddda72562a512c05111054cd85870.png), between (1, 2) and (2, 0) — ![](https://espresso.codeforces.com/23d63d8a57cddda72562a512c05111054cd85870.png). Thus, these points form a beautiful set. You cannot form a beautiful set with more than three points out of the given points. Note that this is not the only solution.