codeforces-scrape

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

32D.md (2431B)


      1 Source: https://codeforces.com/problemset/problem/32/D
      2 
      3 D. Constellation
      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 A star map in Berland is a checked field *n* × *m* squares. In each square there is or there is not a star. The favourite constellation of all Berland's astronomers is the constellation of the Cross. This constellation can be formed by any 5 stars so, that for some integer *x* (radius of the constellation) the following is true:
     22 
     23 * the 2nd is on the same vertical line as the 1st, but *x* squares up
     24 * the 3rd is on the same vertical line as the 1st, but *x* squares down
     25 * the 4th is on the same horizontal line as the 1st, but *x* squares left
     26 * the 5th is on the same horizontal line as the 1st, but *x* squares right
     27 
     28 Such constellations can be very numerous, that's why they are numbered with integers from 1 on the following principle: when two constellations are compared, the one with a smaller radius gets a smaller index; if their radii are equal — the one, whose central star if higher than the central star of the other one; if their central stars are at the same level — the one, whose central star is to the left of the central star of the other one.
     29 
     30 Your task is to find the constellation with index *k* by the given Berland's star map.
     31 
     32 Input
     33 
     34 The first line contains three integers *n*, *m* and *k* (1 ≤ *n*, *m* ≤ 300, 1 ≤ *k* ≤ 3·107) — height and width of the map and index of the required constellation respectively. The upper-left corner has coordinates (1, 1), and the lower-right — (*n*, *m*). Then there follow *n* lines, *m* characters each — description of the map. *j*-th character in *i*-th line is «*», if there is a star in the corresponding square, and «.» if this square is empty.
     35 
     36 Output
     37 
     38 If the number of the constellations is less than *k*, output -1. Otherwise output 5 lines, two integers each — coordinates of the required constellation. Output the stars in the following order: central, upper, lower, left, right.
     39 
     40 Examples
     41 
     42 Input
     43 
     44 ```
     45 5 6 1  
     46 ....*.  
     47 ...***  
     48 ....*.  
     49 ..*...  
     50 .***..
     51 ```
     52 
     53 Output
     54 
     55 ```
     56 2 5  
     57 1 5  
     58 3 5  
     59 2 4  
     60 2 6
     61 ```
     62 
     63 Input
     64 
     65 ```
     66 5 6 2  
     67 ....*.  
     68 ...***  
     69 ....*.  
     70 ..*...  
     71 .***..
     72 ```
     73 
     74 Output
     75 
     76 ```
     77 -1
     78 ```
     79 
     80 Input
     81 
     82 ```
     83 7 7 2  
     84 ...*...  
     85 .......  
     86 ...*...  
     87 *.***.*  
     88 ...*...  
     89 .......  
     90 ...*...
     91 ```
     92 
     93 Output
     94 
     95 ```
     96 4 4  
     97 1 4  
     98 7 4  
     99 4 1  
    100 4 7
    101 ```